multiplate-0.0.3: Lightweight generic library for mutually recursive data types.

Data.Generics.Multiplate

Description

Suppose we are given mutually recursive data types `A`, `B`, and `C`. Here are some definitions of terms.

`child`
A maximal subexpression of `A`, `B`, or `C`. A child does not necessarily have to have the same type as the parent. `A` might have some children of type `B` and other children of type `C` or even `A`.
`children`
A list of all children. In particular children are ordered from left to right.
`descendant`
Any subexpression of of `A`, `B`, or `C`. Specifically a descendant of an expression is either the expression itself or a descendant of one of its children.
`family`
A list of all descendant. The order is a context dependent. `preorderFold` uses preorder, while `postorderFold` and `mapFamilyM` uses postorder.
`plate`
A plate is a record parametrized by a functor `f` with one field of type `A -> f A` for each type belonging to the mutually recursive set of types. For example, a plate for `A`, `B`, and `C` would look like
```data ABCPlate f = ABCPlate
{ fieldA :: A -> f A
, fieldB :: B -> f B
, fieldC :: C -> f C
}
```

Although this above is the original motivation behind multiplate,but you can make any structure you want into a `Multiplate` as long as you satisfy the two multiplate laws listed below.

The names of the functions in this module are based on Sebastian Fischer's Refactoring Uniplate: http://www-ps.informatik.uni-kiel.de/~sebf/projects/traversal.html

Synopsis

# Documentation

type Projector p a = forall f. p f -> a -> f a Source

A plate over `f` consists of several fields of type `A -> f A` for various `A`s. `Projector` is the type of the projection functions of plates.

class Multiplate p where Source

A `Multiplate` is a constructor of kind `(* -> *) -> *` operating on `Applicative` functors having functions `multiplate` and `mkPlate` that satisfy the following two laws:

1. ``` `multiplate` `purePlate` = `purePlate`
where
`purePlate` = `mkPlate` (\_ -> `pure`)
```
2. ``` `multiplate` (`composePlate` p1 p2) = `composePlate` (`multiplate` p1) (`multiplate` p2)
where
`composePlate` p1 p2 = `mkPlate` (\proj a -> (`Compose` (proj p1 ``fmap`` proj p2 a)))
```

Note: By parametricity, it suffices for (1) to prove

````multiplate` (`mkPlate` (\_ -> `Identity`)) = `mkPlate` (\_ -> `Identity`)
```

Methods

multiplate :: Applicative f => p f -> p f Source

This is the heart of the Multiplate library. Given a plate of functions over some applicative functor `f`, create a new plate that applies these functions to the children of each data type in the plate.

This process essentially defines the semantics what the children of these data types are. They don't have to literally be the syntactic children. For example, if a language supports quoted syntax, that quoted syntax behaves more like a literal than as a sub-expression. Therefore, although quoted expressions may syntactically be subexpressions, the user may chose to implement `multiplate` so that they are not semantically considered subexpressions.

mkPlate :: (forall a. Projector p a -> a -> f a) -> p f Source

Given a generic builder creating an `a -> f a`, use the builder to construct each field of the plate `p f`. The builder may need a little help to construct a field of type `a -> f a`, so to help out the builder pass it the projection function for the field being built.

e.g. Given a plate of type

```data ABCPlate f = ABCPlate {
{ fieldA :: A -> f B
, fieldB :: B -> f B
, fieldC :: C -> f C
}
```

the instance of `mkPlate` for `ABCPlate` should be

``` `mkPlate` builder = ABCPlate (builder fieldA) (builder fieldB) (builder fieldC)
```

applyNaturalTransform :: forall p f g. Multiplate p => (forall a. f a -> g a) -> p f -> p g Source

Given a natural transformation between two functors, `f` and `g`, and a plate over `f`, compose the natural transformation with each field of the plate.

purePlate :: (Multiplate p, Applicative f) => p f Source

Given an `Applicative` `f`, `purePlate` builds a plate over `f` whose fields are all `pure`.

Generally `purePlate` is used as the base of a record update. One constructs the expression

````purePlate` { fieldOfInterest = \a -> case a of
| constructorOfInterest -> expr
| _                     -> `pure` a
}
```

and this is a typical parameter that is passed to most functions in this library.

emptyPlate :: (Multiplate p, Alternative f) => p f Source

Given an `Alternative` `f`, `emptyPlate` builds a plate over `f` whose fields are all `const empty`.

Generally `emptyPlate` is used as the base of a record update. One constructs the expression

````emptyPlate` { fieldOfInterest = \a -> case a of
| constructorOfInterest -> expr
| _                     -> `empty`
}
```

and this is a typical parameter that is passed to `evalFamily` and `evalFamilyM`.

kleisliComposePlate :: forall p m. (Multiplate p, Monad m) => p m -> p m -> p m Source

Given two plates over a monad `m`, the fields of the plate can be Kleisli composed (`<=<`) fieldwise.

composePlate :: forall p f g. (Multiplate p, Functor g) => p f -> p g -> p (Compose g f) Source

Given two plates, they can be composed fieldwise yielding the composite functor.

composePlateRightId :: forall p f. Multiplate p => p f -> p Identity -> p f Source

Given two plates with one over the `Identity` functor, the two plates can be composed fieldwise.

composePlateLeftId :: forall p f. (Multiplate p, Functor f) => p Identity -> p f -> p f Source

Given two plates with one over the `Identity` functor, the two plates can be composed fieldwise.

appendPlate :: forall p o. (Multiplate p, Monoid o) => p (Constant o) -> p (Constant o) -> p (Constant o) Source

