Haskell Length 函数实现

Question

我正在学习 Haskell 编程，并试图了解列表的工作原理，因此我尝试编写两个可能的length函数：

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

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

哪一个更好？

在我看来，myLength1它更容易理解，并且在列表上操作看起来很自然。

另一方面，myLength较短且不使用递归；这是否意味着myLength运行速度比 myLength1?

Answer 1

请记住以下“伪实现” foldr：

foldr :: function -> initializer -> [a] -> b
foldr _ i [] = i
foldr f i (x:xs) = x `f` (foldr f i xs)

现在我们有了您的代码

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

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

由于foldr本身也是递归的，因此您的 myLength1 和 myLength 几乎相同，但在第一种情况下，递归调用是由foldr 完成的，而不是由您自己显式完成的。他们应该大约在同一时间运行。