为什么 Data.List.genericLength 实现为右折叠？

Question

截至base 4.12版本，genericLength 的实现方式如下：

genericLength           :: (Num i) => [a] -> i
{-# NOINLINE [1] genericLength #-}
genericLength []        =  0
genericLength (_:l)     =  1 + genericLength l

{-# RULES
  "genericLengthInt"     genericLength = (strictGenericLength :: [a] -> Int);
  "genericLengthInteger" genericLength = (strictGenericLength :: [a] -> Integer);
 #-}

strictGenericLength     :: (Num i) => [b] -> i
strictGenericLength l   =  gl l 0
                        where
                           gl [] a     = a
                           gl (_:xs) a = let a' = a + 1 in a' `seq` gl xs a'

这基本上是一个 foldr，除了对于 Int 和 Integer ，它执行的是 foldl'。

为什么不在所有情况下使用 foldl'？难道 foldr 会为长列表建立大量的thunk吗？

- Ziyang Liu

---

它本身并不会构建一个大的长列表，这取决于Num的实现。例如，可以以这样的方式实现(+)，使其有时只需要查看第一个元素，并且由于惰性，因此可以在评估整个列表之前终止。 - Willem Van Onsem

Answer 1

genericLength 的实现是基于 Peano 数的思想：

data Peano = Zero | Succ Peano

使用这种表示法的数字可以是非严格的，因此像 genericLength [1..] > 5 这样的操作会返回True而不是无法终止。

对于大多数其他合理的Num实现，genericLength 中的foldr确实会导致您提到的问题。

- amalloy