Haskell:并行计算和monads的 '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上的 this answer指出:

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[.]

问题

具有此“顺序属性”到底是什么意思？

monad如何执行此操作？

对于computeP的示例:使用哪个monad不受限制，因此我可以使用身份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的类型有助于确保并行计算彼此之间按顺序进行，但绝不能气密。它仅仅是“尽力而为”的抽象。

How does a monad enforce this?

实际上， computeP仅应与绑定(bind) (>>=)的第一个参数严格的monad一起使用，因此在 u >>= k中，仅在对 k求值之后，才会应用 u函数。然后，如果您将 computeP与此类monad一起使用，

do w <- computeP v
   k w

确保将矢量 w传递给 k之前已对其进行了评估，这可以安全地执行其他 computeP操作。

严格monad的示例: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?

那些报价是手工的。如我所见，“顺序”和“单子(monad)”之间的关系是双重的。

首先，对于Haskell中的许多monad而言， (>>=)的定义自然会规定求值顺序，通常是因为它立即在第一个参数上进行模式匹配。如前所述，这是Repa用来强制按顺序执行 computeP计算的原因(这就是为什么如果将其专门用于 Identity，它会中断的原因；这不是严格的monad)。在总体方案中，这是惰性评估的一个相当小的细节，而不是通常适合于单子(monad)的任何事物。

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

关键不是单子(monad)具有固有的顺序方面，而在于单子(monad)组合本质上是单子(monad)的:如果您尝试列出可从名称“单子(monad)组合”中期望的常规属性，则可能会结束与一起被称为“monad”的属性；这是Moggi的开创性论文“计算和单子(monad)的概念”的要点之一。

“单子(monad)”不是一个神奇的概念，它具有极大的通用性，因此很多东西碰巧是单子(monad)。毕竟，主要的要求是要有一个关联的操作。对于顺序合成，这是一个非常合理的假设。 (如果在听到“关联性”时认为“monoid”或“category”，请注意，所有这些概念都是在“monoid对象”的保护下统一的，因此就“associtivity”而言，它们是所有相同的想法，只是在不同的类别中。)