# Indexed `Plated`

## What is `Plated`

?

`lens`

provides `Plated`

, whose purpose is to help with the traversal of
*self-recursive* types, such as trees. The `Plated`

class itself is
straightforward:

```
class Plated a where
plate :: Traversal' a a
```

That is, given some value of type `a`

, how do we visit all of its immediate
self-similar children. A motivating example, taken directly from `Plated`

's
documentation, would be the following:

```
data Expr
= Val Int
| Neg Expr
| Add Expr Expr
instance Plated Expr where
plate f = \case
Val n -> pure $ Val n
Neg e -> Neg <$> f e
Add x y -> Add <$> f x <*> f y
```

Using the combinators provided alongside `Plated`

, it is now easy to traverse
and transform this recursive structure without having to write the boiler*plate*
ourselves:

```
simplify :: Expr -> Expr
simplify = rewrite \case
Neg (Neg x) -> Just x
Neg (Val n) -> Just $ Val $ negate n
Add (Val 0) x -> Just x
Add x (Val 0) -> Just x
Add (Neg x) (Neg y) -> Just $ Neg $ Add x y
_ -> Nothing
```

A limitation of `Plated`

, however, is that the function that is expected by the
`Traversal`

only takes the value `a`

itself, without context: in our `simplify`

example above, the argument to `rewrite`

operates on *any* `Expr`

, without
knowing whether it is operating at the root of the expression, or at the very
bottom of it. And, in some cases, it could be useful to track where we are in
the larger data structure. For instance, while introspecting a JSON value, it
could be useful to know the path that led to the current inner value.

## Introducing `IndexedPlated`

This library introduces `IndexedPlated`

, which is just like `Plated`

but carries
around an "index" of the user's choosing. The definition of `IndexedPlated`

is
as follows:

```
class IndexedPlated i a where
iplate :: i -> IndexedTraversal' i a a
```

If we inline the type aliases (and simplify the result), the difference becomes
clearer:

```
plate :: ( a -> f b) -> s -> f t
iplate :: i -> (i -> a -> f b) -> s -> f t
```

`iplate`

takes an additional "starting index" on top of the root value, and the
given function also expects the index matching the given value.

This library also provides most of the combinators that accompany `Plated`

. All
of them are prefixed with `i`

, similarly to how `lens`

indicate indexed
functions (such as `iover`

).

For instance, for Aeson's `Value`

, we could write the following:

```
type Path = [Step]
data Step = Key Text | Index Int
instance IndexedPlated Path Value where
iplate parentPath f = \case
Object o -> fmap Object $
flip traverseWithKey o \key value ->
f (parentPath <> [Key key]) value
Array a -> fmap Array $
for (indexed a) \(index, value) ->
f (parentPath <> [Index index]) value
String s -> pure $ String s
Number x -> pure $ Number x
Bool b -> pure $ Bool b
Null -> pure Null
```

An example use of this would be to use the path for error reporting in a
recursive transformation of a value. For instance, this function attempts to
replace all strings starting with a `$`

by corresponding values from a lookup
table. Despite no recursion being present in this function, the underlying use
of `IndexedPlated`

means that all such possible expansions will be performed,
recursively (preventing infinite expansions from recursive anchors is left as an
exercise to the reader).

```
expandAnchors
:: MonadError (Path, Text) m
=> HashMap Text Value
-> Value
-> m Value
expandAnchors anchors =
flip irewriteM [] \path value -> runMaybeT do
text <- hoistMaybe $ value ^? _String
('$', name) <- hoistMaybe $ uncons text
case lookup name anchors of
Nothing -> throwError (path, name)
Just res -> pure res
```

## Caveats and limitations

Since indices are user-defined, there is no way for this library to provide a
default implementation to `iplate`

which, ironically, results in some
boilerplate.