StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>There are at least 4 libraries that I am aware of providing lenses.</p> <p>The notion of a lens is that it provides something isomorphic to </p> <pre><code>data Lens a b = Lens (a -> b) (b -> a -> a) </code></pre> <p>providing two functions: a getter, and a setter</p> <pre><code>get (Lens g _) = g put (Lens _ s) = s </code></pre> <p>subject to three laws:</p> <p>First, that if you put something, you can get it back out</p> <pre><code>get l (put l b a) = b </code></pre> <p>Second that getting and then setting doesn't change the answer</p> <pre><code>put l (get l a) a = a </code></pre> <p>And third, putting twice is the same as putting once, or rather, that the second put wins.</p> <pre><code>put l b1 (put l b2 a) = put l b1 a </code></pre> <p>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.</p> <p>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.</p> <p>With that in mind, we can turn to the different implementations:</p> <p><strong><em>Implementations</em></strong></p> <p><strong>fclabels</strong></p> <p><a href="http://hackage.haskell.org/package/fclabels" rel="noreferrer">fclabels</a> is perhaps the most easily reasoned about of the lens libraries, because its <code>a :-> b</code> can be directly translated to the above type. It provides a <a href="http://www.haskell.org/ghc/docs/6.12.2/html/libraries/base-4.2.0.1/Control-Category.html" rel="noreferrer">Category</a> instance for <code>(:->)</code> which is useful as it allows you to compose lenses. It also provides a lawless <code>Point</code> type which generalizes the notion of a lens used here, and some plumbing for dealing with isomorphisms.</p> <p>One hindrance to the adoption of <code>fclabels</code> 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) <code>TypeOperators</code> extension.</p> <p><strong>data-accessor</strong></p> <p>[Edit: <code>data-accessor</code> is no longer using this representation, but has moved to a form similar to that of <code>data-lens</code>. I'm keeping this commentary, though.]</p> <p><a href="http://hackage.haskell.org/package/data-accessor" rel="noreferrer">data-accessor</a> is somewhat more popular than <code>fclabels</code>, in part because it <em>is</em> Haskell 98. However, its choice of internal representation makes me throw up in my mouth a little bit.</p> <p>The type <code>T</code> it uses to represent a lens is internally defined as </p> <pre><code>newtype T r a = Cons { decons :: a -> r -> (a, r) } </code></pre> <p>Consequently, in order to <code>get</code> 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.</p> <p>That said, Henning has included the template-haskell plumbing to automatically generate the accessors for you in a separate '<a href="http://hackage.haskell.org/package/data-accessor-template" rel="noreferrer">data-accessor-template</a>' package.</p> <p>It has the benefit of a decently large set of packages that already employ it, being Haskell 98, and providing the all-important <code>Category</code> instance, so if you don't pay attention to how the sausage is made, this package is actually pretty reasonable choice.</p> <p><strong>lenses</strong></p> <p>Next, there is the <a href="http://hackage.haskell.org/packages/archive/lenses/0.1.4/doc/html/Data-Lenses.html" rel="noreferrer">lenses</a> package, which observes that a lens can provide a state monad homomorphism between two state monads, by definining lenses directly <em>as</em> such monad homomorphisms.</p> <p>If it actually bothered to provide a type for its lenses, they would have a rank-2 type like:</p> <pre><code>newtype Lens s t = Lens (forall a. State t a -> State s a) </code></pre> <p>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 <code>Category</code> instance for lenses, which would let you compose them with <code>.</code>. The implementation also requires multi-parameter type classes.</p> <p>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.</p> <p>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.</p> <p>Because of the lack of <code>Category</code> instance, the baroque encoding, and the requirement of template-haskell in the main package, this is my least favorite implementation.</p> <p><strong>data-lens</strong></p> <p>[Edit: As of 1.8.0, these have moved from the comonad-transformers package to data-lens]</p> <p>My <a href="http://hackage.haskell.org/package/data-lens" rel="noreferrer"><code>data-lens</code></a> package provides lenses in terms of the <a href="http://hackage.haskell.org/packages/archive/comonad-transformers/1.5.2.6/doc/html/Control-Comonad-Trans-Store-Lazy.html" rel="noreferrer">Store</a> comonad.</p> <pre><code>newtype Lens a b = Lens (a -> Store b a) </code></pre> <p>where</p> <pre><code>data Store b a = Store (b -> a) b </code></pre> <p>Expanded this is equivalent to</p> <pre><code>newtype Lens a b = Lens (a -> (b, b -> a)) </code></pre> <p>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 <code>fclabels</code> definition, especially when accessors are chained.</p> <p>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 <code>l</code> down to 2 nicely pointfree equivalents:</p> <pre><code>extract . l = id duplicate . l = fmap l . l </code></pre> <p>This approach was first noted and described in Russell O'Connor's <a href="http://front.math.ucdavis.edu/1103.2841" rel="noreferrer"><code>Functor</code> is to <code>Lens</code> as <code>Applicative</code> is to <code>Biplate</code>: Introducing Multiplate</a> and was <a href="http://patternsinfp.wordpress.com/2011/01/31/lenses-are-the-coalgebras-for-the-costate-comonad/" rel="noreferrer">blogged about based on a preprint</a> by Jeremy Gibbons.</p> <p>It also includes a number of combinators for working with lenses strictly and some stock lenses for containers, such as <code>Data.Map</code>.</p> <p>So the lenses in <code>data-lens</code> form a <code>Category</code> (unlike the <code>lenses</code> package), are Haskell 98 (unlike <code>fclabels</code>/<code>lenses</code>), are sane (unlike the back end of <code>data-accessor</code>) and provide a slightly more efficient implementation, <a href="http://hackage.haskell.org/package/data-lens-fd" rel="noreferrer"><code>data-lens-fd</code></a> 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 <a href="http://hackage.haskell.org/package/data-lens-template" rel="noreferrer"><code>data-lens-template</code></a>.</p> <p><strong><em>Update 6/28/2012: Other Lens Implementation Strategies</em></strong></p> <p><strong>Isomorphism Lenses</strong></p> <p>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'.</p> <p>Given a type for isomorphisms</p> <pre><code>data Iso a b = Iso { hither :: a -> b, yon :: b -> a } </code></pre> <p>such that valid members satisfy <code>hither . yon = id</code>, and <code>yon . hither = id</code></p> <p>We can represent a lens with:</p> <pre><code>data Lens a b = forall c. Lens (Iso a (b,c)) </code></pre> <p>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.</p> <p><strong>van Laarhoven Lenses</strong></p> <p>We can model lenses such that they can be composed with <code>(.)</code> and <code>id</code>, even without a <code>Category</code> instance by using</p> <pre><code>type Lens a b = forall f. Functor f => (b -> f b) -> a -> f a </code></pre> <p>as the type for our lenses.</p> <p>Then defining a lens is as easy as:</p> <pre><code>_2 f (a,b) = (,) a <$> f b </code></pre> <p>and you can validate for yourself that function composition is lens composition.</p> <p>I've recently written on how you can further <a href="http://comonad.com/reader/2012/mirrored-lenses/" rel="noreferrer">generalize van Laarhoven lenses</a> to get lens families that can change the types of fields, just by generalizing this signature to</p> <pre><code>type LensFamily a b c d = forall f. Functor f => (c -> f d) -> a -> f b </code></pre> <p>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.</p> <p>The <code>Lens</code> I defined above for <code>_2</code> is actually a <code>LensFamily</code>.</p> <pre><code>_2 :: Functor f => (a -> f b) -> (c,a) -> f (c, b) </code></pre> <p>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 <a href="http://hackage.haskell.org/package/lens" rel="noreferrer"><code>lens</code></a> package.</p> <p>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 <code>Functor f => (b -> f b) -> a -> f a</code>, for their particular types 'a' and 'b'. This greatly lowers the cost of adoption.</p> <p>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.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload