haskell - 在什么情况下单子(monad)计算是尾递归的？

Question

在 Haskell Wiki 的 Recursion in a monad 中有一个例子，据称是 tail-recursive :

f 0 acc = return (reverse acc)
f n acc = do
    v  <- getLine
    f (n-1) (v : acc)

虽然命令式符号让我们相信它是尾递归的，但它根本不那么明显(至少对我来说)。如果我们去糖do我们会得到

f 0 acc = return (reverse acc)
f n acc = getLine >>= \v -> f (n-1) (v : acc)

重写第二行导致

f n acc = (>>=) getLine (\v -> f (n-1) (v : acc))

因此我们看到 f 出现在 >>= 的第二个参数内，而不是在尾递归位置。我们需要检查 IO 的 >>= 才能得到答案。显然，将递归调用作为 do block 中的最后一行并不是函数成为尾递归的充分条件。

<小时/>

假设一个 monad 是尾递归的，当且仅当此 monad 中的每个递归函数定义为

f = do
    ...
    f ...

或者同等的

f ...  =  (...) >>= \x -> f ...

是尾递归的。我的问题是:

1. 哪些 monad 是尾递归的？
2. 是否有一些通用规则可以用来立即区分尾递归 monad？

<小时/>

更新:让我举一个具体的反例:根据上面的定义，[] monad 不是尾递归的。如果是的话，那么

f 0 acc = acc
f n acc = do
    r <- acc
    f (n - 1) (map (r +) acc)

必须是尾递归的。然而，对第二行进行脱糖会导致

f n acc = acc >>= \r -> f (n - 1) (map (r +) acc)
        = (flip concatMap) acc (\r -> f (n - 1) (map (r +) acc))

显然，这不是尾递归，恕我直言，这是无法实现的。原因是递归调用并不是计算的结束。执行多次并将结果组合起来得到最终结果。

Answer 1

引用自身的一元计算永远不会是尾递归的。然而，在 Haskell 中，你有惰性和核心递归，这才是最重要的。让我们使用这个简单的例子:

forever :: (Monad m) => m a -> m b
forever c' = let c = c' >> c in c

当且仅当 (>>) 的第二个参数是非严格的时，这样的计算才会在常量空间中运行。这确实与列表和重复非常相似:

repeat :: a -> [a]
repeat x = let xs = x : xs in xs

由于 (:) 构造函数的第二个参数是非严格的，因此它可以工作并且可以遍历列表，因为您有一个有限的弱头范式 (WHNF)。只要消费者(例如列表折叠)只请求 WHNF，它就可以在恒定空间中运行并运行。

在永远的情况下，消费者是解释单子(monad)计算的任何东西。如果 monad 是 []，则当第一个参数是空列表时，(>>) 的第二个参数是非严格的。因此，forever [] 将导致 []，而 forever [1] 将会发散。对于 IO monad 来说，解释器就是运行时系统本身，您可以认为 (>>) 在其第二个部分中始终是非严格的论证。