How to implement a Lens like Getter for a specific type?

Given the general Getter type

type Getter s a = forall f. (Contravariant f, Functor f) => (a -> f a) -> s -> f s

how would I implement a getter for, say, a pair tuple? I guess the above type represents a partially applied function and the missing part is exactly what confuses me.

Beyond that I don't understand the contravariant constraint. It's probably there to make the type more lens like, but isn't functor enough?

Solution

In the type Getter s a, type s denotes the "object" that somehow "contains" a value of type a, which the getter can somehow "extract" from it.

If you want to implement a getter for a pair, then your s = (x, y), and your a would be either x or y, depending on which element you're extracting. Let's say for clarity that you're extracting the first element. Then a = x.

Ok, so your function would look like this:

firstElementGetter :: Getter (x, y) x

Now, if we expand the definition of Getter, we get:

firstElementGetter :: (blah-blah) => (x -> f x) -> (x, y) -> f (x, y)
firstElementGetter h (x, y) = ...

This means that your function gets two parameters: (1) a function h that can "wrap" an x in functor f, and (2) a tuple (x, y); and it needs to return a tuple (x, y) wrapped in the functor f. Let's see if we can do that.

First, we have a function h that takes a parameter of type x. Conveniently, we also have an x of that very type. Let's apply it: h x. The result of that has type f x. How can we turn that into f (x, y)?

Well, the very thing of a Functor is that you can map over it. So what function can we map over f x to obtain f (x, y)? Such function obviously needs to have a type x -> (x, y) - and behold! We have all the parts to construct such a function! We can take our existing y and recombine it into the tuple: \xx -> (xx, y).

Now we have everything to fulfill the contract of the getter:

firstElementGetter :: (blah-blah) => (x -> f x) -> (x, y) -> f (x, y)
firstElementGetter h (x, y) = fmap (\xx -> (xx, y)) (h x)

This is, at root, how all optics work - be they getters, traversals, prisms, or whatever. The consumer can then make them do different things by choosing the right functor f and the right wrapping function h.

For example, the consumer can use your getter to "extract" the first element from a tuple by choosing this functor:

data Const a b = Const a

instance Functor (Const a) where
    fmap f (Const a) = Const a

Notice how it completely ignores the type b. Doesn't actually "wrap" a value of it, and fmap implementation doesn't touch it either. You might say it's a "fake" functor. We're going to use that to our advantage!

For function h we're going to choose Const. It fits the type, because Const :: x -> Const x foo for any foo, which happens to be compatible with x -> Const x x, which matches the required type x -> f x when f = Const x. I know, this is a bit mind-blowing, but bear with me.

Now, if h = Const, our getter will dutifully call h x, which would return Const x, which the getter will fmap over, but since our definition of fmap ignores its first argument, the result of fmap will still be the very same Const x, which the getter will then return. Now, all we need to do is just unwrap it, and we're done!

getFirst :: (x, y) -> x
getFirst pair = 
    let (Const x) = firstElementGetter Const pair
    in x

The Contravariant part is a bit of a clever type-level hackery. See, when a functor f is not only Functor, but also Contravariant, it has to have the shape of the Const type above - i.e. it cannot "wrap" a value of its type parameter inside.

Functor can be thought of as a thing that "produces" (or "contains") values, while Contravariant is a thing that "consumes" values. If a "wrapper" type has to be both, the only way to implement it is to only pretend to "consume" or "produce" values, but ignore them behind the scenes. I understand this is not a very clear explanation, but I can't do any better. Just try to implement a type like that, you'll see.

So Getter is given this weird constraint just as a way to ensure that the only thing it can do is "get" a value, never "set" or "transform" it.

The simplest implementation of a getter would be just s -> a.
A less simple implementation would be (a -> x) -> s -> x - in continuation-passing style, but equivalent to the previous one.
A yet less simple implementation would be (a -> Const x a) -> s -> Const x s - I just replaced both a with Const x foo with different foo, but it's still equivalent to the previous one.

While the first (simplest) definition would do for the actual getting, the last definition has the advantage of having a signature compatible with other lenses, thus making it possible to use such getter in lens compositions.