When manipulating immutable datastructures, what's the difference between Clojure's assoc-in and Haskell's lenses?

Question

I need to manipulate and modify deeply nested immutable collections (maps and lists), and I'd like to better understand the different approaches. These two libraries solve more or less the same problem, right? How are they different, what types of problem is one approach more suitable for over the other?

Clojure's assoc-in
Haskell's lens

Answer 1

Clojure's assoc-in lets you specify a path through a nested data struture using integers and keywords and introduce a new value at that path. It has partners dissoc-in, get-in, and update-in which remove elements, get them without removal, or modify them respectively.

Lenses are a particular notion of bidirectional programming where you specify a linkage between two data sources and that linkage lets you reflect transformations from one to the other. In Haskell this means that you can build lenses or lens-like values which connect a whole data structure to some of its parts and then use them to transmit changes from the parts to the whole.

There's an analogy here. If we look at a use of assoc-in it's written like

(assoc-in whole path subpart)

and we might gain some insight by thinking of the path as a lens and assoc-in as a lens combinator. In a similar way you might write (using the Haskell lens package)

set lens subpart whole

so that we connect assoc-in with set and path with lens. We can also complete the table

set          assoc-in
view         get-in
over         update-in
(unneeded)   dissoc-in       -- this is special because `at` and `over`
                             -- strictly generalize dissoc-in

---

That's a start for similarities, but there's a huge dissimilarity, too. In many ways, lens is far more generic than the *-in family of Clojure functions are. Typically this is a non-issue for Clojure because most Clojure data is stored in nested structures made of lists and dictionaries. Haskell uses many more custom types very freely and its type system reflects information about them. Lenses generalize the *-in family of functions because they works smoothly over that far more complex domain.

First, let's embed Clojure types in Haskell and write the *-in family of functions.

type Dict a = Map String a

data Clj 
  = CljVal             -- Dynamically typed Clojure value, 
                       -- not an array or dictionary
  | CljAry  [Clj]      -- Array of Clojure types
  | CljDict (Dict Clj) -- Dictionary of Clojure types

makePrisms ''Clj

Now we can use set as assoc-in almost directly.

(assoc-in whole [1 :foo :bar 3] part)

set ( _CljAry  . ix 1 
    . _CljDict . ix "foo" 
    . _CljDict . ix "bar" 
    . _CljAry  . ix 3
    ) part whole

This somewhat obviously has a lot more syntactic noise, but it denotes a higher degree of explicitness about what the "path" into a datatype means, in particular it denotes whether we're descending into an array or a dictionary. We could, if we wanted, eliminate some of that extra noise by instantiating Clj in the Haskell typeclass Ixed, but it's hardly worth it at this point.

Instead, the point to be made is that assoc-in is applying to a very particular kind of data descent. It's more general than the types I laid out above due to Clojure's dynamic typing and overloading of IFn, but a very similar fixed structure like that could be embedded in Haskell with little further effort.

Lenses can go much further though, and do so with greater type safety. For instance, the example above is actually not a true "Lens" but instead a "Prism" or "Traversal" which allows the type system to statically identify the possibility of failing to make that traversal. It will force us to think about error conditions like that (even if we choose to ignore them).

Importantly that means that we can be sure when we have a true lens that datatype descent cannot fail—that kind of guarantee is impossible to make in Clojure.

We can define custom data types and make custom lenses which descend into them in a typesafe fashion.

data Point = 
  Point { _latitude  :: Double
        , _longitude :: Double
        , _meta      :: Map String String }
  deriving Show

makeLenses ''Point

> let p0 = Point 0 0
> let p1 = set latitude 3 p0
> view latitude p1
3.0
> view longitude p1
0.0
> let p2 = set (meta . ix "foo") "bar" p1
> preview (meta . ix "bar") p2
Nothing
> preview (meta . ix "foo") p2 
Just "bar"

We can also generalize to Lenses (really Traversals) which target multiple similar subparts all at once

dimensions :: Lens Point Double

> let p3 = over dimensions (+ 10) p0
> get latitude p3
10.0
> get longitude p3
10.0
> toListOf dimensions p3
[10.0, 10.0]

Or even target simulated subparts which don't actually exist but still form an equivalent description of our data

eulerAnglePhi   :: Lens Point Double
eulerAngleTheta :: Lens Point Double
eulerAnglePsi   :: Lens Point Double

---

Broadly, Lenses generalize the kind of path-based interaction between whole values and subparts of values that the Clojure *-in family of functions abstract. You can do a lot more in Haskell because Haskell has a much more developed notion of types and Lenses, as first class objects, widely generalize the notions of getting and setting that are simply presented with the *-in functions.