Length with foldl and foldr

Question

I have two functions computing the length of a list of integers

lengthFoldl :: [Int] -> Int
lengthFoldl xs = (foldl (\_ y -> y+1) 0 xs)

and

lengthFold :: [a] -> Int
lengthFold xs = foldr (\_ y -> y+1) 0 xs

they are the same except one uses foldr and one foldl.

But when trying to compute the length of any list [1 .. n] I get a wrong result (one too big) from lengthFoldl.

Answer 1

To complement joelfischerr's answer, I'd like to point out that a hint is given by the types of your functions.

lengthFoldl :: [Int] -> Int
lengthFold :: [a] -> Int

Why are they different? I guess you might had to change the first one to take an [Int] since with [a] it did not compile. This is however a big warning sign!

If it is indeed computing the length, why should lengthFoldl care about what is the type of the list elements? Why do we need the elements to be Ints? There is only one possible explanation for Int being needed: looking at the code

lengthFoldl xs = foldl (\_ y -> y+1) 0 xs

we can see that the only numeric variable here is y. If y is forced to be a number, and list elements are also forced to be numbers, it seems as if y is taken to be a list element!

And indeed that is the case: foldl passes to the function the accumulator first, the list element second, unlike foldr.

The general thumb rule is: when type and code do not agree, one should think carefully about which one is right. I'd say that most Haskellers would think that, in most cases, it is easier to get the type right than the code right. So, one should not just adapt the type to the code to force it to compile: a type error can instead witness a bug in the code.