RecursionAndState.md

The thing that students have the hardest time on when learning functional programming is how to process a recursive structure while maintaining some sort of "state", the result if you will. I'll attempt here to demystify the process.

Functional programming languages almost always use a lot of recursively defined structures. Depending on the language those can be implemented in various ways, but in any case the end result is the same. A structure of this type is either an "atom", i.e. an irreducible thing, or a "compound" consisting of substructures of the same form.

For example a "list" is either an Empty/Nil list (the "atom") or it is formed as a Cons of a value and another list (compound form). That other "sublist" can itself be empty or another cons and so on and so forth. A tree is similar. It is either empty, or it consists of a triple of a value and two sub-trees, left and right.

Almost every problem we encounter is a question about doing something with all entries in a structure. To solve these problems, there are two ways to analyze your problem. One leads to "normal" recursion, the other leads to tail recursion. But they both have one thing in common:

• They do a certain thing on an "atom"
• For a compound structure they find how to relate the answer to the question for the overall structure to the answers for its substructures.

Way 1

Let us examine the one way first. As an example, we will imagine we have a tree of numbers, and our goal is simply to add all those numbers.

You basically ask yourself two questions:

1. If I knew the answer for all the substructures of a compound structure, how do I find the answer for the overall structure?
2. If I had to answer the question for an "atom" structure, what would the answer be? This one can get tricky some times.

Let's start with the first question for our problem. Our compound tree structure has an elem, a left subtree and a right subtree. So we would ask ourselves: If we new the sum of the values in the left subtree, and the sum of the values in the right subtree, how do we find the sum of all the values? Yes I know it's easy in this case, but it is this question you need to answer on each problem.

Of course the answer in this case would be that we would take elem + sum(left) + sum(right). This is the part that makes the thing recursive: We are calling our function on each of the substructures, get their answers, then combine them in some way. Simple, right?

Now we have to worry about what happens when the process "terminates". That happens at the "atoms". So what should the sum of the numbers in an empty tree be? In order to answer that question, you should keep in mind this: that this atom is one of the possible substructures on the recursive step above. So it should return an answer that makes sense in that context. So what should we have in the above formula in place of sum(left) if there are in fact no numbers on the left side? We would essentially like for that term to not be there at all, so we would like it to equal 0. Therefore that's what calling our function on the empty set should return.

So how will evaluation proceed in such a case? It's going to start at the root of the tree. It is going to go down the left side first, and keep going left, trying to compute the sum(left) part. Each of those requires calling sum on its left and so on, and the only reason this process will terminate is that eventually you end up computing the sum of an empty list. That one returns its result, and so the previous step in the process can proceed to compute sum(right). Eventually that one will terminate as well, this would allow that previous step to return a value to its caller, who will then proceed to look at its right subtree and so on and so forth until every little bit of the tree has been visited and accounted for.

You are probably somewhat familiar with the above, so I will proceed to the second way of dealing with such problems. This way is important because it is essentially the model for maintaining state information without using mutable variables.

Way 2

The key idea is this: Our function takes an extra parameter, representing the "state", but most typically called an "accumulator". If you think about it the job of an accumulator is to say: "ok this is my value now, and you want me to somehow include into it this new value, so now here's my new value". This is exactly what "state" means: Given a previous state and a new value to deal with, you proceed to a new state.

So in this new framework, the function signature would look something like func(structure, state) where the type of state is basically the return type of our function, in this case probably integer. We again ask two questions, like above, but now different questions:

1. If I have a compound structure and a state value, how should I change this state given the value stored in my structure element, before passing it on to the substructures waiting for it? We "change our state" by calling the substructures with some modified state value. The example will make it more clear.
2. If we have an atomic structure, the answer is easy, we simply return the state. It represents the idea that we arrived at the end of our "loop", and whatever value our state has at this time is the final value.

Let's apply these two steps to our example. Remember that we have a tree structure with numbers, and we want to add those numbers up. Our "state" is the current sum of the numbers we have added up so far. We'll want this sum to be 0 to begin with. Our function would look like sum(tree, currSum).

