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

考虑Haskell中的以下两个表达式：

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只会尝试从内到外对其进行评估。

但是，第二个表达式不能立即给出任何内容。我一直认为foldM只是使用（>> =）进行折叠，但随后会遇到相同的问题。因此，它在这里做的事情更聪明-一旦成功，它就会停止。 foldM实际上如何工作？

最佳答案

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列表库的融合框架。