3

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.

förschter
  • 740
  • 1
  • 7
  • 24

2 Answers2

5

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.

chi
  • 111,837
  • 3
  • 133
  • 218
3

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'

AJF
  • 11,767
  • 2
  • 37
  • 64
förschter
  • 740
  • 1
  • 7
  • 24
  • 1
    for me, it's easier to handle these things mentally by *always* using `\acc a -> ...` with `foldl`, and `\a r -> ...` with `foldr`. BTW you almost always want to use `foldl'` (instead of `foldl`). – Will Ness Jun 22 '18 at 09:16
  • Why should I use foldl ? – förschter Jun 22 '18 at 09:17
  • 3
    `foldl'` (instead of `foldl`). it is stricter. your foldl won't actually compute the sums as it goes along the list, just store away the future additions. this leads to bloated memory and even stack overflows if the list was long enough, when those nested future additions must be retraced and actually calculated. I'll find the canonical link and add it here shortly. [here it is](https://stackoverflow.com/a/13052612/849891). – Will Ness Jun 22 '18 at 09:19