Now first we will deal with the case where tree is a compound tree, it has an elem number, a left subtree and a right subtree. What contribution should this tree have on the current sum (i.e. how should it change the state)? Well first of all, it should add its elem, so that's just elem + currSum. Next, it needs to account for everything in its left subtree. So it would call sum on this left subtree: sum(left, elem + currSum). This would return "all the numbers we have added up so far, plus the elem, plus everything in the left subtree". Lastly, we need to now add things from the right subtree to this result, so we call sum on it passing this computed value as the state:

sum(right, sum(left, elem + currSum))

Complicated? A bit, but it has a natural flow to it. And we can use immutable variable assignments to store the intermediate components. It would look something like this (using ML-like syntax, but it should be clear how to do it elsewhere):

let
  val elemAdded = elem + currSum
  val leftAdded = sum(left, elemAdded)
in
  sum(right, leftAdded)
end

So the idea now is that each compound structure adjusts the state, then passes it on to the recursive call it does to its substructures. While atomic values simply return that state, as they have nothing to contribute to it (sum(Empty, currSum) = currSum).

We kick-start the whole process with something like sum(rootTree, 0). Since there is the second variable that is an internal state that we maintain and the user of our sum method need not know anything about, we usually do all the above in a helper method, sumHelper or something, then the main sum method would just do sum(rootTree) = sumHelper(rootTree, 0).

A different example

With the above basics out of the way, I will describe a slightly different problem, but I think it will highlight how one can maintain state without mutable variables.

The problem is this: Suppose we have a method read, that reads in a line of input from the user/file, and for our purposes I will pretend that it returns an empty string instead of an end-of-file marker. Now we want to write a function that will read in these lines of code and stores them in a list, until it encounters an empty string. Then it is supposed to call some other function f, passing it that list of lines as an argument. We will call our function loop. Let's think of what loop should do:

1. It starts with an empty list.
2. On every read adds the new string to the list, and keeps going on (recursion!).
3. When encountering an empty string needs to pass the list over to a function f.

What is our state here? It is the list of strings. So this then MUST be an argument of our loop function. In this case we don't have a recursive function to go through, so it will in fact be the only argument in our loop function. So here's how it might look:

def loop(strList) =
  let
    val newStr = read()
  in
    if !isEmpty(newStr)
    then loop(insert(newStr, strList))
    else f(reverse(strList))
  end

loop(EmptyList)

So what is going on? we read() a string and record that information in newStr. We then check to see if it isEmpty. If it is not, then we insert the newStr into our list strList, and this is the new state, so we call the loop function again passing this new state. So at any time through the loop strList, contains the strings encountered so far, it is the analog of currSum earlier.

Our termination condition now is that the new string is empty. In that case we just call f, passing it our current "state" strList. We just have to reverse it first, as the strings have been inserted in the reverse order, so to speak.

All that is left is to kick-start the process. We do that by simply calling the loop function, passing it an EmptyList to start.

Well I will stop here for now I think, I hope this was helpful to some people.

I wonder why way 2 is better than way 1?

First of all, it's because of guys like you that the open source community exists. What a great article! Thanks for writing it, it must have taken some time to put it together.

@tomchen1000 I can answer that. It's not that it's better but all programming languages that support recursion have a max level of recursions, if you exeed it you will get a stack overflow error: http://en.wikipedia.org/wiki/Stack_overflow#Very_deep_recursion. With the second approach that will not happen because the last thing the function returns is the accumulator, not another recursive call. But if you are sure that you won't reach that max level of recursions then the #1 is cleaner.

PS: Here's some more info: http://stackoverflow.com/questions/33923/what-is-tail-recursion

Great explanation !
It helped me for the Scala course on Coursera. Thanks :)

Very useful article and nicely written. Thanks.

My only piece of advice would be to remove the Secret classification and let more people see this. Really helpful stuff.

thanks skiadas.This was helpful

Excellent exposition thank you very much.

Awesome! FP is beginning to make some sense now! :P

Excellent. Thanks for putting this together.

That was enlightening, thanks :-)

nice article! thanks!