Abstract fun

Typing Optics (2): Traversals

November 24, 2018

Last post I wrote about my first tentatives to add typings to my focused lens library. I explained the main issue was the lack of Higher Kinded Types in TypeScript which makes it uneasy to port abstractions from functional languages like Haskell.

So with a hacky workaround, I ended up implementing basic type classes and Lenses, the main tradeoff being that the solution can only be used internally in the library, since we need to specify all type parameters at the call site. This is to allow the public API to be fully typed.

So current status, we have working definitions for

  • basic typeclasses (Functor for now)
  • Lenses
  • Lens Composition
  • implementation of over

Next step, we’ll add Traversal. It’s the same definition as Lens but requires an Applicative instead of just a Functor (since a Traversal needs to operate on many values). So we need to add a definition for Applicatives as well

interface Applicative<A, B, FA, FB> extends Functor<A, B, FA, FB> {
  pure: Fn<A, FA>;
  combine: (f: Fn<A[], B>, fas: FA[]) => FB;
}

If you’re familiar with the usual Applicative definition from Haskell, the definition of combine may be a little surprising, i,e, I ‘should’ define something like

apply: (F<A -> B>, F<A>) -> F<B>`

There are 2 reasons for the above choice:

  1. apply definition makes more sense when used with languages supporting automatic currying: in Haskell, <*> (which is the operator alias for apply) can be used conveniently on a function f taking many arguments (a, b, c..): (e.g. f <$> fa <*> fb <*> fc ..). In typical JavaScript (and TypeScript) we don’t use currying much often.
  2. More important, all the interfaces are mainly to be used internally by focused to define the public API. The recurrent use case for using Applicatives with Traversals is to operate on the values embedded inside a monomorphic container (i.e. containing many values of the same type like Array, Set …), so it makes more sense to adopt the combine definition rather than a polymorphic/curry-oriented version.

The definition of a Traversal is

interface Traversal<S, T, A, B> {
  $applyOptic: (<FB, FT>(
    F: Applicative<B, T, FB, FT>,
    f: Fn<A, FB>,
    s: S
  ) => FT);
}

The Applicative implementation for Identity is trivial

const Identity = {
  //...
  pure: x => x,
  combine(f, xs) {
    return f(xs);
  }
};

Next step, we need to adjust the type definition of compose (we don’t have to touch the implementation, just instructs the compiler how to derive the right Optic).

So here begins our second challenge. In Haskell, we don’t have to write anything special since the compiler can automatically infer the result type. Remember, in Haskell the type definitions for Lens and Traversal are

type Lens s t a b = forall f. Functor F => (a -> f b) -> s -> f t
type Traversal s t a b = forall f. Applicative F => (a -> f b) -> s -> f t

If for example we compose a Lens with a Traversal, the compiler infers that the f type parameter for the resulting function must satisfy both the Functor and Applicative constraints, since Applicative is more specific than Functor, the constraint can be simplified to Applicative, which yields the same type definition as Traversal.

Now with TypeScript, the first issue is that we can’t use simple function composition because:

  • Our optic functions has 3 paramaters (the typeclass, the function and the state)
  • Even if we redefine our functions with the idiomatic/curried style, we’d have to solve the Higher Kinded Type issue again. And even if we take that road (e.g. using the URI solution) I doubt we’d succeed in making TypeScript unify the type parameter constraints.

Still, TypeScript offers an adhoc solution: function overloading. We can define multiple signatures for each combination of 2 optics. Normally, since we have [for now] 2 optics (Lens & Traversal) we’d have to write 4 (2*2) overloads. But in reality we ‘should’ only have 2 cases. Why? first let’s write down the definitions

function compose<S, T, A, B, X, Y>(
  parent: Lens<S, T, A, B>,
  child: Lens<A, B, X, Y>
): Lens<S, T, X, Y>;
function compose<S, T, A, B, X, Y>(
  parent: Traversal<S, T, A, B>,
  child: Traversal<A, B, X, Y>
): Traversal<S, T, X, Y>;
// Lens composition
function compose(parent, child) {
  return {
    $applyOptic(F, f, s) {
      return parent.$applyOptic(F, a => child.$applyOptic(F, f, a), s);
    }
  };
}

Now, here is the why: because every Lens is also a Traversal (the inverse is not necessarily true). Remember that the 2 interfaces differ only on the constraint imposed on the typeclass (the 1st) parameter:

  • Lens is (equivalent to) a function which takes a Functor
  • Traversal is (equivalent to) a function which takes an Applicative

In other words, Lens’s function is more permissive (can take more values) than Traversal’s one. So it can be dropped on any context where a Traversal is expected. BTW, this is a general rule, it’s because functions are said to be Contravariant in their parameter types (you can replace a function with another taking more general argument => subtyping relation goes on the inverse direction of the enclosing function type). They are also Covariant in their results (you can replace a function with another returning a more specific result => subtyping relation goes on the same direction). There is a nice phrase in Wikipedia>) that summaises it

be liberal in what you accept and conservative in what you produce

But there’s still one (perhaps more) caveat. Contravariance isn’t enabled by default in TypeScript. Because for some reason TS folks decided to make function types bivariant on their parameters (type compatibility works on both directions)

When comparing the types of function parameters, assignment succeeds if either the source parameter is assignable to the target parameter, or vice versa. This is unsound because a caller might end up being given a function that takes a more specialized type, but invokes the function with a less specialized type. In practice, this sort of error is rare, and allowing this enables many common JavaScript patterns.

Of course, there is a strictFunctionTypes option in TS which enables Contravariance in function parameters. But I’m not particularly comfortable with enforcing this on the library user. So we’d have to resort to some other workaround. This time we’ll simply add an optional field $type to each optic definition

interface Lens<S, T, A, B> {
  readonly $type?: "Lens" & "Traversal";
  // $applyOptic:  ...
}

interface Traversal<S, T, A, B> {
  readonly $type?: "Traversal";
  // $applyOptic: ...
}

It works, but to be honest, at the time of this writing, this is still kinda dog science for me. On one hand the fields are optional so we don’t have to alter the existing definitions (esp. compose), on the other hand, the compiler seems to infer correctly that Lens is more specific than Traversal without Contravarance enabled because of the presence of fields in the type definition.

Only left (for today) is typing over. We’ll simply take the most generic optic which is Traversal

function over<S, T, A, B>(l: Traversal<S, T, A, B>, f: Fn<A, B>, s: S): T {
  return l.$applyOptic<B, T>(Identity, f, s);
}

I know, we’re getting more and more away from Haskell spirit but that’s inevitable. As I said, the main goal of this is to provide a working type definition for the public API. The library user could then uses Optics and operations like over or view in a typesafe way. If it means sacrificing the ‘internal elegance’ of the model, I’m ok with it.

I believe it’s enough for today. Next challenge will be integrating Isomorphisms and Prisms

Links