在什么情况下是单次计算尾递归？ [英] Under what circumstances are monadic computations tail-recursive?

问题描述

在Haskell Wiki的单向递归中，有一个例子声称是tail-recursive ：

  f 0 acc = return （反向acc）
fn acc = do 
v < -  getLine 
f（n-1）（v：acc）
  

尽管命令符号使我们相信它是尾递归的，但它根本不是那么明显（至少对我而言）。如果我们脱糖 do 我们得到

  f 0 acc = return （反向acc）
fn acc = getLine>> = \ v  - > f（n-1）（v：acc）
  

并重写第二行导致

  fn acc =（>> =）getLine（\v-> f（n-1）（v：acc） ）
  

所以我们看到 f 出现在里面第二个参数是>> = ，而不是尾递归位置。我们需要检查 IO 的>> = 来得到答案。
显然将递归调用作为 do 块中的最后一行不是一个足够的条件，函数是尾递归的。

---

假设一个 monad是尾递归的 iff每个递归函数在这个monad定义为

  f = do 
 ... 
f ... 
  

或等价地

  f。 .. =（...）>> = \ x  - > f ... 
  

是尾递归的。我的问题是：
$ b $ ol

什么monad是尾递归的？

是否有一些通用规则我们可以用它来立即区分尾递归monads？



$ b

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

  f 0 acc = acc 
fn acc = do 
r < -  acc 
f（n  -  1）（map（r +）acc）
  

必须是尾巴-recursive。但是，第二行的解除导致：

  f n acc = acc>> = \ r  - > f（n-1）（map（r +）acc）
 =（flip concatMap）acc（\ r→f（n-1）（map（r +）acc））
  

很显然，这不是尾递归，恕我直言不能做。原因是递归调用不是计算的结束。它会执行多次，并将结果合并在一起以产生最终结果。

解决方案

引用自身的monadic计算永远不会尾递归。但是，在Haskell中，你有懒惰和核心引用，这才是重要的。让我们用这个简单的例子：

  forever ::（Monad m）=> m a  - > m b 
 forever c'= let c = c'>> c in c 
  

如果且仅当（ >>）在其第二个参数中是非严格的。这与列表和 repeat 非常相似：

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

由于<在它的第二个参数中，code>（：）构造函数是非严格的，因为你有一个有限的弱头标准形式（WHNF），所以这个列表可以被遍历。只要消费者（例如列表折叠）只需要WHNF就可以工作并且在恒定空间中运行。

消费者在 forever 是任何解释单子计算的东西。如果monad是 [] ，那么（>>）在其第二个参数中是非严格的，它的第一个参数是空的列表。因此 forever [] 将导致 [] ，而 forever [1] 会分歧。在 IO monad的情况下，解释器本身就是运行时系统，在那里你可以想到（>>）在第二个参数中总是非严格的。

In Haskell Wiki's Recursion in a monad there is an example that is claimed to be tail-recursive:

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

While the imperative notation leads us to believe that it is tail-recursive, it's not so obvious at all (at least to me). If we de-sugar do we get

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

and rewriting the second line leads to

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

So we see that f occurs inside the second argument of >>=, not in a tail-recursive position. We'd need to examine IO's >>= to get an answer. Clearly having the recursive call as the last line in a do block isn't a sufficient condition a function to be tail-recursive.

---

Let's say that a monad is tail-recursive iff every recursive function in this monad defined as

f = do
    ...
    f ...

or equivalently

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

is tail-recursive. My question is:

1. What monads are tail-recursive?
2. Is there some general rule that we can use to immediately distinguish tail-recursive monads?

---

Update: Let me make a specific counter-example: The [] monad is not tail-recursive according to the above definition. If it were, then

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

would have to be tail-recursive. However, desugaring the second line leads to

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

Clearly, this isn't tail-recursive, and IMHO cannot be made. The reason is that the recursive call isn't the end of the computation. It is performed several times and the results are combined to make the final result.

解决方案

A monadic computation that refers to itself is never tail-recursive. However, in Haskell you have laziness and corecursion, and that is what counts. Let's use this simple example:

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

Such a computation runs in constant space if and only if (>>) is nonstrict in its second argument. This is really very similar to lists and repeat:

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

Since the (:) constructor is nonstrict in its second argument this works and the list can be traversed, because you have a finite weak-head normal form (WHNF). As long as the consumer (for example a list fold) only ever asks for the WHNF this works and runs in constant space.

The consumer in the case of forever is whatever interprets the monadic computation. If the monad is [], then (>>) is non-strict in its second argument, when its first argument is the empty list. So forever [] will result in [], while forever [1] will diverge. In the case of the IO monad the interpreter is the very run-time system itself, and there you can think of (>>) being always non-strict in its second argument.

这篇关于在什么情况下是单次计算尾递归？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！