24

这里有一些值得深思的地方。

当我编写 monadic 代码时，monad 会对完成的操作进行排序。例如，如果我在 IO monad 中编写：

do a <- doSomething
   b <- doSomethingElse
   return (a + b)

我知道doSomething之前会被处决doSomethingElse。

现在，考虑类似 C 语言的等效代码：

return (doSomething() + doSomethingElse());

C 的语义实际上并没有指定这两个函数调用的评估顺序，因此编译器可以随意移动。

我的问题是这样的：我将如何在 Haskell 中编写单子代码，这也使这个评估顺序未定义？理想情况下，当我的编译器的优化器查看代码并开始移动时，我会获得一些好处。

以下是一些可能无法完成工作但具有正确“精神”的技术：

  • 以函数式编写代码，即编写plus doSomething doSomethingElse并让plus调度单子调用。缺点：您无法共享单子操作的结果，并且plus仍然决定何时评估事物。
  • 使用惰性 IO，即 ，unsafeInterleaveIO将调度推迟到评估惰性的需求。但是惰性与未定义顺序的严格不同：特别是我确实希望我的所有一元动作都能被执行。
  • 惰性 IO，结合立即对所有参数进行排序。特别是，seq不强加排序约束。

从这个意义上说，我想要一些比一元排序更灵活但不如完全惰性的东西。

4

3 回答 3

16

这个过度序列化单子代码的问题被称为“交换单子问题”。

可交换单子是动作顺序没有区别的单子（它们是可交换的），即在以下代码中：

do a <- f x
   b <- g y
   m a b

是相同的：

do b <- g y
   a <- f x
   m a b

有许多通勤的单子（例如Maybe，Random）。例如，如果 monad 是可交换的，那么在其中捕获的操作可以并行计算。它们非常有用！

然而，我们没有一个很好的 monad 的语法，尽管很多人都要求这样的东西——它仍然是一个开放的研究问题。

顺便说一句，应用函子确实给了我们重新排序计算的自由，但是，您必须放弃bind（作为例如liftM2show 的建议）的概念。

于 2011-05-05T17:09:27.487 回答
9

这是一个非常肮脏的黑客，但它似乎应该对我有用。

{-# OPTIONS_GHC -fglasgow-exts #-}
{-# LANGUAGE MagicHash #-}
module Unorder where
import GHC.Types

unorder :: IO a -> IO b -> IO (a, b)
unorder (IO f) (IO g) = IO $ \rw# ->
           let (# _, x #) = f rw#
               (# _, y #) = g rw#
           in (# rw# , (x,y) #)

由于这将非确定性置于编译器手中，因此它在控制流问题（即异常）方面也应该表现得“正确”（即非确定性）。

另一方面，我们无法使用大多数标准单子的相同技巧，例如Stateand Either a因为我们确实依赖于通过弄乱RealWorld令牌获得的远处的幽灵行动。为了获得正确的行为，我们需要一些可用于优化器的注释，表明我们可以在两个非等效替代方案之间进行非确定性选择。

于 2011-05-05T17:22:49.667 回答
3

C 的语义实际上并没有指定这两个函数调用的评估顺序，因此编译器可以随意移动。

但是，如果doSomething()导致会改变行为的副作用doSomethingElse()怎么办？您真的希望编译器弄乱顺序吗？（提示：否）您完全处于 monad 中的事实表明情况可能如此。你的注释“你失去了对结果的分享”也表明了这一点。

但是，请注意，monadic 并不总是意味着已排序。这与您所描述的不完全一样，但您可能对Par monad感兴趣，它允许您并行运行您的操作。

您有兴趣保留未定义的顺序，以便编译器可以神奇地为您优化它。也许您应该使用类似 Par monad 的东西来指示依赖关系（有些事情不可避免地必须在其他事情之前发生），然后让其余的事情并行运行。

旁注：不要将 Haskellreturn与 C混淆return

于 2011-05-05T15:05:46.843 回答