在什么情况下monadic计算尾递归？

Question

在Haskell Wiki的monad中的递归中有一个声称是尾递归的例子:

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块中的最后一行是一个尾递归函数的充分条件.

---

假设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

引用自身的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

由于(:)构造函数在其第二个参数中是非限制的,因此可以遍历列表,因为您具有有限的弱头正规形式(WHNF).只要消费者(例如列表折叠)只询问WHNF,它就可以工作并在恒定的空间中运行.

在这种情况下,消费者forever可以解释monadic计算.如果monad是[],那么(>>)当它的第一个参数是空列表时,它的第二个参数是非严格的.所以forever []会导致[],同时forever [1]会分歧.在IOmonad 的情况下,解释器本身就是运行时系统,在那里你可以想到(>>)它的第二个参数总是非严格的.

Answer 2

真正重要的是恒定的堆栈空间。由于懒惰，第一个示例是尾递归模态cons。

该(getLine >>=)被执行，会蒸发掉，再留给我们的呼吁f。重要的是，这发生在恒定数量的步骤中-没有大量的堆积。

您的第二个例子

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

n在结果块列表中，它将仅是线性的（in ），因为结果列表是从左侧访问的（同样由于懒惰，concat也是非严格的）。如果在头部消耗掉它，则可以在O（1）空间中运行（不算f(0), f(1), ..., f(n-1)左边缘的线性空间thunk ）。

更糟糕的是

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

因为由于信息依赖性而产生了额外的强迫。同样，如果给定单子的绑定是严格操作。