Lenses, Folds, and Traversals: Haskell Meet-up

The Google San Francisco office hosted a talk by Edward Kmett called "Lenses, Folds, and Traversals" which was well attended by the local Bay Area Haskell Users group as well as Google employees on Thursday, October 18,  2012. Almost 100 people turned up to hear why the power is in the dot (as explained by Gavin Bierman, Erik Meijer and Wolfram Schulte in their 2002 paper "The essence of data access in Cω: The power is in the dot"). This paper pushed the boundaries of our understanding of how to build data-access features for programming languages that go beyond naıve access via simple APIs) by greatly generalizing member access (e.g. over choice types). Although this paper resorted to the creation of a new language to support innovations in data-access (and concurrency) this talk by Edward showed how generalized member-access could be achieved using just a regular library in Haskell as exemplified by his lens library.

Edward presented a beautifully crafted set of APL-like combinators that allow programmers to navigate through structured data and perform generalized operations for access and modification. The core concept in the library is of a lens which groups together a 'setter' and a 'getter':

data Lens a b = Lens { set :: a -> b -> a
                    , view :: a -> b
                    }

where informally the idea is that a lens give you a way to extract from an object (of type a) some information (of type b) by using the view function and also to let you perform the reverse i.e. using the set function, take an object of type a and a value of type b and return a new object of type a with the sub-information about type b suitably incorporated. The actual definition of lens in Edward's library is different (it is cast in terms of a functor). Lenses are essentially composable functional references. The talk showed how lenses can be composed using the ordinary function composition operator (.) in Haskell. The talk then illustrated a scheme for performing lens-based folds and traversals in a highly composable manner and climaxed with the impossible: the overloading of function application. For the grand finale, Edward explained how lenses are just the functors, foldables, traversals and functions that (hard-core Haskell) people already know how to use.

Here is a specific example which shows the result of computing an expression using Haskell's command-line interpreter:

ghci> over (mapped._2) succ [(1,2),(3,4)]
[(1,3),(3,5)]

Informally, here we see the successor function succ applied to the second element of every structure contained by the top-level structure i.e. 2 is mapped to 3 and 4 is mapped to 5. The over function is used to modify the target of a lens (or all the targets of setters or traversals) with a function. The mapped function is a setter that can be used to map over all the values in a functor. The _2 operation accesses the second field of a tuple.

You can view Edward's slides and an earlier talk on the subject. Alternatively, @PLT_Borat could have just told you that "Costate Comonad Coalgebra is the equivalent of Java's member variable update technology for Haskell".

By Satnam Singh, Google