Recursion in TypeScript (without the tears)

Principal devs hate this one weird trick...

Have you felt frustrated by how hard recursion is?

If you've ever tried writing recursive code in TypeScript, all types do is seem to get in the way, and distract you from the real problem you're trying to solve.

Trust me, I've been there.

But what if I told you there was a way you could make TypeScript do the hard part for you?

What if there was a way to make recursion type-safe?

Today I'm going to show you a trick I wish I'd known about circa 2016, when I started on my TypeScript journey.

Enough preamble: let's look at some code.

• Playground
• Sandbox

JSON.map

To start, let's imagine the built-in JSON namespace had a .map method, similar to Array.

How would it behave?

For starters, it would have to be structure-preserving, like Array.prototype.map.

What do I mean by structure-preserving?

Simple: if you map over an array, the array that comes out will always have the same number of elements as the one you put in.

Same things goes for our imaginary JSON.map -- only since we also have objects, it will need to preserve the object keys, and only apply the function to object values.

To make implementing our map function easier, first let's write a function that abstracts away whether we're mapping over an array or an object, since for our purposes, we want to "forget" that there's a different.

We'll call it mapObject, since arrays are also objects:

function mapObject(
  src: { [x: string]: unknown } | unknown[], 
  mapFn: (src: unknown, ix: any, xs: typeof src) => unknown
) {
  if (Array.isArray(src)) return src.map(mapFn)
  else {
    const keys = Object.keys(src)
    let out: { [x: string]: unknown } = {}
    for (const key of keys) {
      out[key] = mapFn(src[key], key, src)
    }
    return out
  }
}

If we try it out, we can see that it works with both objects an arrays, and that in both cases, our implementation is structure-preserving.

Now let's implement JSON.map:

type Scalar = 
  | null
  | boolean
  | number
  | string

type Json<T> =
  | Scalar
  | readonly T[]
  | { [x: string]: T }

const isScalar = (src: unknown) => src == null 
  || typeof src === 'boolean' 
  || typeof src === 'number' 
  || typeof src === 'string'

const isArray
  : <T>(src: unknown) => src is readonly T[] 
  = Array.isArray

const isObject = <T>(src: unknown): 
  src is { [x: string]: T } => !!src
  && typeof src === 'object' 
  && !isArray(src)

export function mapJSON<S, T>(
  f: (src: S) => T
): (x: Json<S>) => Json<T> {
  return (x) => {
    switch (true) {
      default: return x
      case isScalar(x): return x
      case isArray(x): return mapObject(x, f)
      case isObject(x): return mapObject(x, f)
    }
  }
}

That's a lot of code -- let's walk through it:

Json<T>

First I created a Json type. Only, this Json type is a little bit different than what you'll usually see; can you spot this difference?

type Scalar = 
  | null
  | boolean
  | number
  | string

type Json<T> =
  | Scalar
  | readonly T[]
  | { [x: string]: T }

Well, for starters, this definition of Json is not recursive.

To see what I mean, let's compare it to the Json type you'll usually see in the wild:

type Json =
  | Scalar
  | readonly Json[]
  | { [x: string]: Json }

This definition has its advantages, and its disadvantages.

The biggest advantage is that it definitely rules out values such as bigint, symbol, Dates and undefined.

But the disadvantage is that the type isn't flexible.

What we're trying to do with our JSON.map function is think about JSON in terms of its structure -- remember, we're zooming out, and focusing on implementing a JSON.map that works like Array.map.

Here, from where we're standing, we're making the decision to not focus on the details that make generic data structures like Array<T>, Map<K, V> different than JSON, and instead focus on the ways in which they can be thought of as being the same.

Taking this perspective comes with its advantages, and for our use case, we're mostly interested in 2:

1. because this definition does not rush to constrain its input, Json.map will be able to take JSON input, and map it to other, non-JSON targets (like bigints and Dates)

2. because this definition is not recursive, it perfectly describes our primary goal, which is to factor out recursion.

To see what I mean, let's practice some wishful thinking.

Wishful thinking

When it comes to recursion, what do we want?

If you said "to never have to write recursive code", you're well on your way to thinking like a functional programmer!

Let's explore that idea.

Let's pretend for a moment that JSON.stringify isn't a thing. It doesn't exist. And it's our job to implement it.

How would we go about implementing it? Is there a way to do it that doesn't involve recursion?

Let's write some pseudo-code:

function toString<T>(json: Json<T>) {
  switch (true) {
    // if we've got a scalar value, turn it into a string:
    case isScalar(json): return String(json)
    // how are we supposed to get to the values?
    case isArray(json): 
    // how are we supposed to get to the values?
    case isObject(json):
  }
}

How are we supposed to implement this, if we can't call our toString function on the elements values?

Well, what if we didn't have to?

Reframing the problem

What if, again, practicing some wishful thinking, we instead use Json<string> instead of Json<T>?

function toString(json: Json<string>) {
  switch (true) {
    // if we've got a scalar value, turn it into a string:
    case isScalar(json): return String(json)
    // how are we supposed to get to the values?
    case isArray(json): 
    // how are we supposed to get to the values?
    case isObject(json):
  }
}

See if you can handle the array and object cases, now that we've factored out the recursion.

