Search code examples
haskellfunctorapplicativehaskell-lens

Every Lens' is a Traversal'... how?

Control.Lens.Tutorial says:

type Traversal' a b = forall f . Applicative f => (b -> f b) -> (a -> f a) 
type Lens'      a b = forall f . Functor     f => (b -> f b) -> (a -> f a)

Notice that the only difference between a Lens' and a Traversal' is the type class constraint. A Lens' has a Functor constraint and Traversal' has an Applicative constraint. This means that any Lens' is automatically also a valid Traversal' (since Functor is a superclass of Applicative).

I simply don't follow the logical sequence here. We know that every Applicative is a Functor. From this, should it not follow, if at all, that every Traversal' is a Lens'? The tutorial however reaches the converse conclusion.

Solution

  • A Lens' works for all functors, which includes all applicative functors, so if a function g is a Lens', then g is also a Traversal'.

    A Traversal' works for all applicative functors, but not necessarily all functors. So if a function h is a Traversal', it is not necessarily a Lens'.

    (I'm not the one to describe this formally, but to me at least, it looks like the types are "contravariant" in their constraints. Lens' is a subtype of Traversal' precisely because Functor is a superclass of Applicative.)