Itero-recursive algorithms.

description.md

Iterorecursive algorithms

Picture the following scene: you are in a job interview, and the interviewer defines a tree-based data structure and asks you to traverse it. You do a good quick job, maybe using recursion:

// provided by the interviewer: nonempty rose trees carrying the values on the internal nodes
interface ITree<x> {
  value: x;
  children: Array<ITree<x>>;
}

// you come up with:
function traverse<x>(tree: ITree<x>, visit: (arg: ITree<x>) => void) {
  visit(tree);
  for (const subtree of tree.children) {
    traverse(subtree, visit);
  }
}

“Great,” they say, “but this will hit the nodes of the tree in depth-first-order, so what if our tree was infinite or rapidly branching or something and you had to modify this into a breadth-first search instead?”

If you’ve seen the approach before it’s not too hard, you just keep a queue. So you start to write something like

const queue: Array<ITree<x>> = [tree];
while (queue.length > 0) {
  const subtree = queue.shift();
  if (visit(subtree)) {
    return { type: 'found', value: subtree };
  }
  // otherwise
  for (const child of subtree.children) {
    queue.push(child);
  }
}
return { type: 'not found' };

The interviewer then asks, “okay, but what I liked about the previous algorithm was that traverse was recursive. What if I asked you to do this recursively?”

You could, of course, object programmers must optimize for their colleagues’ understanding first, and code clarity will suffer from this change. Some folks I know would definitely say, “What does that have to do with writing quality software?” and then prepare to leave the interview, questioning whether any of these interview questions can help to hire quality programmers.

We face a minor danger here though. We have a word for true statements said in place of actually accomplishing a challenge: English calls them “excuses” and even when “valid” an excuse does not actually rise to the occasion. Maybe subconsciously you think that working out the recursive version could take all afternoon. It won’t. More importantly I found this exercise very important when I started to learn another programming language, Haskell.

The Haskell sitch

The designers of Haskell built a functional programming language: “everything is a function.” In it, we do not have for(_;_;_) or while(_) loops. The story behind this is a little involved. We can most naturally view most languages in an imperative model of computation: like how let x = 1 means “create a new (mutable) name in the current block called x, and then point that name at the value 1” in JavaScript. We could say that the language consists of commands.

Functional programming comes from a simpler model of computation, the principle of substitution. You write a template which takes a named parameter and contains a “body;” when this template gets “applied” to a value, then the computer substitutes every use of that name in that body with that value. And the principle of substitution, while it plays very nice with definitions, does not usually play nice with mutable things. FP says, “you mean after I have performed this substitution I need to still keep track of what I substituted, so that when you change this value I can change all 5 instances of it in my filled-in template? Except that you want to change the value while I am still simplifying and reducing parts of this template?” You rapidly find yourself reinventing that imperative model just from variables alone. I am not quite sure why this is. Template substitution has a weaker, more implicit, understanding of time than the imperative model; perhaps variables are just naturally easier to phrase with a stronger, more explicit understanding of time.

But if you don't have true variables then what are you going to do with while(_)? Whatever gets substituted into its parentheses must remain unchanged, leaving while(true) and while(false). “Aha,” you say: “I will just use break statements!” ... but how are you going to phrase those as something that plays nice with template substitution? I am not saying it is impossible, just that Haskell wisely waved a white flag and surrendered.

How we make do

So everyone who comes to Haskell now needs to learn how to do looping without for and while. We instead use recursive functions—functions that are defined in terms of themselves. It turns out that these can be rewritten with the same jump instructions that for and while use by the compiler so long as every recursive call looks like,

// within a definition of f(x, y, z)
return f(newX, newY, newZ);

Note that there cannot be manipulation of the value afterwards, like return f(...) + 1 is not allowed: that semicolon is exactly where it needs to be. In some ways this makes things worse! Not only do you have to write your loop as a recursion, you must write it in this “tail-recursive” style!

