arrays - 在 STArrays 列表上映射 runSTArray？

Question

我有一个函数可以递归地从树中创建一个扁平的矩阵列表，这些矩阵必须是可变的，因为它们的元素在创建过程中经常更新。到目前为止，我已经提出了一个具有签名的递归解决方案:

doAll :: .. -> [ST s (STArray s (Int, Int) Int)]

我不返回 [UArray (Int,Int) Int] 的原因直接是因为 doAll递归调用，修改列表中矩阵的元素并附加新矩阵。我不想不必要地卡住和解冻矩阵。

到目前为止，一切都很好。我可以检查 n - Array (Int, Int) Int 中的第矩阵(类型为 ghci)

runSTArray (matrices !! 0)
runSTArray (matrices !! 1)

事实上，我的算法得到了正确的结果。但是，我没有找到映射 runSTUArray 的方法超过 doAll 返回的列表:

map (runSTArray) matrices

Couldn't match expected type `forall s. ST s (STArray s i0 e0)'
            with actual type `ST s0 (STArray s0 (Int, Int) Int)'

如果我尝试对列表进行递归评估或尝试评估包含在函数中的单个元素，则会发生同样的问题

有人可以解释发生了什么(我并不真正理解 forall 关键字的含义)以及如何评估列表中的数组？

Answer 1

这是导致 ST 的类型技巧的不幸结果。安全的。首先，您需要了解 ST 的工作原理。从 ST 获取的唯一方法monad 到纯代码是 runST函数，或其他基于它的函数，如 runSTArray .这些都是 forall s. 的形式.这意味着，为了从 STArray 构造一个 Array，编译器必须能够确定它可以用它喜欢的任何类型替换 s。 runST 内的类型变量.

现在考虑函数 map :: (a -> b) -> [a] -> [b] .这表明列表中的每个元素必须具有完全相同的类型( a )，因此也必须具有相同的 s .但是这个额外的约束违反了 runSTArray 的类型。 ，它声明编译器必须能够自由地用其他值替换 s .

您可以通过定义一个新函数来解决此问题，首先卡住 ST monad 中的数组，然后运行生成的 ST 操作:

runSTArrays :: Ix ix => (forall s. [ST s (STArray s ix a)]) -> [Array ix a]
runSTArrays arrayList = runST $ (sequence arrayList >>= mapM freeze)

注意 forall需要 RankNTypes扩大。