将runSTArray映射到STArrays列表中？

问题描述：

我有一个递归创建矩阵的扁平化列表的功能，它必须是可变的，因为它们的元素在创建时经常更新。到目前为止，我想出了一个具有签名递归解决方案：将runSTArray映射到STArrays列表中？

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

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

到目前为止这么好。我可以在ghci

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

检查（的Array (Int, Int) Int型）n个矩阵确实为我的算法正确的结果。但是，我没有找到一种方法，在由doAll返回列表映射runSTUArray：如果我尝试在列表递归评估或试图评估包裹在一个单一的元素

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关键字的含义）以及如何评估列表中的数组？

http://www.mail-archive.com/[email protected]/msg47957.html –

答

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

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

您可以解决此通过定义一个新的功能，首先冻结ST单子里面的阵列，然后运行所产生的ST行动：

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

注意forall需要RankNTypes扩展。

谢谢你的解释，这很有道理。但是，我必须在'runSTArrays'中删除'runST'，然后单独调用它。 'ghc'不能推导出上下文，也不能接受明确的类型注释。 – bbtrb

对不起，我已经为此代码添加了适当的类型注释。 GHC不会推断出更高级别的注释（全部），因此需要手动提供。 –

序列是否有一个占位符，用于程序将“具有更新数组内容的某些功能”的位置？ – misterbee

答

你刚刚反弹了类型系统的局限性。

runSTArray具有较高的排名类型。你必须传递一个ST行为，其状态类型变量是唯一的。然而，在Haskell中，通常不可能在列表中包含这样的值。

整个事情是一个聪明的方案，以确保您在ST行动中产生的价值无法逃离那里。这意味着，它看起来像你的设计在某种程度上被打破了。

一个建议：你不能在其他ST动作过程的值，比如

sequence [ ... your ST s (STArray s x) ...] >>= processing 
    where 
    processing :: [STArray s x] -> ST s (your results)

我会感兴趣的是，我的设计可能会被破坏（不是我怀疑它，我是对于haskell来说非常新颖）。你是否有一些关于如何管理不断增长的可变矩阵列表以供评估的建议？ – bbtrb

@bbtrb - 也许这不是设计本身，而是希望与一系列'ST s ...'的东西一起工作。基本上，这样的矩阵是可变数据，这意味着你不能（或者至少不应该）在ST或IO动作之外使用它们。确切地说，这是由John L告诉你的runST *系列功能强制实施的。 'freeze'只是告诉Haskell系统的一种方式，今后你想将矩阵（或其他）作为只读值处理，然后让它在ST动作中构建的值的转义（副本）。 – Ingo

将runSTArray映射到STArrays列表中？

相关推荐