on

# Typing Optics (2): Traversals

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:

`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.- 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