Laziness with Representable Functors

Brian Lonsdorf
Jul 20, 2017 · 5 min read

Recommended listening during read: https://open.spotify.com/track/1vBb916w3u10h8U87QJ1GN

Tl;dr

We can convert any indexable data structure into its function form to achieve laziness. Formally, there’s an isomorphism from any Representable Functor to Reader. Gist is here: https://gist.github.com/DrBoolean/9b951c1c2cb225be9c289b0a2239132f

Prereq

I boldly use words like curry (functions that take 1 arg at a time), isomorphism (a lossless transformation to/from), and functor (a type with a map method)

Eager Beavers

At work we have a data structure called UI that describes our design system.

It looks like this:

UI data structure

We have tooling, a documentation site, tests, etc, that all expect this structure.

Here’s sort of how we build/use it:

Create and use UI

At the end of the day, we want the whole thing, but while developing with hot reload and all, we don’t want to take the time to make every component on every change since it’s pretty expensive.

Turns out a “sparse” version with the component we’re working on filled out would suffice:

Sparse UI

Ya know, something that can be lazily generated as we go along.

REPRESENTABLE

A functor is dubbed Representable if it isomorphic to Function.

This tends to be the case when we have a fixed number of “slots” in our functor and we can represent it with some other type as an index. To do so, we just need an isomorphism and some other type with which to index.

Lets see a few quick examples.

Id can be represented by undefined since it has 1 slot and undefined has 1 instance

Id represented by undefined aka ()

See the symmetry in those type signatures of to/from there? In to we simply capture the data structure in a closure via currying and return a function that gives us the value. Going the other way, from just calls that function to give us back Id.

Pair can be represented by Boolean since it has 2 slots and Boolean has 2 instances:

Pair represented by Boolean

We could also choose any other type with 2 instances — it doesn’t have to be Boolean (though I’m partial).

So we can turn our functor into a function and back. Neat!

If you think about it, feeding a function some input to get a value is the same thing as feeding a data structure some index to get a value. So we can convert from a data structure that can be indexed, to a function which takes an index to a value.

This only works on types that don’t change shape and have a fixed number of slots.

Well that sounds perfect for our UI issue — instead of a full eager data structure, we can convert it to a lazy function that gets us components on demand.

Represent!

UI is already a functor since Map has a map method via Immutable.js.
Let’s make UI a representable functor by adding an index type and isomorphism:

Representable instance for UI

For the index type we used the list of Components since we know the keys line up with the values in our UI (cause that’s how we build it). Formally, we’d say we UI is “represented by” Components. This is cheating a bit. Usually, you’d see a sum type like Components = Alert | Button | DataTable I’m fine with this morally, since we can’t be that much more type safe in plain JS anyways.

So that’s our index type. Next we defined our isomorphism (the to/from part).

The from :: (Component -> a) -> UI function basically says “given a function from Component to some a, I’ll build up the whole UI structure”. We just use that same reduce we used to build UI earlier except this time, we pass the index to the provided function so we can set the value to whatever.

Now for the other way, to :: UI -> (Component -> a). Which says, given a UI, I can return you an index function. Currying for the win!

Takin’ it for a spin

Let’s change this old version:

Old Eager Version

To this:

New Lazy Version

Comparing these two, we only have to change the beginning and end bits. from will build up the whole UI structure from a function — here we just use the identity function x => x to recover what we had. Then we call to(empty) and map away. Note, we’re not mapping over our Immutable.Map anymore, we’re mapping over our function!

Wait, Function doesn’t have a functor instance in JS… Never fear though, we can use one more isomorphism.

Reader Monad

The default map behavior for a function is simply composition. I’ve written about it before:

Instead of altering Function.prototype, we can add a wrapper we call Reader.

Here’s a quick implementation:

Reader Monad w/ examples

It simply swallows up our function so we can decorate with map and chain and stuff.

Okay now we’re all set:

Great! We didn’t have to do anything except throw a Reader around it and call run. Problem solved!

Extra things to Know

  • Representable works on types with fixed or infinite slots, but not varying shapes or sum types in general.
  • Every Representable functor is distributive (like traversable) and a monad/comonad due to it being isomorphic to Reader
  • Sum types typically index into Product types. For further reading checkout functor Pairings and Adjunctions

Full, running code is posted here: https://gist.github.com/DrBoolean/9b951c1c2cb225be9c289b0a2239132f

This was inspired by Chris Penner’s recent work. Checkout his blog http://chrispenner.ca/

*Artwork by Garth Jones https://www.behance.net/gallery/30375121/Sketchbook-2015

)