Given two plates with one over the `Constant o` applicative functor for a `Monoid` `o`, each field of the plate can be pointwise appended with `mappend`.

mChildren :: forall p o. (Multiplate p, Monoid o) => p (Constant o) -> p (Constant o) Source

Given a plate whose fields all return a `Monoid` `o`, `mChildren` produces a plate that returns the `mconcat` of all the children of the input.

preorderFold :: forall p o. (Multiplate p, Monoid o) => p (Constant o) -> p (Constant o) Source

Given a plate whose fields all return a `Monoid` `o`, `preorderFold` produces a plate that returns the `mconcat` of the family of the input. The input itself produces the leftmost element of the concatenation, then this is followed by the family of the first child, then it is followed by the family of the second child, and so forth.

postorderFold :: forall p o. (Multiplate p, Monoid o) => p (Constant o) -> p (Constant o) Source

Given a plate whose fields all return a `Monoid` `o`, `preorderFold` produces a plate that returns the `mconcat` of the family of the input. The concatenation sequence begins with the family of the first child, then it is followed by the family of the second child, and so forth until finally the input itself produces the rightmost element of the concatenation.

mapChildren :: Multiplate p => p Identity -> p Identity Source

Given a plate whose fields transform each type, `mapChildren` returns a plate whose fields transform the children of the input.

mapFamily :: Multiplate p => p Identity -> p Identity Source

Given a plate whose fields transform each type, `mapFamily` returns a plate whose fields transform the family of the input. The traversal proceeds bottom up, first transforming the families of the children, before finally transforming the value itself.

mapChildrenM :: (Multiplate p, Applicative m, Monad m) => p m -> p m Source

Given a plate whose fields transform each type, `mapChildrenM` returns a plate whose fields transform the children of the input. The processing is sequenced from the first child to the last child.

mapFamilyM :: (Multiplate p, Applicative m, Monad m) => p m -> p m Source

Given a plate whose fields transform each type, `mapFamilyM` returns a plate whose fields transform the family of the input. The sequencing is done in a depth-first postorder traversal.

evalFamily :: Multiplate p => p Maybe -> p Identity Source

Given a plate whose fields maybe transforms each type, `evalFamily` returns a plate whose fields exhaustively transform the family of the input. The traversal proceeds bottom up, first transforming the families of the children. If a transformation succeeds then the result is re-`evalFamily`ed.

A post-condition is that the input transform returns `Nothing` on all family members of the output, or more formally

````preorderFold` (`applyNaturalTransform` t f) ``composePlate`` (`evalFamily` f) ⊑ `purePlate`
where
t :: forall a. `Maybe` a -> `Constant` `All` a
t = `Constant` `.` `All` `.` `isNothing`
```

evalFamilyM :: forall p m. (Multiplate p, Applicative m, Monad m) => p (MaybeT m) -> p m Source

Given a plate whose fields maybe transforms each type, `evalFamilyM` returns a plate whose fields exhaustively transform the family of the input. The sequencing is done in a depth-first postorder traversal, but if a transformation succeeds then the result is re-`evalFamilyM`ed.

always :: Multiplate p => p Maybe -> p Identity Source

Given a plate used for `evalFamily`, replace returning `Nothing` with returning the input. This transforms plates suitable for `evalFamily` into plates suitable form `mapFamily`.

alwaysM :: forall p f. (Multiplate p, Functor f) => p (MaybeT f) -> p f Source

Given a plate used for `evalFamilyM`, replace returning `Nothing` with returning the input. This transforms plates suitable for `evalFamilyM` into plates suitable form `mapFamilyM`.

traverseFor :: Multiplate p => Projector p a -> p Identity -> a -> a Source

Given a projection function for a plate over the `Identity` functor, upgrade the projection function to strip off the wrapper.

traverseMFor :: (Multiplate p, Monad m) => Projector p a -> p m -> a -> m a Source

Instantiate a projection function at a monad.

foldFor :: Multiplate p => Projector p a -> p (Constant o) -> a -> o Source

Given a projection function for a plate over the `Constant o` functor, upgrade the projection function to strip off the wrapper.

unwrapFor :: Multiplate p => (o -> b) -> Projector p a -> p (Constant o) -> a -> b Source

Given a projection function for a plate over the `Constant o` functor, and a continuation for `o`, upgrade the projection function to strip off the wrapper and run the continuation.

Typically the continuation simply strips off a wrapper for `o`.

sumFor :: Multiplate p => Projector p a -> p (Constant (Sum n)) -> a -> n Source

Given a projection function for a plate over the `Constant (Sum n)` functor, upgrade the projection function to strip off the wrappers.

productFor :: Multiplate p => Projector p a -> p (Constant (Product n)) -> a -> n Source

Given a projection function for a plate over the `Constant (Product n)` functor, upgrade the projection function to strip off the wrappers.

allFor :: Multiplate p => Projector p a -> p (Constant All) -> a -> Bool Source

Given a projection function for a plate over the `Constant All` functor, upgrade the projection function to strip off the wrappers.

anyFor :: Multiplate p => Projector p a -> p (Constant Any) -> a -> Bool Source

Given a projection function for a plate over the `Constant Any` functor, upgrade the projection function to strip off the wrappers.

firstFor :: Multiplate p => Projector p a -> p (Constant (First b)) -> a -> Maybe b Source

Given a projection function for a plate over the `Constant (First n)` functor, upgrade the projection function to strip off the wrappers.

lastFor :: Multiplate p => Projector p a -> p (Constant (Last b)) -> a -> Maybe b Source

Given a projection function for a plate over the `Constant (Last n)` functor, upgrade the projection function to strip off the wrappers.