在一个STArrays列表上映射runSTArray？

Question

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

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

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

到现在为止还挺好.我可以检查n-th矩阵(类型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的工作原理.从STmonad到纯代码的唯一方法是使用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扩展名.