So I wanted to show you a really simple approach in JS, before you even get to Haskell and its brethren, that I call “iterorecursive” algorithms. If you are ever in a job interview and asked to reverse a linked list recursively, and you know the iterorecursive trick, you can easily ace the above question. Once you have an iterative algorithm, you should not have problems converting it to a recursive one, if you know this trick. And because it came from the iterative algorithm, your solution will naturally be tail-recursive.

The steps in general

1. Write out the loop, maybe in pseudocode. (If this were a job interview you might be able to say “would you mind if we thought it through iteratively first?” if you have, say, been asked to recursively reverse a linked list.)
2. Identify what variables you are modifying in each step of the loop.
3. Define a function which will run one step of the loop. Each of the above variables enters as an argument to that function.
   • This could be either the actual function that you're going to return, or an internal “work” function which does the loop.
   • Especially if you need to preprocess something coming into the function, you may need to have this internal “work” function. Also if you seem to write the same postprocessing logic in two or three places, I would find it worth considering.
   • If you don’t, then you can use the JS syntax f(x, y, var1=startingValue, var2=startingValue2) to fill in the starting values for the variables, and then you can just return the one function.
   • A good name for internal work functions is go, if you don't have a more descriptive name.
4. Write the loop-failure condition at the top of this function, the one that will exit the loop, as an if statement. Figure out what value you want to produce when the loop is complete, and return it inside of that if statement.
   • What really helps is a trick I picked up in my physics degree: write down the simplest input, and what the answer is for the simplest example, then fill in the combination of arguments which makes that simplest example correct.
5. Maybe write some const expressions, if you want to destructure an object or you are going to need to use a sub-expression twice and you would rather name it here.
6. Start with return myFunctionName(...) then fill in the ... with all of the new values of arguments that the single step of the loop would compute.
7. Surprisingly, you are probably done and it probably works. Test it out a bit!

itero-recursive.ts

/* First example: Fibonacci numbers. If you wrote out an iterative algorithm it would look like:
 *
 *     function fibs(n) {
 *       let [last, curr] = [0, 1];
 *       for (let i = 0; i < n; i++) {
 *         [last, curr] = [curr, last + curr];
 *       }
 *       return last; // think: why isn't this `curr`?
 *     }
 *
 * Here is the iterorecursive translation of that:
 */
function fibs(n: number, i = 0, last = 0, curr = 1): number {
  if (i >= n) {
    return last; // because fibs(0) == 0
  }
  return fibs(n, i + 1, curr, last + curr);
}

// Second example: reversing a singly linked list. First let's write out the definition:

interface ICons<x> {
  first: x;
  rest: SLL<x>;
}
type SLL<x> = ICons<x> | null;

/* Here the iterative algorithm looks something like,
 *
 *     function reverse(list) {
 *       let todo = list;
 *       let reversed = null;
 *       while (todo !== null) {
 *         const { first, rest } = todo;
 *         reversed = { first, rest: reversed };
 *       }
 *       return reversed;
 *     }
 *
 * So you would have:
 */
function reverse<x>(todo: SLL<x>, reversed = null as SLL<x>): SLL<x> {
  if (todo === null) {
    return reversed; // because reverse(null) = null
  }
  const { first, rest } = todo;
  return reverse(rest, { first, rest: reversed });
}

/* As an example where you might need more structure, consider how you might concatenate two 
 * singly-linked lists; one approach might be:
 * 
 *     function concat(list1, list2) {
 *       // we need to tack last element of list1 onto the front of list2, so let's reverse it
 *       let todo = reverse(list1);
 *       let done = list2;
 *       while (todo !== null) {
 *         const { first, rest } = todo;
 *         todo = rest;
 *         done = { first, rest: done };
 *       }
 *       return done;
 *     }
 *
 * Preprocessing the input is the sort of sitch where you want to define an inner function:
 */
