CODEWITHSUNDEEP
haskellfold
förschter
förschter

Reputation: 860

Length with foldl and foldr

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.

Upvotes: 3

Views: 2099

Answers (2)

chi
chi

Reputation: 116174

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.

Upvotes: 5

förschter
förschter

Reputation: 860

Looking at the type definitions of foldl and foldr it becomes clear what the issue is.

:t foldr
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b

and 

:t foldl
foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b

One can see that the foldr takes the item of the list and the second argument into the function and foldl takes the second argument and the item of the list into the function.

Changing lengthFoldl to this solves the problem

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

Edit: Using foldl instead of foldl' is a bad idea: https://wiki.haskell.org/Foldr_Foldl_Foldl'

Upvotes: 3

Related Questions