Haskell – lenses, fclabels, data-accessor – which library for structure access and mutation is better

data structureshaskelllensesrecord

There are at least three popular libraries for accessing and manipulating fields of records. The ones I know of are: data-accessor, fclabels and lenses.

Personally I started with data-accessor and I'm using them now. However recently on haskell-cafe there was an opinion of fclabels being superior.

Therefore I'm interested in comparison of those three (and maybe more) libraries.

Best Answer

There are at least 4 libraries that I am aware of providing lenses.

The notion of a lens is that it provides something isomorphic to

data Lens a b = Lens (a -> b) (b -> a -> a)

providing two functions: a getter, and a setter

get (Lens g _) = g
put (Lens _ s) = s

subject to three laws:

First, that if you put something, you can get it back out

get l (put l b a) = b 

Second that getting and then setting doesn't change the answer

put l (get l a) a = a

And third, putting twice is the same as putting once, or rather, that the second put wins.

put l b1 (put l b2 a) = put l b1 a

Note, that the type system isn't sufficient to check these laws for you, so you need to ensure them yourself no matter what lens implementation you use.

Many of these libraries also provide a bunch of extra combinators on top, and usually some form of template haskell machinery to automatically generate lenses for the fields of simple record types.

With that in mind, we can turn to the different implementations:

Implementations

fclabels

fclabels is perhaps the most easily reasoned about of the lens libraries, because its a :-> b can be directly translated to the above type. It provides a Category instance for (:->) which is useful as it allows you to compose lenses. It also provides a lawless Point type which generalizes the notion of a lens used here, and some plumbing for dealing with isomorphisms.

One hindrance to the adoption of fclabels is that the main package includes the template-haskell plumbing, so the package is not Haskell 98, and it also requires the (fairly non-controversial) TypeOperators extension.

data-accessor

[Edit: data-accessor is no longer using this representation, but has moved to a form similar to that of data-lens. I'm keeping this commentary, though.]

data-accessor is somewhat more popular than fclabels, in part because it is Haskell 98. However, its choice of internal representation makes me throw up in my mouth a little bit.

The type T it uses to represent a lens is internally defined as

newtype T r a = Cons { decons :: a -> r -> (a, r) }

Consequently, in order to get the value of a lens, you must submit an undefined value for the 'a' argument! This strikes me as an incredibly ugly and ad hoc implementation.

That said, Henning has included the template-haskell plumbing to automatically generate the accessors for you in a separate 'data-accessor-template' package.

It has the benefit of a decently large set of packages that already employ it, being Haskell 98, and providing the all-important Category instance, so if you don't pay attention to how the sausage is made, this package is actually pretty reasonable choice.

lenses

Next, there is the lenses package, which observes that a lens can provide a state monad homomorphism between two state monads, by definining lenses directly as such monad homomorphisms.

If it actually bothered to provide a type for its lenses, they would have a rank-2 type like:

newtype Lens s t = Lens (forall a. State t a -> State s a)

As a result, I rather don't like this approach, as it needlessly yanks you out of Haskell 98 (if you want a type to provide to your lenses in the abstract) and deprives you of the Category instance for lenses, which would let you compose them with .. The implementation also requires multi-parameter type classes.

Note, all of the other lens libraries mentioned here provide some combinator or can be used to provide this same state focalization effect, so nothing is gained by encoding your lens directly in this fashion.

Furthermore, the side-conditions stated at the start don't really have a nice expression in this form. As with 'fclabels' this does provide template-haskell method for automatically generating lenses for a record type directly in the main package.

Because of the lack of Category instance, the baroque encoding, and the requirement of template-haskell in the main package, this is my least favorite implementation.

data-lens

[Edit: As of 1.8.0, these have moved from the comonad-transformers package to data-lens]

My data-lens package provides lenses in terms of the Store comonad.

newtype Lens a b = Lens (a -> Store b a)

where

data Store b a = Store (b -> a) b

Expanded this is equivalent to

newtype Lens a b = Lens (a -> (b, b -> a))

You can view this as factoring out the common argument from the getter and the setter to return a pair consisting of the result of retrieving the element, and a setter to put a new value back in. This offers the computational benefit that the 'setter' here can recycle some of the work used to get the value out, making for a more efficient 'modify' operation than in the fclabels definition, especially when accessors are chained.

There is also a nice theoretical justification for this representation, because the subset of 'Lens' values that satisfy the 3 laws stated in the beginning of this response are precisely those lenses for which the wrapped function is a 'comonad coalgebra' for the store comonad. This transforms 3 hairy laws for a lens l down to 2 nicely pointfree equivalents:

extract . l = id
duplicate . l = fmap l . l

This approach was first noted and described in Russell O'Connor's Functor is to Lens as Applicative is to Biplate: Introducing Multiplate and was blogged about based on a preprint by Jeremy Gibbons.

It also includes a number of combinators for working with lenses strictly and some stock lenses for containers, such as Data.Map.

So the lenses in data-lens form a Category (unlike the lenses package), are Haskell 98 (unlike fclabels/lenses), are sane (unlike the back end of data-accessor) and provide a slightly more efficient implementation, data-lens-fd provides the functionality for working with MonadState for those willing to step outside of Haskell 98, and the template-haskell machinery is now available via data-lens-template.

Update 6/28/2012: Other Lens Implementation Strategies

Isomorphism Lenses

There are two other lens encodings worth considering. The first gives a nice theoretical way to view a lens as a way to break a structure into the value of the field, and 'everything else'.

Given a type for isomorphisms

data Iso a b = Iso { hither :: a -> b, yon :: b -> a }

such that valid members satisfy hither . yon = id, and yon . hither = id

We can represent a lens with:

data Lens a b = forall c. Lens (Iso a (b,c))

These are primarily useful as a way to think about the meaning of lenses, and we can use them as a reasoning tool to explain other lenses.

van Laarhoven Lenses

We can model lenses such that they can be composed with (.) and id, even without a Category instance by using

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

as the type for our lenses.

Then defining a lens is as easy as:

_2 f (a,b) = (,) a <$> f b

and you can validate for yourself that function composition is lens composition.

I've recently written on how you can further generalize van Laarhoven lenses to get lens families that can change the types of fields, just by generalizing this signature to

type LensFamily a b c d = forall f. Functor f => (c -> f d) -> a -> f b

This does have the unfortunate consequence that the best way to talk about lenses is to use rank 2 polymorphism, but you don't need to use that signature directly when defining lenses.

The Lens I defined above for _2 is actually a LensFamily.

_2 :: Functor f => (a -> f b) -> (c,a) -> f (c, b)

I've written a library that includes lenses, lens families, and other generalizations including getters, setters, folds and traversals. It is available on hackage as the lens package.

Again, a big advantage of this approach is that library maintainers can actually create lenses in this style in your libraries without incurring any lens library dependency whatsoever, by just supplying functions with type Functor f => (b -> f b) -> a -> f a, for their particular types 'a' and 'b'. This greatly lowers the cost of adoption.

Since you don't need to actually use the package to define new lenses, it takes a lot of pressure off my earlier concerns about keeping the library Haskell 98.

Related Topic