# Uniplate is a Traversal

Posted on October 30, 2022 by Jack Kelly

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.