Typing Optics with TypeScript

I remember my first attempts to learn Optics started long time ago, I stopped on basic things due to the lack of good resources at the time. Recently, lens over tea series by Artyom Kazak renewed my interest. I recommend it for anyone looking for a deep dive on the topic (Depending on your taste, you may find Artyom’s style boring or amusing).

As part of my learning process, I usually try to port/adapt the ideas I learn from Haskell into JavaScript. The result is (yet another) JavaScript Optics library called focused (there are many Lens libs in JS but most of them support just Lenses, other optics like Prisms or Traversals are omitted).

The library reuses the same underlying representation from the famous Haskell lens library (known as the Van Laarhoven representation). In this model, all Optics are normal functions (well until we get to the profunctor stuff) of the same form (A -> F<B>) -> S -> F<T> and only differ in the constraints imposed on the F Generic wrapper (Some more info on this twitter thread).

One of the main todos on focused roadmap is to add Typings to the library. I’ll be starting with Typescript but I think a potential solution could be also transposed to Flow (Since I’m relatively new to TypeScript, I may be missing something in the following).

So I started doing some experiments with TypeScript, and soon I stumbled upon a fairly common issue when you try to re-implement ideas from a language like Haskell: the lack of Higher Kinded types. The Haskell lens library already uses some advanced features of the Haskell type system, but it’s not even easy to have something ‘basic’ like type classes to work in TypeScript (this is not to imply TypeScript is inferior to Haskell, we can’t even compare them because the paradigms are so different, it just illustrates my struggle).

A bit of googling lead me to some ingenious workarounds like this one. Unfortunately, this won’t work in my case, the solution requires the values to be wrapped in objects (so we can have a URI property that identifies the current interface). focused uses static interfaces that work with plain JS types. For example, I don’t want to wrap/unwrap accessed values in classes like Identity<A>. Ideally, functions should work directly on A. In Haskell, you can put values in a newtype which gives you the URI like feature but without the runtime overhead. I also found some attempts to implement a newtype-like thing with abstract types in Flow or intersection types in TypeScript, but this also didn’t work so well on my case (I could’ve also misused something).

My current (unfinished) workaround is to give up the Generic type inference and just apply the type parameters directly on the call site. For example, let’s take the definition of Functor

First, here is the Haskell definition

class Functor f where
  map: (a -> b) -> f a -> f b

in an hypothetical TypeScript like language with support for Higher Kinded Types, this would look like

interface Functor<F> {
  map: <A, B>(f: (a: A) => B, fa: F<A>) => F<B>;
}

But it won’t work in the actual TypeScript because we can’t apply the Generic Type Parameter in a Generic way (pun is inevitable). So my workaround is to move up all type parameters in the interface definition

interface Functor<A, B, FA, FB> {
  map(f: Fn<A, B>, x: FA): FB;
}

Now, let’s take a simplified definition of a Lens. In Haskell

type Lens s a = Functor f => (a -> f a) -> s -> f s

Which in our hypothetical TS would be

type Lens<S, A> = <F extends Functor>(f: (a: A) => F<A>) => ((s: S) => F<S>);

With our workaround we need to add type parameters for F<A> and F<S>. (omitting the type extends constraint) this gives us

type Lens<S, A> = <FA, FS>(F: Functor<A, S, FA, FS>, f: Fn<A, FA>, s: S) => FS;

Let’s say we want to write over which allows us to update the value inside a Lens. In Haskell, a simplified type definition is

over ::(Lens s a) -> (a -> a) -> s -> s

The function takes a Lens, the function that will update the embedded value a, and the whole value s. It then returns a new whole value s with a updated.

The implementation of over in Haskell calls the provided Lens with a function which updates the a using f, wraps the updated value in the trivial Identity Functor, the Lens does its internal business and transforms Identity a to Identity s, and finally we unwrap the embedded s using runIdentity.

over l f s = runIdentity $ l (\a -> Identity (f a)) s
-- or equivalently
over l f = runIdentity . l (Identity . f)

Of course, Haskell isn’t actually really wrapping/unwrapping values in Identity because Identity is defined using anewtype so the wrapping doesn’t occur at runtime, it’s just here so we can implement the Functor type class and other interfaces.

newtype Identity a = Identity { runIdentity :: a }

instance Functor Identity where
  map f (Identity x) = Identity (f x)

To implement something like this in (real) TS, we could write Identity as a static interface which works on plain (non wrapped) values

const Identity = {
  map(f, x) {
    return f(x);
  }
};

Then to implement over we typecast Identity using the actual type parameters

function over<S, A>(lens: Lens<S, A>, f: Fn<A, A>, s: S): S {
  return lens(Identity as Functor<A, S, A, S>, f, s);
}

From the perspective of a library user, this is transparent. He would just call over(lens, fn, state), the TS compiler will automatically infer the S and A parameters from the actual arguments (or expected return value) and specializes our Identity as needed. In fact this is the main trade off of this approach, we’re giving up automatic inference internally in order to have it supported in the public API.

So far, I can type Lens composition without problem. Proxy code also works (with some minor caveats). The next challenge is to make it work with other Optics, mainly we need composition to figure out the right Optic type resulting from compositing 2 or many other Optics.

Links

TypeScript playground demo which implements a simplified version of the idea (using only Lenses)

For the interested, here is also a Haskell implementation I was playing with