Uniplate is a Traversal

While writing code to rewrite some Dhall syntax trees, I noticed a cool connection between the core uniplate operation and optics. This will be old news to advanced lens users, but I think it’s worth pointing out. The uniplate package’s original uniplate :: Uniplate a => a -> ([a], [a] -> a) is an early attempt at a “traversal” optic, properly expressed in lens by plate :: Plated a => Traversal' a a.

The uniplate library provides low-boilerplate ways to query and rewrite self-similar data structures; the uniplate function from class Uniplate a is its fundamental operation. Let’s look at the original definition, from the 2007 paper Uniform Boilerplate and List Processing:

class Uniplate a where
  uniplate :: a -> ([a], [a] -> a)

-- An example data type and instance
data Expr = Lit Int | Negate Expr | Add Expr Expr

instance Uniplate Expr where
  uniplate (Lit i) = ([], \[] -> Lit i)
  uniplate (Negate e) = ([e], \[e'] -> Negate e')
  uniplate (Add e1 e2) = ([e1, e2], \[e1', e2'] -> Add e1' e2')

uniplate extracts from a value of type T any immediate children of type T, and provides a function to reassemble the original structure with new children. From this, we can define operations like transform, which applies a function everywhere it can be applied, in a bottom-up way:

transform :: Uniplate a => (a -> a) -> a -> a
transform f a = rebuild $ map (transform f) as
  where (as, rebuild) = uniplate a

Look closely at the type of the uniplate operation: it extracts [a] from a structure, and provides a function to assign a new [a] into a structure. This is exactly what a get/set lens does:

-- As a record:
data GetSetLens s a = GetSetLens
  { get :: s -> a
  , set :: s -> a -> s
  }

-- As a type alias for a tuple:
type GetSetLens s a = (s -> a, s -> a -> s)

-- Factor out the common 's' parameter:
type GetSetLens s a = s -> (a, a -> s)

class Uniplate a where
  uniplate :: GetSetLens a [a]

The example Uniplate instance shows us that this lens requires careful use: we must return a list of exactly the same length as the one we are given. Now that we’ve noticed a connection between Uniplate and lenses, is there a better optic we could use? Yes — traversals are optics that focus zero or more targets, so we could rebuild the uniplate library on top of an operation that provides a Traversal' a a. This is what lens does with Control.Lens.Plated:

class Plated a where
  plate :: Traversal' a a

If you are unable to define a Plated instance on a type (e.g., you do not want to introduce an orphan instance on a type you do not own), lens also provides a helper, uniplate :: Data a => Traversal' a a. Interestingly, lens also provides a partsOf combinator which collects the foci of an optic into a list:

-- Usable as:
partsOf :: Iso' s a       -> Lens' s [a]
partsOf :: Lens' s a      -> Lens' s [a]
partsOf :: Traversal' s a -> Lens' s [a]
partsOf :: Fold s a       -> Getter s [a]
partsOf :: Getter s a     -> Getter s [a]

-- The real type signature:
partsOf :: Functor f => Traversing (->) f s t a a -> LensLike f s t [a] [a]

Its haddock even says that it “resembles an early version of the uniplate (or biplate) type” and that “you really should try to maintain the invariant of the number of children in the list”.

And that brings us full circle; we can get a van Laarhoven version of our original uniplate lens using Data.Data.Lens.uniplate:

Data.Data.Lens.uniplate :: Data a => Traversal' a a
partsOf Data.Data.Lens.uniplate :: Data a => Lens' a [a]

This is one of my favourite things about programming in Haskell: seeing that library authors have carefully refined concepts like “view the self-similar children of a structure” into ever more powerful and composable forms, and being able to notice the different stages in that evolution.