放松monadic计算中的排序约束

Question

这里有一些值得思考的东西.

当我编写monadic代码时,monad会对完成的操作进行排序.例如,如果我写入IO monad:

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

我知道doSomething以前会被执行doSomethingElse.

现在,考虑像C这样的语言中的等效代码:

return (doSomething() + doSomethingElse());

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

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

以下是一些可能无法完成工作的技术,但却是正确的"精神":

• 以functorial风格编写代码,即编写plus doSomething doSomethingElse并plus调度monadic调用.缺点:你失去了对monadic动作结果的分享,并且plus仍然决定什么时候最终会被评估.
• 使用惰性IO,即将unsafeInterleaveIO调度推迟到评估的懒惰需求.但懒惰不同于严格的未定义顺序:特别是我确实希望我的所有monadic动作都被执行.
• 懒惰的IO,加上立即seq'ing所有的参数.特别是,seq不强加排序约束.

从这个意义上讲,我想要一些比一元顺序更灵活的东西,但是比完全懒惰更不灵活.

Answer 1

这种过度序列化monad代码的问题被称为"可交换monad问题".

交换monad是monad,其行为顺序没有区别(他们通勤),即遵循以下代码:

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的建议)的概念.

Answer 2

这是一个深刻的肮脏的黑客,但它似乎应该对我做的伎俩.

{-# 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) #)

由于这会将非确定性置于编译器的手中,因此它也应该在控制流问题(即异常)方面表现得"正确"(即非确定性).

另一方面,我们不能像大多数标准单子那样拉扯相同的技巧State, Either a因为我们真的依靠通过弄乱RealWorld令牌而在远处可用的怪异动作.为了获得正确的行为,我们需要一些优化器可用的注释,表明我们可以选择两个非等价的替代方案之间的非确定性选择.