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

Safe HaskellSafe
LanguageHaskell98

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 As. 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-evalFamilyed.

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-evalFamilyMed.

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.