3

Can anybody explain how foldl works?
I understood that, for example, foldr (-) 0 [1,2,3] produces (1 - (2 - (3 - 0))), whereas foldl (-) 0 [1,2,3] produces (((0 - 1) - 2) - 3), but I have still some questions:

  • 1st example (length of a list with foldr/foldl):
    foldr (\_ acc -> acc + 1) 0 [1,2,3,4,5] produces 5, as expected.
    foldl (\_ acc -> acc + 1) 0 [1,2,3,4,5] produces 6. :|
    foldl (\_ acc -> acc + 1) 0 [2] produces 3. :|
    How does foldl react to these given examples?

  • 2nd example:
    foldr (:) [] [1,2,3,4] produces [1,2,3,4] - no worry, but foldl (:) [] [1,2,3,4] gives me an error: Occurs check: cannot construct the infinite type: a ~ [a]
    What is wrong with foldl?

laurentiupiciu
  • 43
  • 5
  • 8
    For `foldl` you need to switch the argument order between `acc` and `_`, because `foldr` logically puts the initial argument on the end of the sequence, while `foldl` puts it logically at the start. That means that the accumulator is the first (!) argument to the folding function for `foldl` (and the second argument for `foldr`). Because of this mistake, your accumulator 'starts' at `1` for `foldl` rather than `0`. If you change the list to `["a", "b", "c", "d", "e"]` for instance, then you'll get a nice type-check error on the `foldl` sample. – MicroVirus Jun 06 '16 at 13:51
  • 3
    If you try `foldl (\_ acc -> acc + 1) 0 [0,0,0,0]` then maybe you will see your error. – pdexter Jun 06 '16 at 13:53
  • Thank you, @MicroVirus ! – laurentiupiciu Jun 06 '16 at 13:55
  • Yes, I've seen it, @pdexter – laurentiupiciu Jun 06 '16 at 13:56
  • 1
    @MicroVirus You should consider making that comment into an answer! – jkeuhlen Jun 06 '16 at 14:19
  • @MicroVirus, it's not because the accumulator starts at 1, it's that the fold just returns the last element of the list plus 1. – pdexter Jun 06 '16 at 14:56
  • 1
    @pdexter Yeah, that was maybe a bit confusing wording on my part, but I meant the 'element' `1`. I cramped it all in one comment, so it's not a complete answer. Feel free to write up a complete answer; that goes for everyone. – MicroVirus Jun 06 '16 at 14:57

1 Answers1

4

In foldr, the accumulator is the second argument of the function you're folding with, but in foldl, the accumulator is the first argument. If you look carefully at the question's introductory paragraph, you can work this out for yourself...

The "1st example" code is misleading because the acc argument (whose name suggests that it should be an accumulator) is consistently the second argument to the lambda, when it should be first for foldl. It is additionally confusing because the type and values of the sample list elements mirror the type and value of the accumulator value... as the comments mention, it would have been better to use other values, and better yet to use some other type!

For the "2nd example", you get a type error because your arguments are swapped (and you can't have a list whose elements are lists of itself). Either swap the argument order by hand:

foldl (\xs x -> x:xs)

or else use flip, the library function designed for this:

foldl (flip (:))

Note that the result for the foldl case should be a reversed list (not a copied one), because foldl iterates in the opposite direction from foldr.

comingstorm
  • 25,557
  • 3
  • 43
  • 67