Why is Data.List.genericLength implemented as a right fold?

Question

genericLength is implemented, as of base 4.12, as:

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'

which is basically a foldr, except that for Int and Integer it performs a foldl' instead.

Why does it not use foldl' in all cases? Doesn't foldr build up large thunks for long lists?

Answer 1

genericLength is implemented with things like Peano numbers in mind:

data Peano = Zero | Succ Peano

Numbers using this representation can be non-strict, so an operation like genericLength [1..] > 5 returns True instead of failing to terminate.

For most other reasonable implementations of Num, the foldr in genericLength does indeed cause the problems you mention.