序列部分应用的单子动作

Question

我知道这可能很明显，但我的 hoogle-fu 在这里让我失望了。我有以下类型的操作列表：

import Data.Vector.Mutable (STVector)
[STVector s a -> ST s ()]

也就是说，一组采用起始 MVector 并以某种方式对其进行变异的操作

我也有一个起始向量

import Data.Vector         (Vector, thaw, freeze)
v :: Vector a

解冻后v，如何将这些操作排序为最终结果？

doIt :: forall s. Vector a -> [STVector s a -> ST s ()] -> Vector a
doIt v ops = runST $ do
  v' <- thaw v
  -- do all the things to v'
  unfreeze v'

如果上下文有帮助，我正在尝试 Advent of Code 的第 16 天拼图（第 2 部分），因此 ops 是一长串突变，我实际上需要运行通过十亿次。我希望能够使用 replicateM_ 来执行此操作，但看不到如何提供起始值。我同样认为 foldM_ 会起作用，但我似乎无法对其进行类型检查。也许我在做一些根本错误的事情？我不能说我完全理解 ST monad。

Answer 1

您要查找的操作是traverse_。它访问数据结构中的每个值，应用具有 monadic return 类型的函数，并将它们的效果排序在一起，同时丢弃它们的结果。 "discarding their results" 部分很重要。这意味着在这种情况下 traverse_ 的 return 类型将是 ST s () 而不是 ST s [()]。那里的差异很大。这意味着该操作不会建立一个巨大的 () 值列表以最终丢弃。

您要传递给 traverse_ 的函数是 "apply a function to v'" 的函数。这可以写成 \f -> f v'，但有一个更短的惯用版本，它使用 $ 运算符。注意，上面的lambda可以改写为\f -> f $ v'，可以改写为($ v').

段

所以你有traverse_ ($ v') ops，这是正确的操作，但它仍然不会进行类型检查。那是因为 runST 的类型，它要求 ST s 中的 s 类型是多态的。使用您编写的类型签名，s 由 doIt 的调用者选择。要使其正常工作，您需要通过确保 {-# LANGUAGE RankNTypes #-} 位于文件顶部来启用 RankNTypes 扩展，然后将类型更改为 Vector a -> (forall s. [STVector s a -> ST s ()]) -> Vector a。 s 类型变量范围的缩小要求 s 在传递给 doIt 的值中是多态的。有了这个限制，runST 将通过上述操作成功进行类型检查。

有关为什么 runST 具有如此有趣的类型的更多信息，请参阅 Lazy Functional State Threads，该论文介绍了 ST 类型并展示了如何使用它来限制外部纯内部的可变性界面。

序列部分应用的单子动作

Sequence partially-applied Monadic Actions

haskell

state-monad