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.

- We started with
`[User]`

. - We can't directly apply the
`posts`

lens, since that requires a`User`

. `traverse`

changes to focus on`User`

inside the`[User]`

.`traverse.posts`

now works, since our target is just a`User`

, so we can compose to get a lens of`traverse.posts`

.

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

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

#### See also

- Lens Tutorial - Introduction (part 1)
- Foldable and Traversable
- Building Monad Transformers - Part 1
- Mutable State in Haskell
- Using Phantom Types in Haskell for Extra Safety - Part 2

#### Liked this blog post? Share it!

comments powered by Disqus