Jakub Arnold's Blog

Lens Tutorial - Stab & Traversal (Part 2)

In the first article in the series about lenses, we’ve looked at the motivation behind the lens library, and we also derived the basic type of Lens s a.

In this article we’ll go deeper and explain the reasoning beheind the more generic Lens s t a b type. We’ll also take a look at how we can get a multi focus lens using a Traversal.

Just to reiterate, here’s how looks the type we derived in the previous article.

type Lens s a = forall f. Functor f => (a -> f a) -> s -> f s

What we’ll do here is further generalize it so that we can change the type of the focus.

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

Now you might be thinking that four type parameters is a bit much, but bear with me here. If we compare the our Lens s t a b to something like fmap, we can see a bit resemblance there.

λ> :t fmap
:: Functor f => (a -> b) -> f a -> f b

Much like a function a -> b can be applied on f a to change it’s structure to become an f b. In the same way a Lens s t a b allows us to change a to b, which changes the shape of s to t. We can also read it as: A lens allows us to look at a inside an s, and if we can also replace the a with a b, which will make the s into t. Here’s a simple example using tuples.

λ> :t ("hello", "world")
:: (String, String)
λ> :t over _1 length ("hello", "world")
:: (Int, String)
λ> over _1 length ("hello", "world")
(5,"world")

Initially we started out with s :: (String, String) and ended up with t :: (Int, String) by applying a String -> Int function on the first element of the tuple. The specific type of the _1 lens in this case would be Lens (String, String) (Int, String) String Int.

It’s important to understand that all of the derivations we made for Lens s a still hold for Lens s t a b, since it’s just a bit more generic. In fact you can write the following (as it is done in the lens library.)

type Lens' s a = Lens s s a a

I’ll leave it as an exercise to the reader to go through all of the steps we did previously and use Lens s t a b instead.

Traversal - the multi foci lens

Disclaimer: When I say list I really mean Data.Traversable, however using a list makes things easier to understand. I also wrote an article on Traversable if you’re unfamiliar with it.

While the lenses we’ve established so far are useful, they do have their shortcomings. One example are nested lists, let’s see an example.

data User = User String [Post] deriving Show
data Post = Post String deriving Show

Now if I give you a list of users and ask you to give me all of the names of their posts, you’ll probably not be very happy about that. Not that it’s difficult, but some work involved.

With Traversal and traverse we can focus on all elements of a list and do this in a single step. But first, let’s define us some lenses to work with the types. In a real world application we’d use Template Haskell to generate the lenses automatically, but for the sake of exercise let’s do it manually here.

posts :: Lens' User [Post]
posts f (User n p) = fmap (\p' -> User n p') (f p)

title :: Lens' Post String
title f (Post t) = fmap Post (f t)

We got two lenses, one that focuses on User’s posts, and another one for the post’s title. Let’s also define us some test data to play around with.

users :: [User]
users = [User "john" [Post "hello", Post "world"], User "bob" [Post "foobar"]]

Now lets open up GHCi, load these definitions file, import Control.Lens and see what we can do.

λ> view (traverse.posts) users
[Post "hello",Post "world",Post "foobar"]

This seems to do what we want, we gave it a list of users and pulled out a list of posts. Note that we used traverse every time the current focus was a list, which is just in the first step on users.

The next step is to go deeper to fetch the post title. If you look at the type of our current lens traverse.posts, you’ll see that it focuses on [Posts].

λ> :t traverse.posts
:: (Traversable t, Applicative f) => 
   [Post] -> f [Post]) -> t User -> f (t User)

In order to reach out to each post, we need to use traverse again. You can think of traverse as something that allows us to focus on multiple targets at once, in a similar way that map allows us to apply a function to all elements of a list.

It is also important to note here that the lens composition works backwards than what is usual in Haskell. You can think of it as a sort of object accessor notation in an object-oriented language, where you’d do foo.bar.baz.

Just to make this point crystal clear, here’s how function composition works for regular functions. The *2 gets applied before the +1.

λ> ((+1).(*2)) 1
3

With lenses it goes the other way and the traverse goes before the posts lens.

Traversing deeper and deeper

Our previous example worked out just as we wanted, so let’s try to go deeper and actually fetch the title of each Post from our users list.

λ> view (traverse.posts.traverse.title) users
"helloworldfoobar"

Huh? This isn’t what we wanted at all! Lens must be completely broken?!!?1!

Much like we got [Post] from traverse.posts, it would make sense to get [String] from traverse.posts.traverse.title, but instead we got one big String with all of the titles combined. In order to understand why this is happening we need to look more closely at how traverse works.

Here’s a simpler example that we can use to reproduce what we had previously.

λ> view traverse ["hello", "world"]
"helloworld"

The reason for this behavior is that if we use view together with traverse it will use the Monoid instance of our focus and smash them together.

Let’s see how this works by inlining the definition of view.

