28

在 Haskell Wiki 的Recursion in a 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. 哪些单子是尾递归的？
  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))

显然，这不是尾递归，恕我直言。原因是递归调用不是计算的结束。它执行多次，并将结果组合起来以形成最终结果。

4

2 回答 2

24

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

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是解释一元计算的任何东西。如果 monad 是[]，那么(>>)当它的第一个参数是空列表时，它的第二个参数是非严格的。所以forever []会导致[]，而forever [1]会发散。在IOmonad 的情况下，解释器本身就是运行时系统，在那里你可以认为(>>)它的第二个参数总是非严格的。

于 2012-11-14T17:46:10.583 回答
5

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

将(getLine >>=)被执行并消失，我们再次调用f. 重要的是，这发生在一定数量的步骤中 - 没有 thunk 积聚。

你的第二个例子，

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

n在其 thunk 构建中将仅是线性的 (in )，因为从左侧访问结果列表（再次由于惰性，因为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- 表示法，

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

因为信息依赖有额外的强迫。同样，如果给定 monad 的绑定是严格操作。

于 2012-11-14T14:11:19.033 回答