Pointwise Lenses
Lenses are a current hot topic in the Haskell community, with a bunch of packages providing implementations (data-accessor, fclabels, lens, amongst others). Although we will recall definitions, this post is not meant as an introduction to lenses. If you have not worked with lenses before, the talk from Simon Peyton Jones or the blog post by Sebastiaan Visser about fclabels are good starting points.
In this blog post we will propose a generalization to the lens representation used in fclabels
and in many other packages (with various minor variations); we will consider the relation to the representation used in lens
in a separate section.
If you wanted to follow along, this is the header I am using:
{-# LANGUAGE FlexibleInstances, RankNTypes, TupleSections #-}
import Prelude hiding ((.), id, const, curry, uncurry)
import Control.Arrow
import Control.Applicative
import Control.Category
import Control.Monad
import Control.Monad.Free
import Control.Monad.Trans.Class
import Data.Functor.Identity
import Data.Functor.Compose
import Data.Traversable
import qualified Data.Traversable as Traversable
-- We define some Show instances just for the examples
instance Show a => Show (Compose [] Identity a) where
show (Compose a) = show a
instance Show a => Show (Compose [] (Compose [] Identity) a) where
show (Compose a) = show a
instance Show a => Show (Identity a) where
show (Identity a) = show a
Basics
A lens from a to b is a way to get a b from an a, and to modify an a given a modification of b:
data Lens a b = Lens {
lensGet :: a -> b
lensModify :: (b -> b) -> (a -> a)
, }
A simple example is a lens for the first component of a pair:
lensFst :: Lens (a, b) a
= Lens fst first lensFst
Importantly, lenses can be composed—they form a category:
instance Category Lens where
id = Lens id id
Lens g m . Lens g' m' = Lens (g . g') (m' . m)
Motivation
Suppose we have a lens from somewhere to a list of pairs:
lensFromSomewhere :: Lens Somewhere [(Int, Char)]
We would like to be able to somehow compose lensFromSomewhere
with lensFst
to get a lens from Somewhere
to [Int]
. The obvious thing to do is to try and define
mapLens :: Lens a b -> Lens [a] [b]
Lens g m) = Lens (map g) _ mapLens (
The getter is easy enough: we need to get a [b]
from a [a]
, and we have a function from b -> a
, so we can just map. We get stuck in the modifier, however: we need to give something of type
-> [b]) -> [a] -> [a] ([b]
given only a modifier of type (b -> b) -> (a -> a)
, and there is simply no way to do that.
If you think about it, there is a conceptual problem here too. Suppose that we did somehow manage to define a lens of type
weirdLens :: Lens [(Int, Char)] [Int]
This means we would have a modifier of type
weirdModify :: ([Int] -> [Int]) -> [(Int, Char)] -> [(Int, Char)]
What would happen if we tried
1 :) weirdModify (
to insert one Int
into the list? Which (Int, Char)
pair would we insert into the original list?
Pointwise lenses
What we wanted, really, is a lens that gave us a [Int]
from a [(Int, Char)]
, and that modified a [(Int, Char)]
given a modifier of type Int -> Int
: we want to apply the modifier pointwise at each element of the list. For this we need to generalize the lens datatype with a functor f:
data PLens f a b = PLens {
plensGet :: a -> f b
plensModify :: (b -> b) -> (a -> a)
, }
It is easy to see that PLens
is strictly more general than Lens
: every lens is also a Pointwise lens by choosing Identity
for f. Here’s a lens for the first component of a pair again:
plensFst :: PLens Identity (a, b) a
= PLens (Identity . fst) first plensFst
Note that the type of the modifier is precisely as it was before. As a simple but more interesting example, here is a lens from a list to its elements:
plensList :: PLens [] [a] a
= PLens id map plensList
You can think of plensList
as shifting the focus from the set as a whole to the elements of the set, not unlike a zipper.
Composition
How does composition work for pointwise lenses?
compose :: Functor f => PLens g b c -> PLens f a b -> PLens (Compose f g) a c
PLens g m) (PLens g' m') = PLens (Compose . fmap g . g') (m' . m) compose (
The modifier is unchanged. For the getter we have a getter from a -> f b
and a getter from b -> g c
, and we can compose them to get a getter from a -> f (g c)
.
As a simple example, suppose we have
exampleList :: [[(Int, Char)]]
= [[(1, 'a'), (2, 'b')], [(3, 'c'), (4, 'd')]] exampleList
Then we can define a lens from a list of list of pairs to their first coordinate:
exampleLens :: PLens (Compose [] (Compose [] Identity)) [[(a, b)]] a
= plensFst `compose` plensList `compose` plensList exampleLens
Note that we apply the plensList
lens twice and then compose with plensFst
. If we get
with this lens we get a list of lists of Int
s, as expected:
> plensGet exampleLens exampleList
1,2],[3,4]] [[
and we modify pointwise:
> plensModify exampleLens (+1) exampleList
2,'a'),(3,'b')],[(4,'c'),(5,'d')]] [[(
Category Instance
As we saw in the previous section, in general the type of the lens changes as we compose. We can see from the type of a lens where the focus is: shifting our focus from a list of list, to the inner lists, to the elements of the inner lists:
PLens Identity [[a]] [[a]]
PLens (Compose [] Identity) [[a]] [a]
PLens (Compose [] (Compose [] Identity)) [[a]] a
However, if we want to give a Category
instance then we need to be able to keep f constant. This means that we need to be able to define a getter of type a -> f c
from two getters of type a -> f b
and b -> f c
; in other words, we need f to be a monad:
instance Monad f => Category (PLens f) where
id = PLens return id
PLens g m . PLens g' m' = PLens (g <=< g') (m' . m)
This is however less of a restriction that it might at first sight seem. For our examples, we can pick the free monad on the list functor (using Control.Monad.Free
from the free
package):
plensFst' :: PLens (Free []) (a, b) a
= PLens (Pure . fst) first
plensFst'
plensList' :: PLens (Free []) [a] a
= PLens lift map plensList'
We can use these as before:
> plensGet id exampleList :: Free [] [[(Int, Char)]]
Pure [[(1,'a'),(2,'b')],[(3,'c'),(4,'d')]]
> plensGet plensList' exampleList
Free [Pure [(1,'a'),(2,'b')],Pure [(3,'c'),(4,'d')]]
> plensGet (plensList' . plensList') exampleList
Free [Free [Pure (1,'a'),Pure (2,'b')],Free [Pure (3,'c'),Pure (4,'d')]]
> plensGet (plensFst' . plensList' . plensList') exampleList
Free [Free [Pure 1,Pure 2],Free [Pure 3,Pure 4]]
Note that the structure of the original list is still visible, as is the focus of the lens. (If we had chosen [] for f instead of Free [], the original list of lists would have been flattened.) Of course we can still modify the list, too:
> plensModify (plensFst' . plensList' . plensList') (+1) exampleList
2,'a'),(3,'b')],[(4,'c'),(5,'d')]] [[(
Comparison to Traversal
An alternative representation of a lens is the so-called van Laarhoven lens, made popular by the lens package:
type LaarLens a b = forall f. Functor f => (b -> f b) -> (a -> f a)
(this is the representation Simon Peyton-Jones mentions in his talk). Lens
and LaarLens
are isomorphic: we can translate from Lens
to LaarLens
and back. This isomorphism is a neat result, and not at all obvious. If you haven’t seen it before, you should do the proof. It is illuminating.
A Traversal
is like a van Laarhoven lens, but using Applicative
instead of Functor
:
type Traversal a b = forall f. Applicative f => (b -> f b) -> (a -> f a)
Traversals have a similar purpose to pointwise lenses. In particular, we can define
tget :: Traversal a b -> a -> [b]
= getConst . t (Const . (:[]))
tget t
tmodify :: Traversal a b -> (b -> b) -> (a -> a)
= runIdentity . t (Identity . f) tmodify t f
Note that the types of tget
and tmodify
are similar to types of the getter and modifier of a pointwise lens, and we can use them in a similar fashion:
travFst :: LaarLens (a, b) a
= (, b) <$> f a
travFst f (a, b)
travList :: Traversal [a] a
= traverse
travList
exampleTrav :: Traversal [[(Int, Char)]] Int
= travList . travList . travFst exampleTrav
As before, we can use this traversal to modify a list of list of pairs:
> tmodify exampleTrav (+1) exampleList
2,'a'),(3,'b')],[(4,'c'),(5,'d')]] [[(
However, Traversals and pointwise lenses are not the same thing. It is tempting to compare the f parameter of the pointwise lens to the universally quantified f in the type of the Traversal, but they don’t play the same role at all. With pointwise lenses it is possible to define a lens from a list of list of pairs to a list of list of ints, as we saw; similarly, it would be possible to define a lens from a tree of pairs to a tree of ints, etc. However, the getter from a traversal only ever returns a single, flat, list:
> tget exampleTrav exampleList
1,2,3,4] [
Note that we have lost the structure of the original list. This behaviour is inherent in how Traversals work: every element of the structure is wrapped in a Const
constructor and are then combined in the Applicative
instance for Const
.
On the other hand, the Traversal
type is much more general than a pointwise lens. For instance, we can easily define
mapM :: Applicative m => (a -> m a) -> [a] -> m [a]
mapM = travList
and it is not hard to see that we will never be able to define mapM
using a pointwise lens. Traversals and pointwise lenses are thus incomparable: neither is more general than the other.
In a sense the generality of the Traversal
type is somewhat accidental, however: it’s purpose is similar to a pointwise lens, but it’s type also allows to introduce effectful modifiers. For pointwise lenses (or “normal” lenses) this ability is entirely orthogonal, as we shall see in the next section.
(PS: Yes, traverse
, travList
and mapM
are all just synonyms, with specialized types. This is typical of using the lens
package: it defines 14 synonyms for id
alone! What you take away from that is up to you :)
Generalizing further
So far we have only considered pure getters and modifiers; what about effectful ones? For instance, we might want to define lenses into a database, so that our getter and modifier live in the IO monad.
If you look at the actual definition of a lens in fclabels
you will see that it generalises Lens
to use arrows:
data GLens cat a b = GLens {
glensGet :: cat a b
glensModify :: cat (cat b b, a) a
, }
(Actually, the type is slightly more general still, and allows for polymorphic lenses. Polymorphism is orthogonal to what we are discussing here and we will ignore it for the sake of simplicity.) GLens
too forms a category, provided that cat
satisfies ArrowApply
:
instance ArrowApply cat => Category (GLens cat) where
id = GLens id app
GLens g m) . (GLens g' m') = GLens (g . g') (uncurry (curry m' . curry m))
(
const :: Arrow arr => c -> arr b c
const a = arr (\_ -> a)
curry :: Arrow cat => cat (a, b) c -> (a -> cat b c)
curry m i = m . (const i &&& id)
uncurry :: ArrowApply cat => (a -> cat b c) -> cat (a, b) c
uncurry a = app . arr (first a)
The ArrowApply
constraint effectively means we have only two choices: we can instantiate cat
with ->
, to get back to Lens
, or we can instantiate it with Kleisli m
, for some monad m, to get “monadic” functions; i.e. the getter would have type (isomorphic to) a -> m b
and the modifier would have type (isomorphic to) (b -> m b) -> (a -> m a)
.
Can we make a similar generalization to pointwise lenses? Defining the datatype is easy:
data GPLens cat f a b = GPLens {
gplensGet :: cat a (f b)
gplensModify :: cat (cat b b, a) a
, }
The question is if we can still define composition.
Interlude: Working with ArrowApply
I personally find working with arrows horribly confusing. However, if we are working with ArrowApply
arrows then we are effectively working with a monad, or so Control.Arrow tells us. It doesn’t however quite tell us how. I find it very convenient to define the following two auxiliary functions:
toMonad :: ArrowApply arr => arr a b -> (a -> ArrowMonad arr b)
= ArrowMonad $ app . (const (f, a))
toMonad f a
toArrow :: ArrowApply arr => (a -> ArrowMonad arr b) -> arr a b
= app . arr (\a -> (unArrowMonad (act a), ()))
toArrow act where
ArrowMonad a) = a unArrowMonad (
Now I can translate from an arrow to a monadic function and back, and I just write monadic code. Right, now we can continue :)
Category instance for GPLens
Since the type of the modifier has not changed at all from GLens
we can concentrate on the getters. For the identity we need an arrow of type cat a (f a)
, but this is simply arr return
, so that is easy.
Composition is trickier. For the getter we have two getters of type cat a (f b)
and cat b (f c)
, and we need a getter of type cat a (f c)
. As before, it looks like we need some kind of monadic (Kleisli) composition, but now in an arbitrary category cat. If you’re like me at this stage you will search Hoogle for
ArrowApply cat, Monad f) => cat a (f b) -> cat b (f c) -> cat a (f c) (
… and find nothing. So you try Hayoo and again, find nothing. Fine, we’ll have to try it ourselves. Let’s concentrate on the monadic case:
compM :: (Monad m, Monad f)
=> (a -> m (f b)) -> (b -> m (f c)) -> a -> m (f c)
= do fb <- f a
compM f g a _
so far as good; fb
has type f b
. But now what? We can fmap g
over fb
to get something of type f (m (f c))
, but that’s no use; we want that m
on the outside. In general we cannot commute monads like this, but if you are a (very) seasoned Haskell programmer you will realize that if f
happens to be a traversable functor then we can flip f
and m
around to get something of type m (f (f c))
. In fact, instead of fmap
and then commute we can use mapM
from Data.Traversable
to do both in one go:
compM :: (Monad m, Monad f, Traversable f)
=> (a -> m (f b)) -> (b -> m (f c)) -> a -> m (f c)
= do fb <- f a
compM f g a <- Traversable.mapM g fb
ffc _
Now we’re almost there: ffc
has type f (f c)
, we need somthing of type f c
; since f
is a monad, we can just use join
:
compM :: (Monad m, Monad f, Traversable f)
=> (a -> m (f b)) -> (b -> m (f c)) -> a -> m (f c)
= do fb <- f a
compM f g a <- Traversable.mapM g fb
ffc return (join ffc)
We can use the two auxiliary functions from the previous section to define Kleisli composition on arrows:
compA :: (ArrowApply cat, Monad f, Traversable f)
=> cat a (f b) -> cat b (f c) -> cat a (f c)
= toArrow (compM (toMonad f) (toMonad g)) compA f g
And now we can define our category instance:
instance (ArrowApply cat, Monad f, Traversable f)
=> Category (GPLens cat f) where
id = GPLens (arr return) app
GPLens g m . GPLens g' m' = GPLens (g' `compA` g)
uncurry (curry m' . curry m)) (
Note that the Traversable
constraint comes up now because we need to commute the “effects” of two monads: the monad f from the structure that we are returning (be it a list or a tree or..) and the monad m implicit in the arrow. In a Traversal these two are somehow more closely coupled. In particular, if we lift a (pure) pointwise lens PLens
to the more general GPLens
, by picking Identity
for f, the Traversable
constraint is trivially satisfied.