view :: Lens s a -> s -> a
view ln s = getConst $ ln Const s

Inlining the arguments we get the following.

λ> view traverse ["hello", "world"]
"helloworld"
λ> getConst $ traverse Const ["hello", "world"]
"helloworld"

We can already see that it is not the lens library that does the magic, it’s the traverse combined with Const. The view just picks the Const applicative to be used with the traverse function.

Now moving on to inlining definition of traverse, which for a list look like following.

traverse _ [] = pure []
traverse f (x:xs) = (:) <$> f x <*> traverse f xs

Since this is a recursive function and our list has two elements, we need to inline it in multiple steps.

-- Inlined the arguments into the definition.
(:) <$> Const "hello" <*> traverse f ["world"]
-- First recursive call to traverse inlined.
(:) <$> Const "hello" <*> ((:) <$> Const "world" <*> traverse f [])
-- Second recursive call to traverse inlined.
(:) <$> Const "hello" <*> ((:) <$> Const "world" <*> pure [])

This whole expression will return a type of Const String [a], from which we need to extract the String using getConst, as shown above.

λ> getConst $ (:) <$> Const "hello" <*> ((:) <$> Const "world" <*> pure [])
"helloworld"

As you can see we’re still getting the same result as in the case of view traverse ["hello", "world"], which means we’re on the right track. But this still doesn’t explain why are the two strings being concatenated together.

Const as a Monoid

To understand the concatenation we need to take a look at how the Applicative instance for Const is implemented, but let’s think about this first.

Const a b acts as an Functor that pretends to contain a value of type b, but in reality hides a value of type a. That’s why if we have Const Int String and fmap a function of type String, we’ll get a Const Int Int, even though there was no actual value for String.

λ> let a = Const 3 :: Const Int String
λ> :t a
:: Const Int String
λ> :t fmap length a
:: Const Int Int
λ> getConst $ fmap length a
3

If you’re having trouble understanding this, check out my first article on Lenses which explains this in a bit more detail.

Now we’re faced with the problem of implementing an Applicative instance. The problem being that Applicative defines pure :: a -> f a, which takes a value and lifts it into the Applicative. But because we’re working with Const, there is no actual value being lifted, as in the case of a Functor where we didn’t really apply the function.

Const Int String does not contain any String, it only contains the Int. That’s why if we do pure 3 to get back a Const String Int, we must throw away the 3 and somehow create a String to hide it into the Const. We need to have a way to create a value for the type we’re hiding. But how do we do that when we have nothing?

We use a Monoid and mempty!

instance Monoid m => Applicative (Const m) where
    pure _ = Const mempty

We just throw away the argument to pure and create a new Const hiding the value returned by mempty, which for a String in our previous example would be "".

λ> getConst $ (pure 3 :: Const String Int)
""

Next up is the definition of <*>, which is rather simple now that we know that our hidden value is a Monoid. The way that <*> works is that it takes two Applicatives and smashes them together. In a general case it would mean applying the function in the first one to the value in the second one, but because our Const is just pretending to have a function while it has none, we do not need to apply it. We just need to find a way to combine our two hidden monoidal values, which is exactly where mappend will come to play.

We simply extract the hidden values and mappend them together to create a new Const.

instance Monoid m => Applicative (Const m) where
    pure _ = Const mempty
    Const f <*> Const x = Const (f `mappend` x)

Intuition behind view traverse

Finally we can get back to our traverse example and understand why it does what it does. We ended up with the following expression.

(:) <$> Const "hello" <*> ((:) <$> Const "world" <*> pure [])

With the recently gained knowledge we can see that it doesn’t matter what function we apply to our Const. In this case it is (:) but it might as well be undefined.

λ> getConst $ undefined <$> Const "hello"
"hello"

This means that the whole (:) <$> has absolutely no meaning. It’s just there so that our Const "hello" can take on a type of a function application, so that we can use <*>. In fact the only thing that does something is the <*> combinator, which calls mappend on the hidden values, but let’s take this step by step.

First we replace pure [] with the actual value it returns in this case.

(:) <$> Const "hello" <*> ((:) <$> Const "world" <*> Const "")

Next we can evaluate the expression in the parentheses, which if you look at our definition of Const will just reduce to the following.

Const $ "world" `mappend` ""

Which evaluates to just Const "world". Now we’re left with the following.

(:) <$> Const "hello" <*> Const "world"

Which again just ends up being:

Const $ "hello" `mappend` "world"

Which evaluates to Const "helloworld". Our initial expression applied getConst to the result of this expression, which would just yield "helloworld".

λ> getConst $ Const $ "hello" `mappend` "world"
"helloworld"

There we go, now we have a full understanding of why view traverse requires the traversed values to be a Monoid.

In the next article we’ll focus on some other use cases for traverse and how to use it with combinators like toListOf, etc.

Related
Haskell · Lens