search

Introducing Folds

Threading state through a recursive data structure

This post is the third in a series.

In the first post, I introduced "catamorphisms", a way of creating functions for recursive types, and in the second post, we created a few catamorphism implementations.

But at the end of the previous post, I noted that all the catamorphism implementations so far have had a potentially serious flaw.

In this post, we'll look at the flaw and how to work around it, and in the process look at folds, tail-recursion and the difference between "left fold" and "right fold".

hashtag
Series contents

Here's the contents of this series:

hashtag
A flaw in our catamorphism implementation

Before we look at the flaw, let's first review the recursive type Gift and the associated catamorphism cataGift that we created for it.

Here's the domain:

Here are some example values that we'll be using in this post:

Here's the catamorphism:

and here is a totalCostUsingCata function built using cataGift:

hashtag
What's the flaw?

So what is wrong with this implementation? Let's stress test it and find out!

What we'll do is create a Box inside a Box inside a Box a very large number of times, and see what happens.

Here's a little helper function to create nested boxes:

Let's try it to make sure it works:

Now try running totalCostUsingCata with these deeply nested boxes:

So far so good.

But if we use much larger numbers, we soon run into a stack overflow exception:

The exact number which causes an error depends on the environment, available memory, and so on. But it is a certainty that you will run into it when you start using largish numbers.

Why is this happening?

hashtag
The problem with deep recursion

Recall that the definition of the cost for the Boxed case (fBox) was innerCost + 1.0m. And what is the inner cost? That's another box too, so we end up with a chain of calculations looking like this:

In other words, innerCost1000 has to be calculated before innerCost999 can be calculated, and 999 other inner costs have to be calculated before the top level innerCost can be calculated.

Every level is waiting for its inner cost to be calculated before doing the calculation for that level.

All these unfinished calculations are stacked up waiting for the inner one to complete. And when you have too many? Boom! Stack overflow!

hashtag
The solution to stack overflows

The solution to this problem is simple. Rather than each level waiting for the inner cost to be calculated, each level calculates the cost so far, using an accumulator, and passes that down to the next inner level. When we get to the bottom level, we have the final answer.

The big advantange of this approach is that all calculations at a particular level are completely finished before the next lowel level is called. Which means that the level and its associated data can be safely discarded from the stack. Which means no stack overflow!

An implementation like this, where the higher levels can be safely discarded, is called tail recursive.

hashtag
Reimplementating the totalCost function with an accumulator

Let's rewrite the total cost function from scratch, using an accumulator called costSoFar:

A few things to note:

  • The new version of the function has an extra parameter (costSoFar). We will have to provide an initial value for this (such as zero) when we call it at the top level.

  • The non-recursive cases (Book and Chocolate) are the end points. The take the cost so far and add it to their price, and then that is the final result.

  • The recursive cases calculate a new costSoFar based on the parameter that is passed in. The new costSoFar is then passed down to the next lower level,

    just as in the example above.

Let's stress test this version:

Excellent. Up to one million nested levels without a hiccup.

hashtag
Introducing "fold"

Now let's apply the same design principle to the catamorphism implementation.

We'll create a new function foldGift. We'll introduce an accumulator acc that we will thread through each level, and the non-recursive cases will return the final accumulator.

If we look at the type signature, we can see that it is subtly different. The type of the accumulator 'a is being used everywhere now. The only time where the final return type is used is in the two non-recursive cases (fBook and fChocolate).

Let's look at this more closely, and compare the signatures of the original catamorphism from the last post with the signatures of the new fold function.

First of all, the non-recursive cases:

As you can see, with "fold", the non-recursive cases take an extra parameter (the accumulator) and return the 'r type.

This is a very important point: the type of the accumulator does not need to be the same as the return type. We will need to take advantage of this shortly.

What about the recursive cases? How did their signature change?

For the recursive cases, the structure is identical but all use of the 'r type has been replaced with the 'a type. The recursive cases do not use the 'r type at all.

hashtag
Reimplementating the totalCost function using fold

Once again, we can reimplement the total cost function, but this time using the foldGift function:

And again, we can process very large numbers of nested boxes without a stack overflow:

hashtag
Problems with fold

So using fold solves all our problems, right?

Unfortunately, no.

Yes, there are no more stack overflows, but we have another problem now.

hashtag
Reimplementation of the description function

To see what the problem is, let's revisit the description function that we created in the first post.

The original one was not tail-recursive, so let's make it safer and reimplement it using foldGift.

Let's see what the output is:

These outputs are wrong! The order of the decorations has been mixed up.

It's supposed to be a wrapped book with a card, not a book and a card wrapped together. And it's supposed to be chocolate in a box, then wrapped, not wrapped chocolate in a box!

