在什么情况下是一元计算尾递归？

Question

在Haskell的单次递推中，有一个被称为尾递归的例子

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的>>=才能得到答案。显然，在块中将递归调用作为最后一行的不是一个足够的条件，一个函数是尾递归的。。

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

f = do
    ...
    f ...

或等量

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

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

1. 什么单子是尾递归的？
2. 有什么一般的规则，我们可以用来立即区分尾递归单子吗？

更新：，让我做一个具体的反例:根据上面的定义，[] 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))

显然，这不是尾递归的，IMHO也无法实现。原因是递归调用不是计算的结束。它被执行了几次，并将结果结合在一起得出最终的结果。

Answer 1

引用自身的一元计算绝不是尾递归的.然而，在Haskell，你有懒惰和共递归，这才是最重要的。让我们使用这个简单的例子：

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

这样的计算在常数空间中运行当且仅当(>>)在其第二个参数中是非严格的。这非常类似于lists和repeat

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

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

在forever的情况下，使用者是任何解释一元计算的人。如果monad是[]，那么(>>)在其第二个参数中是非严格的，而它的第一个参数是空列表。因此，forever []将导致[]，而forever [1]将产生分歧。对于IO monad，解释器本身就是运行时系统，在第二个参数中，您可以认为(>>)总是不严格的。

Answer 2

真正重要的是恒定的堆栈空间。您的第一个例子是尾递归模子，这要感谢您的懒惰。

(getLine >>=)将被执行并消失，使我们再次调用f。重要的是，这种情况发生在一定数量的步骤中

你的第二个例子，

f 0 acc = acc
f n acc = concat [ f (n - 1) $ map (r +) acc | r <- acc]

因为结果列表是从左边访问的(同样是由于懒惰，因为concat是非严格的)，所以在它的堆中只会是线性的(在concat中)。如果它在头部被消耗，它可以在O(1)空间中运行(不包括线性空间thunk，左侧边缘的f(0), f(1), ..., f(n-1) )。

更糟的是

f n acc = concat [ f (n-1) $ map (r +) $ f (n-1) acc | r <- acc]

或者在do-notation

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

因为有额外的强制由于信息依赖。同样，如果对给定的单子绑定是一个严格的操作。