Haskell：并行计算和 monad 的 'sequential property'

Question

我对为什么 REPA 函数 computeP 将其结果打包到 monad 感到困惑。它具有以下类型签名。

computeP :: (Load r1 sh e, Target r2 e, Source r2 e, Monad m) =>
            Array r1 sh e -> m (Array r2 sh e)

在this tutorial中说

The reason for this is that monads give a well defined notion of sequence and thus computeP enforces completion of parallel evaluation in a particular point of monadic computations.

同样，Stack Overflow 上的指出

The reason why parallel computation in Repa must be monadic has to do partially with lazyness, but mostly with Repa's inability to deal with nested parallelism. Sequential property of a Monad solves it for the most part[.]

问题

这个 'sequential property' 到底是什么意思？
monad 如何执行此操作？
对于computeP的例子：没有限制使用哪个monad，所以我可以使用identity monad。那么可以使用下面的函数来代替解包 monad 吗，或者这会产生意想不到的结果，因为它缺少这个顺序属性吗？如果可以的话，有必要使用 monad 吗？
```
import Data.Functor.Identity
import Data.Array.Repa.Eval
import Data.Array.Repa

myComputeP :: (Load r1 sh e, Target r2 e, Source r2 e) => Array r1 sh e -> Array r2 sh e
myComputeP = runIdentity . computeP
```

任何帮助都会很棒。

Answer 1

这个 monad 约束是一个启发式技巧。它帮助有纪律的用户避免嵌套并行，但对恶意或无知的用户没有任何作用。

嵌套并行是指在并行计算某个数组时，您最终不得不并行计算另一个数组的情况。 Repa不支持（原因不重要），所以尽量避免。

computeP的类型有助于确保并行计算彼此按顺序进行，但远非无懈可击；它只是一个 "best effort" 抽象。

How does a monad enforce this?

实际上，computeP 只适用于绑定 (>>=) 第一个参数严格的 monad，因此在 u >>= k 中，函数 k 将仅在评估 u 后应用。那么如果你使用 computeP 这样的 monad，

do w <- computeP v
   k w

保证向量 w 在传递给 k 之前被评估，这可以安全地执行其他 computeP 操作。

严格单子的例子：IO，严格State，Maybe，[]。
惰性 monad 的示例：Identity、惰性 State、Reader。（可以将惰性 monad 设置为严格的，但反之则不行。特别是，如果您只想进行 Repa 计算，则可以定义一个严格的恒等 monad。）

为了防止嵌套并行，computeP 的类型有意使其在可能并行完成的操作中使用起来很麻烦，例如 map :: (a -> b) -> Array _ _ a -> Array _ _ b 和 fromFunction :: sh -> (sh -> a) -> Array _ _ a，这采用非单子函数。仍然可以明确地展开 computeP，例如使用 runIdentity，如您所见：如果您愿意，您可以用脚射击自己，但是您需要为枪上膛，将其指向下方并扣动扳机.

希望这能回答 Repa 中发生的事情。以下是回答另一个问题的理论题外话：

What does having this 'sequential property' mean exactly?

那些引语很随意。在我看来，"sequentiality" 和 "monads" 之间的关系是双重的。

首先，对于 Haskell 中的许多 monad，(>>=) 的定义自然决定了求值顺序，通常是因为它会立即对第一个参数进行模式匹配。如前所述，这就是 Repa 所依赖的强制执行 computeP 计算按顺序发生的原因（这就是为什么如果将它专门化为 Identity 它会中断；它不是严格的 monad）。在事物的宏伟计划中，这是惰性评估的一个相当小的细节，而不是任何适合一般 monad 的东西。

其次，纯函数式编程的一个核心思想是首先-class 计算，明确定义效果和组合。在这种情况下，效果是向量的并行评估，而我们关心的组合是顺序组合。 Monad 为顺序组合提供了一个通用模型或接口。这是 monad 帮助解决 Repa 中避免嵌套并行性问题的另一部分原因。

重点不在于单子具有固有的顺序方面，而是顺序组合本质上是单子的：如果您尝试列出您期望从任何名副其实的东西中获得的一般属性 "sequential composition"，您最终可能会得到一起称为 "monad" 的属性；这是 Moggi 的开创性论文 "Notions of computation and monads".

的观点之一

"Monads" 不是一个神奇的概念，而是一个非常普遍的概念，因此很多事情恰好是 monad。毕竟，主要要求是有关联操作；对于顺序组合，这是一个非常合理的假设。（如果，当您听到 "associativity"，您会想到 "monoid" 或 "category"，请注意，所有这些概念都统一在 "monoid objects" 的保护伞下，因此 "associativity"而言，都是同一个idea，只是分门别类而已。)

Haskell：并行计算和 monad 的 'sequential property'

Haskell: parallel computation and the 'sequential property' of monads

monads

haskell

repa

问题