function concat<x>(list1: SLL<x>, list2: SLL<x>): SLL<x> {
  function go(todo: SLL<x>, done: SLL<x>): SLL<x> {
    if (todo === null) {
      return done;
    }
    const { first, rest } = todo;
    return go(rest, { first, rest: done });
  }
  return go(reverse(list1), list2);
}

/* Final example, building on the other two, is the one from description.md: you are doing a 
 * breadth-first search with some predicate on a rose tree. Again we can start with the data 
 * structures. The simplest purely functional queue is two singly-linked lists, the "front" is
 * stored in the normal order and the "back" is stored in reverse order, so that you can add to the
 * back of the queue instantaneously. You cannot pick up from the front instantaneously, but it is
 * usually not a horrible cost either: if the front is empty and the back contains N elements then
 * it will take N steps to reverse the back into a new front, but then you don't have to do this
 * again for N more steps. 
 */
interface IQueue<x> {
  front: SLL<x>;
  back: SLL<x>;
}
function emptyQueue<x>(): IQueue<x> {
  return { front: null, back: null };
}
function singletonQueue<x>(x: x): IQueue<x> {
  return { front: { first: x, rest: null }, back: null };
}
function addToQueue({ front, back }: IQueue<x>, elements: SLL<x>): IQueue<x> {
  return { front, back: concat(reverse(elements), back) };
}

type Maybe<x> = null | { just: x };

function popQueue<x>({ front, back }: IQueue<x>): Maybe<[x, IQueue<x>]> {
  if (front === null) {
    const reversed = reverse(back);
    return reversed === null
      ? null
      : { just: [reversed.first, { front: reversed.rest, back: null }] };
  }
  return { just: [front.first, { front: front.rest, back }] };
}

// we also need a type of trees; let's suppose it looks like so:
interface ITree<x> {
  value: x;
  children: SLL<ITree<x>>;
}

/* Then if you had these you could pretty easily come up with an iterative algorithm, like maybe:
 *
 *     function bfs(root, predicate) {
 *       let popped = {just: [root, emptyQueue()]};
 *       while (popped !== null) {
 *         const [node, queue] = popped.just;
 *         if (predicate(node)) {
 *           return {just: node};
 *         }
 *         popped = popQueue(addToQueue(queue, node.children))
 *       }
 *       return null;
 *    }
 *
 * And we can translate this directly:
 */
function bfs<x>(root: ITree<x>, predicate: (tree: ITree<x>) => boolean): Maybe<ITree<x>> {
  function go(popped: Maybe<[ITree<x>, IQueue<ITree<x>>]>): Maybe<ITree<x>> {
    if (popped === null) {
      return null;
    }
    const [node, queue] = popped.just;
    if (predicate(node)) {
      return { just: node };
    }
    return go(popQueue(addToQueue(queue, node.children)));
  }
  return go({ just: [root, emptyQueue()] });
}

postscriptum.md

Intentional bug

I actually left a bug I wrote in one of the commented-out iterative algorithms above. Can you find it? It would look much more out-of-place if you propagated it to the tail-recursive version, but above it is the absence of a line which has to be there: very frustrating!

Conclusion

So there’s nothing to fear from making iterative algorithms into tail-recursive ones. You ace the interview, you perhaps get a job and perhaps get to come up with a set of alternative hiring practices that work better for that company. I don’t know. I definitely think that there’s room for excuses in life, that you don’t need to rise to every challenge but have to pick your battles wisely. I just wanted you to understand that this particular battle of making things tail-recursive is less of an ordeal, more of a minor skirmish.

Come learn Haskell on the functional programming Slack!

If you have suggestions for making this better or just want to chat with me about something, I am @crdrost on Twitter or you can drop me a line with the same username at GMail. If you follow me I must warn you that I’m also trained in physics and a Christian mystic, so I tweet those sorts of things, too: they may not be the most relevant to you.