FoldLeft, FoldRight

The title should be inverted. Fold right is way more important and powerful than fold left. Both operators share the effect of taking a list and producing a result with a type possibly different from the values contained in the list. That’s to say that both folds are functions of type:

[α] -> β

The visual idea is to substitute the nodes of a tree (the list) with a function that operates on the pieces of tree hanging to each node. But this may be misleading: for example, most usages of fold left won’t produce a tree, but a scalar value. Moreover hinting at left-right simmetries is possibly the biggest red herring I’ve come across in my career; actually the differences in goals and applications between the two operators are …ehm …manifold.

Wikipedia has two pictures which are a nice decoration for this page but, apart from that, don’t tell the true heart of the story. Moreover, they mix up things using the same name for operands f and v, which (apart from being in both cases a function and a scalar(*)) have completely different natures, purposes and usages in fold left rather than fold right. That’s the main reason I decided to rename those operands in the case of fold left.

Left fold transformationFold left (aka reduce left) is the basic list iterator. Straight, efficient and dumb: once it starts it has to get to the end of the list. No way to talk to the driver during the trip. At each element, a given operation (expressed by the function s) gets performed and the result brought along in the next recursion. The operation happens inside the recursion call. This makes fold left suited for tail recursion optimisation done by the compiler, but that’s its only advantage.

The definition of fold left (shortly foldl) is:

foldl s a (x:xs) = foldl s (s a x) xs

I use the names s & a (rather than f & v) to make clear at any time that I am talking about fold left rather than fold fold right. Their presentation is in the specific fold left page.

Right fold transformation

Fold right (aka reduce right) is the basic list recursion operator. Way more intelligent than its cousin. It has a non-intuitive way to handle its own parameters, but the operation you entrust it with (represented by the function f) gets performed outside the recursion call, which is the general thing you expect a recursive function to do. This makes fold right extremely versatile(**). Unlike fold left (which has signed a suicidal pact to reach the end of the list or blow the stack in the effort) during the trip you may talk to the driver and tell it for example to fetch the result and get out of the recursion.

The definition of fold right (shortly fold, to express the fact that fold right is the fold) is:

fold f v (x:xs) = f x (fold f v xs)

I use the names f & v (rather than s & a) to make clear at any time that I am talking about fold right rather than fold left. Their presentation is in a specific fold right post.

The two short definitions in italic are taken from [1].

(*) That’s not entirely accurate: in the case of fold right, I’ve met cases where v is a function as well. I reckon the same could be done for fold left, but I haven’t any evidence to support this last claim.

(**) As a proof of that, you may implement fold left using fold right, but not the other way around.

[1] http://srfi.schemers.org/srfi-1/srfi-1.html#FoldUnfoldMap

Advertisements

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