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完成的，而不是由您自己进行的。它们应该在同一时间运行。