This part is important.

I highly encourage you to try it out in the Playground.

I can talk all day about how this technique is useful, or about how the technique works, but if you don't get your hands dirty, things won't stick, and this technique probably won't make any sense.

I'll give you a few minutes to try it out.

...

Okay, how'd you do?

Here's what I came up with:

Playground

function toString(json: Json<string>): string {
  switch (true) {
    case isScalar(json): return String(json)
    case isArray(json): return '[' + json.join(', ') + ']'
    case isObject(json): return '{' + Object.entries(json).map(([k, v]) => `"${k}": ${v}`).join(', ') + '}'
    default: return json satisfies never
  }
}

Was this close to what you came up with?

If not, don't feel bad: the first time I tried this, I tried too hard. In fact, I was so used to recursion being hard, that I had a hard time accepting that such a direct approach was possible.

But wait a minute... you haven't shown us anything. We're still doing wishful thinking, remember? So far we haven't actually implemented anything.

Ah, you're right. I'm getting ahead of myself. We still haven't actually factored out the recursion. Let's do that.

Factoring out recursion

For this next part, you're going to have to trust me that you'll never have to actually write this code yourself.

By that I mean, it's possible to implement a generalized version of this function.

Again, this isn't the kind of thing you'll need to "roll yourself" every time you have a new data structure you need to work with.

Okay, with that out of the way, here's the code that takes care of the recursion for us:

function lift<T>(json: T): Json<T>
function lift<T>(json: T) { return json }

function foldJson<T>(reducer: (json: Json<T>) => T): (json: Json<T>) => T {
  return function loop(value: Json<T>): T {
    return reducer(mapJson(loop)(lift(value)))
  }
}

That's it.

I've got another article planned where I talk through exactly why and how this function works, but it's worth noting that I didn't come up with it myself -- I simply ported it from the Haskell library that first introduced this technique.

Okay, that was the sweaty part.

Does it actually work?

Seeing it in use

See for yourself:

Sandbox

Great! Let's recap:

Recap

To make working with recursive code easier, we explored a way we can "factor out" recursion.

To simplify things, we chose to focus on only JSON values, and to make things concrete, we chose just to focus on implementing a naive version of JSON.stringify.

To get there, we had to make a few decisions:

1. To make things type-safe, we opted for a non-traditional, non-recursive definition of Json, which looked like this:

type Json<T> = 
  | null 
  | boolean 
  | number 
  | string
  | readonly T[]
  | { [x: string]: T }

1. Then, we used this type to implement a utility function called mapJson that let us zoom out a bit, and apply a function to a JSON value without knowing anything about its structure in advance. Importantly, this map function preserves structure -- meaning that the value that we get out will have the same "shape" as the value we put in -- the only thing that will change are the leaf values.

That map function looked like this:

export function mapJson<S, T>(f: (src: S) => T): (x: Json<S>) => Json<T> {
  return (x) => {
    switch (true) {
      default: return x
      case isScalar(x): return x
      case isArray(x): return mapObject(x, f)
      case isObject(x): return mapObject(x, f)
    }
  }
}

1. We leaned on some "library code" to handle the recursive bit. I won't put that code here, because it's not important that we fully grok how that code works for us to use it.

2. Finally, we implemented a naive version of Json.stringify. Notably, this implementation was not recursive:
   

function toString(json: Json<string>): string {
  switch (true) {
    case isScalar(json): return String(json)
    case isArray(json): return '[' + json.join(', ') + ']'
    case isObject(json): return '{' + Object.entries(json).map(([k, v]) => `"${k}": ${v}`).join(', ') + '}'
    default: return json satisfies never
  }
}

The takeaway here is that because this implementation is not recursive, it's also 100% type-safe. Here, TypeScript was our friend, since when we went to implement the array and object cases, it was there to remind us that we were working with string[] and { [x: string]: string }, and not unknown[] or { [x: string]: unknown }.

Finally, we put all the pieces together, wrote a few tests, and made sure it all worked!

The full implementation + tests is available in a Sandbox that you can play with.

If you're only interested in the types, you can check out the Playground.

Phew! That's a lot for one day.

Closing thoughts

It's important when you're learning something new to balance the theory with practice -- and to not overload yourself with too much information -- so I think we should call it here.

Congratulations! If this is the first time you've ever used recursion schemes before, you're not alone -- this technique, although quite popular in the functional programming world, is virtually unheard of in the TypeScript ecosystem.

If you're hungry for more, I went ahead and included an example in the Sandbox that applied the same technique to solve a notoriously tricky recursive problem: turning a deeply nested JSON object into a flat object whose keys are the paths, and whose values are the corresponding value at that path.

I've called it Json.toPaths, since that's the name most commonly used to describe this operation in the JavaScript ecosystem.

Plugs

If you liked this kind of content, you might be interested in a library that I wrote called @traversable/schema. It's a TypeScript schema library -- kinda like a lightweight zod (faster at runtime, and scales to arbitrarily large schemas without slowing down your IDE). Recursion schemes are at the heart of its implementation -- it even includes the same Json.map we implemented earlier.

And if you're hiring TypeScript developers and liked this content, I'm in the market -- let's talk! Feel free to email me at [e-mail] if you'd like a copy of my resume.