Haskell 列表上的递归如何工作

Question

我正在学习 Haskell，有人可以解释一下，为什么这个功能有效吗？ 我的意思是，感应案例如何不会永远运行？ 这里的停止条件是什么？

    myLength :: [a] -> Integer
    myLength []     = 0
    myLength (x:xs) = (+1) (myLength xs)

Answer 1

停止条件是列表用完，所以[]模式。在这种情况下，Haskell 将返回一个 0。

在递归的情况下，我们因此匹配任何非空列表(x:xs)，其中x是第一个元素，和 xs tail(剩余元素的列表)。在这种情况下，我们因此返回 1 + myLength xs，所以我们在尾部递归。

这意味着对于每一个有限列表，我们最终都会以[]为参数进行递归调用，从而返回0。

因此，Python 中的等效算法如下所示:

def myLength(items):
    if <strong>len(items)</strong>:
        return myLength(<strong>items[1:]</strong>) + 1
    else:
        return 0

这里计算尾部需要 O(n)，而在 Haskell 中需要 O(1)。