Folding in Haskell

Trying to learn Haskell, round 2.  The first time around, I had a lot of difficulty understanding the difference between the three different types of folds.  This time, for some reason, it’s a lot clearer.

  • foldl is left associative
  • foldr is right associative
  • foldl’ is left associative, but calculates the value of a thunk immediately instead of pushing it onto the stack.

This link was particularly helpful in understanding the difference between the three.

Understanding the difference in implementation between the three folds is good, but in daily usage, it’s much more useful to know when to use them. Shamelessly copied from this link, but properly attributed, the general rule of thumb is here:

  • foldr – Partial results, infinite lists, lazy operators
  • foldl’ – Finite lists with strict operators
  • foldl – Otherwise (like reverse)

Anything with partial results, infinite lists or lazy operators should be done with foldr, because recursive calls are on the tail of the list and you can get the initial values by lazily evaluating only part of the list with foldr.

foldl’ is used for finite lists with strict operators because it is tail-call optimized and doesn’t create large thunks.

foldl is used much less, for other functions like ‘reverse’.

Advertisements

3 thoughts on “Folding in Haskell

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s