What are the differences between lenses and zippers?

Question

This is an example of using a zipper in Haskell:

data Tree a = Fork (Tree a) (Tree a) | Leaf a
data Cxt a = Top | L (Cxt a) (Tree a) | R (Tree a) (Cxt a)
type Loc a = (Tree a, Cxt a)

left :: Loc a -> Loc a
left (Fork l r, c) = (l, L c r)

right :: Loc a -> Loc a
right (Fork l r, c) = (r, R l c)

top :: Tree a -> Loc a 
top t = (t, Top)

up :: Loc a -> Loc a
up (t, L c r) = (Fork t r, c)
up (t, R l c) = (Fork l t, c)

upmost :: Loc a -> Loc a
upmost l@(t, Top) = l
upmost l = upmost (up l)

modify :: Loc a -> (Tree a -> Tree a) -> Loc a
modify (t, c) f = (f t, c)

This is an example of using a zipper in Clojure:

(use 'clojure.zip)
(require '[clojure.zip :as z])

user> (def z [[1 2 3] [4 [5 6] 7] [8 9]])
#'user/z

user> (def zp (zipper vector? seq (fn [_ c] c) z))
#'user/zp

user> zp
[[[1 2 3] [4 [5 6] 7] [8 9]] nil]

user> (-> zp down)
[[1 2 3] {:l [], :pnodes [[[1 2 3] [4 [5 6] 7] [8 9]]], :ppath nil, :r ([4 [5 6] 7] [8 9])}]

user> (first (-> zp down))
[1 2 3]

This is an example of using a Lens in Haskell:

data Person = P { name :: String 
                , addr :: Address 
                }
data Address = A { street :: String
                 , city :: String
                 , postcode :: String 
                 }

setPostcode :: String -> Person -> Person
setPostcode pc p = p { addr = addr p { postcode = pc }}

This is an example of using a Lens in Clojure.

(use 'lens)

(defrecord Address [street city postcode])
(defrecord Person [name age address])
(defrecord User [uid username identity password])

(def -postcode (mklens :postcode))
(def -city (mklens :city))
(def -street (mklens :street))
(def -address (mklens :address))
(def -age (mklens :age))
(def -name (mklens :name))
(def -uid (mklens :uid))
(def -username (mklens :username))
(def -identity (mklens :identity))
(def -password (mklens :password))

(-get -postcode home)

(-set -postcode home 500)

Now it seems both lenses and zippers are functional ways of traversing nested data structures.

My question is: What are the differences between lenses and zippers? Is one suited to a particular use case?

Answer 1

Zippers are akin to cursors: they allow to traverse trees in an ordered manner. Their usual operations are up, down, left, right and edit. (names may vary depending on impl)

Lenses are some sort of generalized keys (as in "keys of an associative datastructure"). The structure does not need to be ordered. Their usual operations are fetch and putback and are very similar to get and assoc. (names may vary depending on impl)

So as you see zippers are very much concerned about hierarchy (up/down) and order (left/right) while lenses are just about focusing (hence the name) on a piece of data, which may even be a projection (that is something that didn't existed on its own in the original structure).

For example in my ongoing work on Enliven, I have lenses that allow me to focus on a single class or style attribute in a HTML document.

Answer 2

Zippers are a variant of a datatype which unfolds the type into its local context and its extents in all directions. Atop a Zipper you can implement efficient motion and local update.

Lenses are first class examinations of a particular component of a data type. They focus on 0, 1, or many subparts of a data structure. Notably, your example of a lens in Haskell is not actually a lens—it's not first class.

It's perfectly reasonable to build a lens which focuses on some part of a zipper. For instance, an even simpler zipper than your examples is a Cons list zipper:

data Cons a = Empty | Cons a (Cons a)

data ConsZ a = ConsZ { lefts :: Cons a; here :: a; rights :: Cons a }

zip :: Cons a -> Maybe (ConsZ a)
zip Empty = Nothing
zip (Cons a as) = ConsZ Empty a as

unzip :: ConsZ a -> Cons a
unzip (ConsZ Empty a as) = Cons a as
unzip (ConsZ (Cons l ls) a as) = unzip (ConsZ ls) l (Cons a as)

We can incrementally modify this structure, moving the focus left or right:

moveRight :: ConsZ a -> Maybe (ConsZ a)
moveRight (ConsZ _ _ Empty) = Nothing
moveRight (ConsZ ls x (Cons a as)) =  ConsZ (Cons x ls) a as

and modify the current local point:

modify :: (a -> a) -> ConsZ a -> ConsZ a
modify f (ConsZ ls x rs) = ConsZ ls (f x) rs

We can also build lenses which access each part of the zipper structure:

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

_lefts :: Lens (ConsZ a) a
_lefts inj (ConsZ ls x rs) = (\ls -> ConsZ ls' x rs) <$> inj ls

_here :: Lens (ConsZ a) a
_here inj (ConsZ ls x rs) = (\x' -> ConsZ ls x' rs) <$> inj x

And even use them to build our zipper actions effectively:

over :: ((a -> Identity a) -> s -> Identity s) -> (a -> a) -> (s -> s)
over l f s = runIdentity (l (Identity . f) s)

modify = over _here

Ultimately, however, a lens is always a first class access to a particular point in a data structure. They can be composed, which gives the illusion of "motion" in a type, but if you really want that then you ought to make the zipper transform and use a real zipper type.

Answer 3

Lenses and zippers are not mutually exclusive ways of looking at the world. You can build a "movable focus" datatype on top of lenses, by reifying a chain of lenses as a type-aligned stack. Keeping track of the types you visited on your way down a structure means you know what types you'll be looking at when you go back up.

The API of this "movable focus" looks roughly like this:

empty :: Path (E :> a)
up :: Path (as :> a :> b) -> Path (as :> a)
down :: Path (as :> a) -> Traversal' a b -> Path (as :> a :> b)
left :: Path (as :> a :> b) -> Path (as :> a :> b)
right :: Path (as :> a :> b) -> Path (as :> a :> b)

flatten :: Path as -> Traversal' (Top as) (Bottom as)

Path is parameterised by a snoc-list of types. The type of the "current focus" of the Path is the rightmost element of the list.

Given a Path which focuses on an a in some structure, you can use down to append a Traversal' a b, to get back a Path which focuses on a b (namely, the first result of the Traversal). You can then go back up, which pops the most recently-appended Traversal to give you back a Path which focuses on an a again. left and right move the focus around inside the topmost Traversal.

You also need a way to turn a Path back into an actual Traversal, in order to access the actual value that your Path zooms in on. The flatten combinator does this. Top and Bottom are a pair of type families which find the leftmost and rightmost elements of a snoc-list, respectively.

---

So how's it implemented?

infixl 5 :>
data Snoc a = E | Snoc a :> a

type family Top as where
    Top (E :> a) = a
    Top (as :> _) = Top as
type family Bottom as where
    Bottom (_ :> a) = a

data Path as where
    Top :: Path (E :> a)
    Child :: Path (as :> a) -> Traversal' a b -> Int -> Path (as :> a :> b)

Path is a stack-shaped GADT. The Top constructor creates an empty Path - a path from any value to itself. The Child constructor focuses on a particular element of a Traversal - it contains the parent Path which focuses on an a, a Traversal from a to b, and an Int representing the particular element of the Traversal which the Path focuses on.

empty creates an empty path.

empty :: Path (E :> a)
empty = Top

up takes a non-empty path (guaranteed by the type) and pops the topmost Traversal from it.

up :: Path (as :> a :> b) -> Path (as :> a)
up (Child p _ _) = p

down takes a Traversal and appends it to a Path, focusing on the leftmost result of the Traversal.

down :: Path (as :> a) -> Traversal' a b -> Path (as :> a :> b)
down p t = Child p t 0

left and right don't change the level of the structure that you're focusing on - no adding or removing traversals from the stack - they just change which element of the topmost traversal the path points to.

left :: Path (as :> a :> b) -> Path (as :> a :> b)
left (Child p t n) = Child p t (n - 1)

right :: Path (as :> a :> b) -> Path (as :> a :> b)
right (Child p t n) = Child p t (n + 1)

flatten looks at each traversal in turn and uses elementOf to focus on a particular element of the traversal. It composes them all together using ..

flatten :: Path as -> Traversal' (Top as) (Bottom as)
flatten Top = id
flatten (Child p t n) = flatten p . elementOf t n

---

Path isn't a zipper, exactly. An important part of what makes a zipper a zipper is that you can efficiently view or edit the focus and its neighbours without traversing or rebuilding the whole thing. Path merely composes traversals without reference to a particular structure, so it's just as inefficient as working with whole traversals.

However, it's not a big leap from Path to a true zipper. The zippers package provides true zippers - cursors with efficient access to a focused part of an actual structure - generically, based on this idea of a type-aligned sequence of lenses. As you descend through a structure, the Zipper unpacks each traversal into a data structure rather like your Loc. Then when you go back upward it writes the new values back into the structure using the Traversal.