Typing Optics (3): Isomorphisms and Prisms

November 24, 2018

This is the 3rd post documenting my tentative to add typings to my focused lens library.

So far, I’ve been able to add type definitions for

base typeclasses/interfaces (Functor and Applicative)
Lenses
Traversals
Lens & Traversal Composition
type definition of over

In this post I’ll be tackling Isomorphisms and Prisms

Isomorphisms

If we look at the typical definition of Isos in Haskell

type Iso s t a b = forall p f. (Profunctor p, Functor f) => p a (f b) -> p s (f t)

There is a story behind this representation. You can read it in detail in the linked post (but it’s not required to follow the rest).

To simplify, an Iso can be represented in 2 ways: functional & concrete . The concrete representation matches our intuition about Isos, a pair of inversible functions

data CIso a s = CIso (s -> a) (a -> s)
-- or using the polymorphic version
data CIso a b s t = CIso (s -> a) (b -> t)

The functional representation is similar to Lenses

type FIso s t a b = (a -> f b) -> s -> f t

We need Isos to be both above representations at once. In Haskell we do this by creating a typeclass (something like an interface) that abstracts over both representations and instantiate (implement) the typeclass for each concrete representation. For Isos, the typeclass used is the Profunctor class. By making both functions and CIso instances of it, we can rely on Haskell type inference to choose the appropriate representation (for the interested here is an an implementation example, look at the file Iso.hs).

Now, in TypeScript, I don’t actually want to introduce Profunctors in the library for various reasons. But I can have both representation as part of the same interface.

interface Iso<S, T, A, B> {
  readonly $type?: "Iso" & "Lens" & "Traversal";
  $applyOptic: (<FB, FT>(F: Functor<B, T, FB, FT>, f: Fn<A, FB>, s: S) => FT);
  from: (s: S) => A;
  to: (b: B) => T;
}

Each Iso is a also a Lens (and by extension a Traversal), since the functional implementation is the same as the Lens one.

Now the trick is I can always construct the functional representation given the concrete representation

function iso<S, T, A, B>(from: (s: S) => A, to: (b: B) => T): Iso<S, T, A, B> {
  return {
    $applyOptic(F, f, s) {
      return F.map(to, f(from(s)));
    },
    from,
    to
  };
}

And I can inverse an Iso using the embedded pair of functions

function from<S, T, A, B>(anIso: Iso<S, T, A, B>): Iso<B, A, T, S> {
  return iso(anIso.to, anIso.from);
}

But there is one caveat, if I compose an Iso with another Iso it’ll only give me the composed function $applyOptic, so the original from and to are gone. If I want to preserve the Isomorphism when composing 2 Isos, I’ll have to modify the compose function to handle this special case. In fact, this what’s done in the actual implementation.

Since now we have 3 optic types, normally we’d have to write 9 overloads for compose but as we already saw in the previous post, we need only 3 overloads (since every Iso is a Lens and a Traversal).

function compose<S, T, A, B, X, Y>(
  parent: Iso<S, T, A, B>,
  child: Iso<A, B, X, Y>
): Iso<S, T, X, Y>;
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>;

We don’t need to modify the definition of over since it takes the most general type (Traversal).

Prisms

The definition of Prisms follows the same path. The Haskell definition is

type Prism s t a b = forall p f.(Choice p, Applicative f) => p a (f b) -> p s (f t)

It’s the same as Isos except we use Choice in place of Profunctor. Choice is also a Profunctor but extends it with additional functions to deal with Sum types like Either (you can read the full story here).

The concrete representation for Prisms is

data CPrism s a = CPrism (s -> Either s a) (a -> s)
-- Polymorphic version
data CPrism s t a b = CPrism (s -> Either t a) (b -> t)

Again it’s the same as Iso except that instead of s -> a in Isos, we have now a s -> Either t a (while an Iso always succeeds in extracting an a from s, a Prism can fail in which case it returns an alternative t that short-circuits the function b -> t).

Since we need to preserve Prisms over composition, we’ll follow the similar trick we did with Isos.

type Either<A, B> = { type: "Left"; value: A } | { type: "Right"; value: B };

interface Prism<S, T, A, B> {
  readonly $type?: "Prism" & "Traversal";
  $applyOptic: (<FB, FT>(
    F: Applicative<B, T, FB, FT>,
    f: Fn<A, FB>,
    s: S
  ) => FT);
  match: (s: S) => Either<T, A>;
  build: (b: B) => T;
}

Notice the function takes an Applicative and not a Functor, we’ll see why in a minute.

prism function is used to construct a functional representation from a concrete one

function prism<S, T, A, B>(
  match: (s: S) => Either<T, A>,
  build: (b: B) => T
): Prism<S, T, A, B> {
  return {
    $applyOptic(F, f, s) {
      const eta = match(s);
      if (eta.type === "Left") {
        // here!!
        return F.pure(eta.value);
      } else {
        return F.map(build, f(eta.value));
      }
    },
    match,
    build
  };
}

F.pure(eta.value) explains why we need an Applicative. In case the match fails in extracting a value from S, we get a T (wrapped in Either), since we need to return an F<T> from T, the pure function from the Applicative interface allows us to wrap plain values into the Applicative context (In fact we don’t need the whole Applicative just the pure part, this restricted interface is sometimes called Pointed).

As for compose we need to add only one overload, if you consulted the implementation of compose linked in the previous section, you’ve already seen that there is also a special case analysis for composing 2 prisms.

function compose<S, T, A, B, X, Y>(
  parent: Prism<S, T, A, B>,
  child: Prism<A, B, X, Y>
): Iso<S, T, X, Y>;

So far, it seems we have typings for the 4 optics, Remaining:

Add typing for accessor functions view, preview and co
I’ll have to figre Something for Getters
Proxies

Isomorphisms

Prisms

Links