折叠中的懒惰(>> =)

Question

考虑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只会尝试从内到外进行评估.

然而,第二个表达式立即给出了Nothing.我一直认为foldM只是使用(>> =)进行折叠,但是它会遇到同样的问题.所以它在这里做了一些更聪明的事情 - 一旦它命中了它就知道停止了.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列表库的融合框架.