What has gone wrong?

The answer is that the correct description for each layer depends on the description of the layer below. We can't "pre-calculate" the description for a layer and pass it down to the next layer using a descriptionSoFar accumulator.

But now we have a dilemma: a layer depends on information from the layer below, but we want to avoid a stack overflow.

hashtag
Using functions as accumulators

Remember that the accumulator type does not have to be the same as the return type. We can use anything as an accumulator, even a function!

So what we'll do is, rather than passing a descriptionSoFar as the accumulator, we'll pass a function (descriptionGenerator say) that will build the appropriate description given the value of the next layer down.

Here's the implementation for the non-recursive cases:

The implementation for recursive cases is a bit more complicated:

  • We are given an accumulator (descriptionGenerator) as a parameter.

  • We need to create a new accumulator (a new descriptionGenerator) to pass down to the next lower layer.

  • The input to the description generator will be all the data accumulated from the lower layers.

    We manipulate that to make a new description and then call the descriptionGenerator passed in from the higher layer.

It's more complicated to talk about than to demonstrate, so here are implementations for two of the cases:

We can simplify that code a little by using a lambda directly:

We could continue to make it more compact using piping and other things, but I think that what we have here is a good balance between conciseness and obscurity.

Here is the entire function:

Again, I'm using overly descriptive intermediate values to make it clear what is going on.

If we try descriptionUsingFoldWithGenerator now, we get the correct answers again:

hashtag
Introducing "foldback"

Now that we understand what to do, let's make a generic version that that handles the generator function logic for us. This one we will call "foldback":

By the way, I'm going to use term "generator" here. In other places, it is commonly referred to as a "continuation" function, often abbreviated to just "k".

Here's the implementation:

You can see that it is just like the descriptionUsingFoldWithGenerator implementation, except that we are using generic newInnerVal and generator values.

The type signatures are similar to the original catamorphism, except that every case works with 'a only now. The only time 'r is used is in the generator function itself!

The foldback implementation above is written from scratch. If you want a fun exercise, see if you can write foldback in terms of fold.

Let's rewrite the description function using foldback:

And the results are still correct:

hashtag
Comparing foldback to the original catamorphism

The implementation of descriptionUsingFoldBack is almost identical to the version in the last post that used the original catamorphism cataGift.

Here's the version using cataGift:

And here's the version using foldbackGift:

All the handler functions are basically identical. The only change is the addition of an initial generator function, which is just id in this case.

However, although the code looks the same in both cases, they differ in their recursion safety. The foldbackGift version is still tail recursive, and can handle very large nesting depths, unlike the cataGift version.

But this implementation is not perfect either. The chain of nested functions can get very slow and generate a lot of garbage, and for this particular example, there is an even faster way, which we'll look at in the next post.

hashtag
Changing the type signature of foldback to avoid a mixup

In foldGift the signature for fWrapped is:

But in foldbackGift the signature for fWrapped is:

Can you spot the difference? No, me neither.

The two functions are very similar, yet work very differently. In the foldGift version, the first parameter is the accumulator from the outer levels, while in foldbackGift version, the first parameter is the accumulator from the inner levels. Quite an important distinction!

It is therefore common to change the signature of the foldBack version so that the accumulator always comes last, while in the normal fold function, the accumulator always comes first.

This change shows up in the type signature. The Gift value comes before the accumulator now:

and now we can tell the two versions apart easily.

hashtag
Rules for creating a fold

To finish up this post, let's summarize the rules for creating a fold.

In the first post we saw that creating a catamorphism is a mechanical process that follows rules. The same is true for creating a iterative top-down fold. The process is:

  • Create a function parameter to handle each case in the structure.

  • Add an additional parameter as an accumulator.

  • For non-recursive cases, pass the function parameter the accumulator plus all the data associated with that case.

  • For recursive cases, perform two steps:

    • First, pass the handler the accumulator plus all the data associated with that case (except the inner recursive data). The result is a new accumulator value.

    • Then, call the fold recursively on the nested value using the new accumulator value.

Note that each handler only "sees" (a) the data for that case, and (b) the accumulator passed to it from the outer level. It does not have access to the results from the inner levels.

hashtag
Summary

We've seen in this post how to define a tail-recursive implementation of a catamorphism, called "fold" and the reverse version "foldback".

In the next post we'll step back a bit and spend some time understanding what "fold" really means, and at some guidelines for choosing between fold, foldback and cata.

We'll then see if we can apply these rules to another domain.

The source code for this post is available at this gistarrow-up-right.

PreviousCatamorphism examplesNextUnderstanding Folds

Last updated

Was this helpful?