haskell - 分段可变状态的单子

Question

我知道普通的State工作原理（编辑：显然不是！）。

如果我需要创建一个数组，并且一次创建整个数组不方便，我可以创建一个STArray，填充它，然后冻结并将一个普通的不可变数组返回给用户。

现在假设我需要同时创建两个不同类型的数组。

更一般地说，我可能想创建一个带有可变节点的任意图，逐个节点修改它一段时间，就像我会STArray逐个单元格修改一样，然后立即冻结整个图并返回正常的不可变数据。

我不想诉诸IOArrays 或IO单子中的任何东西。我有哪些选择？

标签： haskellstate-monad

Answer 1

这里有一些选项。

{-# LANGUAGE RankNTypes #-}
{-# LANGUAGE ScopedTypeVariables #-}
module TestSTArray where

import Control.Monad.ST
import Data.Array.ST
import Data.Array
import Data.Array.MArray

-- not needed until later on    
import GHC.Arr (unsafeFreezeSTArray)

基本的、安全的方法是冷冻。但是，这将导致复制。

test2Safe :: (Array Int Char, Array Int Bool)
test2Safe = runST $ do
   a1 <- newArray (0,9) 'A' :: ST s (STArray s Int Char)
   a2 <- newArray (0,9) False :: ST s (STArray s Int Bool)
   writeArray a1 5 'B'
   x <- readArray a2 6
   writeArray a1 7 (if x then 'X' else 'Y')
   writeArray a2 5 True
   arr1 <- freeze a1
   arr2 <- freeze a2
   return (arr1, arr2)

更有风险但可能仍然安全的是利用低杠杆/不安全的 GHC 原语并构建安全的扩展变体runSTArray。这样我们就避免了复制。

runSTArray2 :: (forall s. ST s (STArray s i1 e1, STArray s i2 e2))
            -> (Array i1 e1, Array i2 e2) 
runSTArray2 st = runST $ do
  (a1, a2) <- st
  (,) <$> unsafeFreezeSTArray a1 <*> unsafeFreezeSTArray a2

我相信上面使用的unsafe东西其实是安全的，因为我们在不安全冻结后不再使用a1,a2，所以不需要复制。

当然，上面的包装器可以推广到更多的数组。可以说，应该将更通用的版本放入库中。

最后，我们可以利用辅助功能：

test2LessSafe :: (Array Int Char, Array Int Bool)
test2LessSafe = runSTArray2 $ do
   a1 <- newArray (0,9) 'A' :: ST s (STArray s Int Char)
   a2 <- newArray (0,9) False :: ST s (STArray s Int Bool)
   writeArray a1 5 'B'
   x <- readArray a2 6
   writeArray a1 7 (if x then 'X' else 'Y')
   writeArray a2 5 True
   return (a1, a2)