haskell - (>>=) 折叠时的惰性

Question

考虑 Haskell 中的以下 2 个表达式:

foldl' (>>=) Nothing (repeat (\y -> Just (y+1)))
foldM (\x y -> if x==0 then Nothing else Just (x+y)) (-10) (repeat 1)

第一个需要永远，因为它试图计算无限表达式

...(((Nothing >>= f) >>= f) >>=f)...

Haskell 只会尝试从里到外评估它。

然而，第二个表达式立即给出 Nothing 。我一直认为 FoldM 只是使用 (>>=) 进行折叠，但随后它会遇到同样的问题。所以它在这里做了一些更聪明的事情——一旦它遇到了Nothing，它就知道要停止。 FoldM 实际上是如何工作的？

Answer 1

foldM 无法使用 foldl 实现。它需要 foldr 的力量才能停止。在我们到达那里之前，这是一个没有任何花哨的版本。

foldM f b [] = return b
foldM f b (x : xs) = f b x >>= \q -> foldM f q xs

我们可以将其转换为使用 foldr 的版本。首先我们翻转一下:

foldM f b0 xs = foldM' xs b0 where
  foldM' [] b = return b
  foldM' (x : xs) b = f b x >>= foldM' xs

然后将最后一个参数移过去:

  foldM' [] = return
  foldM' (x : xs) = \b -> f b x >>= foldM' xs

然后识别 foldr 模式:

  foldM' = foldr go return where
    go x r = \b -> f b x >>= r

最后，我们可以内联 foldM' 并将 b 移回左侧:

foldM f b0 xs = foldr go return xs b0 where
  go x r b = f b x >>= r

同样的通用方法适用于您想要在右折叠内从左向右传递累加器的各种情况。您首先将累加器一直向右移动，这样您就可以使用 foldr 构建一个采用累加器的函数，而不是尝试直接构建最终结果。 Joachim Breitner 做了大量工作来为 GHC 7.10 创建 Call Arity 编译器分析，帮助 GHC 优化以这种方式编写的函数。这样做的主要原因是它允许他们参与 GHC 列表库的融合框架。