Variations on the Y-Combinator and Recursion

Practical benefits of extracting recursion from our functions

In part one of this post, we learned what the Y-combinator is, how to implement it, and saw its connection to function fixed points. As cool as this connection is, it doesn’t directly help us write better code, and in most cases, the Y-combinator in JavaScript is more interesting as a concept than it is useful as a utility. However, this post will show that there are also benefits to be gained. By separating the logic used by a recursive function from the recursive function itself, we can write logic which modifies recursive functions in general, decoupled from the logic of any specific algorithm.

To start off, let’s address a problem with the fibonacci function we wrote in the previous post.

Exponential behavior and memoization

The fibonacci function we implemented called itself twice, and so was extremely inefficient. Let’s trace what happens when we call fib(5):

fib(5) calls fib(4)
fib(4) calls fib(3)
fib(3) calls fib(2), which returns 1
fib(3) calls fib(1), which returns 1
fib(3) adds 1 + 1, returning 2
fib(4) calls fib(2), which returns 1
fib(4) adds 2 + 1, returning 3
fib(5) calls fib(3)
fib(3) calls fib(2), which returns 1
fib(3) calls fib(1), which returns 1
fib(3) adds 1 + 1, returning 2
fib(5) adds 2 + 3, returning 5

We can see here that to compute fib(5), we compute fib(3) twice, fib(2) three times, and fib(1) twice. If we did all of the tracing for fib(6), we’d see that we’d end up calling fib(4) twice, fib(3) three times, fib(2) five times, and fib(1) three times. This isn’t good: we compute the same values over and over, and the number of function calls we make increases exponentially as we try to find higher fibonacci numbers.

A common solution to this kind of problem is memoization. Memoization is an optimization technique that can be thought of as “memorization”; when we compute the value of a function for certain inputs, we can “remember” that function’s return value, so we don’t need to compute it again if the function is called with the same inputs. We can do this by saving the output of our function in a cache.

A naive attempt at memoizing our fibonacci function could look something like this:

const cache : Map<number, number> = new Map();
function fibonacciFactoryMemoized(recurse : number => number) : number => number {
  
  return function (n : number) : number {
    const cached = cache.get(n);
    if (typeof cached === 'number') return cached;
    const result = (n < 3) ?
      1 :
      recurse(n - 1) + recurse(n - 2);
    cache.set(n, result);
    return result;
  };
}

When pass this factory to y, we’ll get a memoized version of fib. This version saves its output value for each input value, so calling fib(5) results in fib(4) through fib(1) each getting called exactly once. This turns our function that ran in exponential time into a function which runs in linear time, which is pretty nifty.

There are problems with this solution, though.

One problem is that it complicates our implementation of fibonacciFactory by mixing in secondary concerns. The standard solution to this is to write a memoize function to encapsulate the memoization logic, and indeed that’s what the previously linked tutorial does. This solution has its own shortcomings, though, based around the lifetime of the cache.

In both our solution and the linked tutorial’s solution, the cache sticks around after the function is finished running. For fibonacci, this is not a problem, but for some algorithms it would be. Imagine a recursive function which ran on nodes in a graph, which cached its value by the ID of the visited nodes. We wouldn’t want to reuse the same cache for different graphs, because the same node ID might mean different things in different graphs.

We could clear out the cache between invocations, or create a new memoized function for each graph, but there’s a simpler way: limiting the lifetime of our cache to a single invocation of a recursive function. We don’t need to cache the results of our function between the calls that the rest of our program makes to it; instead, we only want that function to cache the calls that it makes to itself. In other words, instead of changing the function to be memoized, we can change the recursion done by that function to be memoized.

The Y-combinator encapsulates the essence of recursion, so we can write a new version of it which provides a different kind of recursion, recursion which is memoized using a cache:

function yMemoized<A, B>(fn: (A => B) => A => B) : A => B {
function recursive (memory: Map<string, B>, arg : A) : B {
  const cacheKey = JSON.stringify(arg);
  // Casts are because Flow doesn't treat memory.has as a type
  // refinement, and thinks `memory.get` might return undefined
  if (memory.has(cacheKey))
    return ((memory.get(cacheKey) : any) : B);
    const completeFunction : A => B =
      fn(recursive.bind(null, memory));
    const result = completeFunction(arg);
    memory.set(cacheKey, result);
    return result;
  };
  return recursive.bind(null, new Map());
};

Now, we can use our yMemoized function in place of our original y function, and get a memoized fibonacci function, without modifying our original, simple fibonacci function at all. The cache for this fibonacci function will be created fresh every time we run it, but it will still have the same efficiency gain during its execution as the first example we saw. And because we implemented this caching in a variation of y, we can apply it to any recursive function that we write using y.

Variations on recursion

We could write other kinds of Y-combinator functions, which provide different kinds of recursion. We could provide finite, bounded recursion with a version of y that limits the number of recursive calls that may be made, preventing infinite loops:

function finiteY<A, B>(fn: (A => B) => (A => B), max: number)
  : A => B {
  function recursive (invocationCount: number, arg : A) : B {
    if (invocationCount > max)
      throw new Error("Recursion went too many levels deep!");
    const completeFunction : A => B =
      fn(recursive.bind(null, invocationCount + 1));
    return completeFunction(arg);
  };
  return recursive.bind(null, 0);
}

We could provide recursion with a side-effect, which we could use to help us trace and debug recursive algorithms:

function noisyY<A, B>(fn: (A => B) => (A => B)) : A => B {
  function recursive (arg : A) : B {
    console.log("called function with ", arg);
    const completeFunction : A => B = fn(recursive);
    const result = completeFunction(arg);
    console.log("Results of arg ", arg,  " was ", result);
    return result;
  };
  return recursive;
}

By changing the types a bit, asynchronous variations could be written, working with functions that take callbacks or return promises. While normal, direct recursion may be the simplest solution in simple cases, having the ability to extract recursion out of algorithms into a separate, compositional piece opens up a toolbox for working with recursive functions in general.

The Y-combinator’s encapsulation of recursion has practical, if a bit niche, benefits. It give us a separation of concerns between what our recursive algorithms should do at each step, and how that recursion should be accomplished. This separation allows us to write functions which deal with the nature of recursion in different ways, without that logic bleeding into the logic for any particular recursive algorithm.

This article is part of my series on recursion schemes. Functions aren’t the only thing with fixed points, and for which a Y-combinator can be defined. In my next post, we’ll see how a Y-combinator on types allows us to build much more powerful tools to work with recursive algorithms in general.

Thanks to Lizz Katsnelson for editing this post.