Only use this module if you are using both
Direct instances in
the same project and they are conflicting.
- class Uniplate on where
- class Uniplate to => Biplate from to where
- universe :: Uniplate on => on -> [on]
- children :: Uniplate on => on -> [on]
- transform :: Uniplate on => (on -> on) -> on -> on
- transformM :: (Monad m, Uniplate on) => (on -> m on) -> on -> m on
- rewrite :: Uniplate on => (on -> Maybe on) -> on -> on
- rewriteM :: (Monad m, Uniplate on) => (on -> m (Maybe on)) -> on -> m on
- contexts :: Uniplate on => on -> [(on, on -> on)]
- holes :: Uniplate on => on -> [(on, on -> on)]
- para :: Uniplate on => (on -> [r] -> r) -> on -> r
- universeBi :: Biplate from to => from -> [to]
- childrenBi :: Biplate from to => from -> [to]
- transformBi :: Biplate from to => (to -> to) -> from -> from
- transformBiM :: (Monad m, Biplate from to) => (to -> m to) -> from -> m from
- rewriteBi :: Biplate from to => (to -> Maybe to) -> from -> from
- rewriteBiM :: (Monad m, Biplate from to) => (to -> m (Maybe to)) -> from -> m from
- contextsBi :: Biplate from to => from -> [(to, to -> from)]
- holesBi :: Biplate from to => from -> [(to, to -> from)]
- transformBis :: forall a. Data a => [[Transformer]] -> a -> a
- data Transformer
- transformer :: Data a => (a -> a) -> Transformer
The underlying method in the class. Taking a value, the function should return all the immediate children of the same type, and a function to replace them.
uniplate x = (cs, gen)
cs should be a
Str on, constructed of
x's direct children of the same type as
should take a
Str on with exactly the same structure as
and generate a new element with the children replaced.
instance Uniplate Expr where uniplate (Val i ) = (Zero , \Zero -> Val i ) uniplate (Neg a ) = (One a , \(One a) -> Neg a ) uniplate (Add a b) = (Two (One a) (One b), \(Two (One a) (One b)) -> Add a b)
Perform a transformation on all the immediate children, then combine them back.
This operation allows additional information to be passed downwards, and can be
used to provide a top-down transformation. This function can be defined explicitly,
or can be provided by automatically in terms of
For example, on the sample type, we could write:
descend f (Val i ) = Val i descend f (Neg a ) = Neg (f a) descend f (Add a b) = Add (f a) (f b)
Monadic variant of
Return all the top most children of type
from == to then this function should return the root as the single
descend but with more general types. If
from == to then this
function does not descend. Therefore, when writing definitions it is
highly unlikely that this function should be used in the recursive case.
A common pattern is to first match the types using
descendBi, then continue
the recursion with
Single Type Operations
Get all the children of a node, including itself and all children.
universe (Add (Val 1) (Neg (Val 2))) = [Add (Val 1) (Neg (Val 2)), Val 1, Neg (Val 2), Val 2]
This method is often combined with a list comprehension, for example:
vals x = [i | Val i <- universe x]
Get the direct children of a node. Usually using
universe is more appropriate.
Transform every element in the tree, in a bottom-up manner.
For example, replacing negative literals with literals:
negLits = transform f where f (Neg (Lit i)) = Lit (negate i) f x = x
Monadic variant of
Rewrite by applying a rule everywhere you can. Ensures that the rule cannot be applied anywhere in the result:
propRewrite r x = all (isNothing . r) (universe (rewrite r x))
transform is more appropriate, but
rewrite can give better
compositionality. Given two single transformations
g, you can
f which performs both rewrites until a fixed point.
Monadic variant of
Return all the contexts and holes.
universe x == map fst (contexts x) all (== x) [b a | (a,b) <- contexts x]
The one depth version of
children x == map fst (holes x) all (== x) [b a | (a,b) <- holes x]
Perform a fold-like computation on each value, technically a paramorphism
Multiple Type Operations
Return the children of a type. If
to == from then it returns the
original element (in contrast to
Apply a sequence of transformations in order. This function obeys the equivalence:
transformBis [[transformer f],[transformer g],...] == transformBi f . transformBi g . ...
Each item of type
[Transformer] is applied in turn, right to left. Within each
[Transformer], the individual
Transformer values may be interleaved.
The implementation will attempt to perform fusion, and avoid walking any part of the data structure more than necessary. To further improve performance, you may wish to partially apply the first argument, which will calculate information about the relationship between the transformations.