Data.Generics.Uniplate.Operations

Definitions of Uniplate and Biplate classes, along with all the standard operations.

Import this module directly only if you are defining new Uniplate operations, otherwise import one of Data.Generics.Uniplate.Direct, Data.Generics.Uniplate.Typeable or Data.Generics.Uniplate.Data.

Most functions have an example of a possible use for the function. To illustate, I have used the Expr type as below:

data Expr = Val Int
          | Neg Expr
          | Add Expr Expr

The Classes

class Uniplate on where

The standard Uniplate class, all operations require this. All definitions must define uniplate, while descend and descendM are optional.

Minimal complete definition

uniplate

Methods

uniplate :: on -> (Str on, Str on -> on)

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.

Given uniplate x = (cs, gen)

cs should be a Str on, constructed of Zero, One and Two, containing all x's direct children of the same type as x. gen should take a Str on with exactly the same structure as cs, and generate a new element with the children replaced.

Example instance:

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)

descend :: (on -> on) -> on -> on

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

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)

descendM :: Applicative m => (on -> m on) -> on -> m on

Applicative variant of descend

Instances

Uniplate Bool

Defined in Data.Generics.Uniplate.Direct

Methods

uniplate :: Bool -> (Str Bool, Str Bool -> Bool)

descend :: (Bool -> Bool) -> Bool -> Bool

descendM :: Applicative m => (Bool -> m Bool) -> Bool -> m Bool

Uniplate Char

Defined in Data.Generics.Uniplate.Direct

Methods

uniplate :: Char -> (Str Char, Str Char -> Char)

descend :: (Char -> Char) -> Char -> Char

descendM :: Applicative m => (Char -> m Char) -> Char -> m Char

Uniplate Double

Defined in Data.Generics.Uniplate.Direct

Methods

uniplate :: Double -> (Str Double, Str Double -> Double)

descend :: (Double -> Double) -> Double -> Double

descendM :: Applicative m => (Double -> m Double) -> Double -> m Double

Uniplate Float

Defined in Data.Generics.Uniplate.Direct

Methods

uniplate :: Float -> (Str Float, Str Float -> Float)

descend :: (Float -> Float) -> Float -> Float

descendM :: Applicative m => (Float -> m Float) -> Float -> m Float

Uniplate Int

Defined in Data.Generics.Uniplate.Direct

Methods

uniplate :: Int -> (Str Int, Str Int -> Int)

descend :: (Int -> Int) -> Int -> Int

descendM :: Applicative m => (Int -> m Int) -> Int -> m Int

Uniplate Integer

Defined in Data.Generics.Uniplate.Direct

Methods

uniplate :: Integer -> (Str Integer, Str Integer -> Integer)

descend :: (Integer -> Integer) -> Integer -> Integer

descendM :: Applicative m => (Integer -> m Integer) -> Integer -> m Integer

Uniplate ()

Defined in Data.Generics.Uniplate.Direct

Methods

uniplate :: () -> (Str (), Str () -> ())

descend :: (() -> ()) -> () -> ()

descendM :: Applicative m => (() -> m ()) -> () -> m ()

Data a => Uniplate a

Defined in Data.Generics.Uniplate.Data

Methods

uniplate :: a -> (Str a, Str a -> a)

descend :: (a -> a) -> a -> a

descendM :: Applicative m => (a -> m a) -> a -> m a

PlateAll a a => Uniplate a

Defined in Data.Generics.Uniplate.Typeable

Methods

uniplate :: a -> (Str a, Str a -> a)

descend :: (a -> a) -> a -> a

descendM :: Applicative m => (a -> m a) -> a -> m a

Uniplate [Char]

Defined in Data.Generics.Uniplate.Direct

Methods

uniplate :: [Char] -> (Str [Char], Str [Char] -> [Char])

descend :: ([Char] -> [Char]) -> [Char] -> [Char]

descendM :: Applicative m => ([Char] -> m [Char]) -> [Char] -> m [Char]

Uniplate (Ratio Integer)

Defined in Data.Generics.Uniplate.Direct

Methods

uniplate :: Ratio Integer -> (Str (Ratio Integer), Str (Ratio Integer) -> Ratio Integer)

descend :: (Ratio Integer -> Ratio Integer) -> Ratio Integer -> Ratio Integer

descendM :: Applicative m => (Ratio Integer -> m (Ratio Integer)) -> Ratio Integer -> m (Ratio Integer)

class Uniplate to => Biplate from to where

Children are defined as the top-most items of type to starting at the root. All instances must define biplate, while descendBi and descendBiM are optional.

Minimal complete definition

biplate

Methods

biplate :: from -> (Str to, Str to -> from)

Return all the top most children of type to within from.

If from == to then this function should return the root as the single child.

descendBi :: (to -> to) -> from -> from

Like 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 descend.

descendBiM :: Applicative m => (to -> m to) -> from -> m from

Instances

(Data a, Data b, Uniplate b) => Biplate a b

Defined in Data.Generics.Uniplate.Data

Methods

biplate :: a -> (Str b, Str b -> a)

descendBi :: (b -> b) -> a -> a

descendBiM :: Applicative m => (b -> m b) -> a -> m a

(Typeable a, Typeable b, Uniplate b, PlateAll a b) => Biplate a b

Defined in Data.Generics.Uniplate.Typeable

Methods

biplate :: a -> (Str b, Str b -> a)

descendBi :: (b -> b) -> a -> a

descendBiM :: Applicative m => (b -> m b) -> a -> m a

Biplate [Char] Char

Defined in Data.Generics.Uniplate.Direct

Methods

biplate :: [Char] -> (Str Char, Str Char -> [Char])

descendBi :: (Char -> Char) -> [Char] -> [Char]

descendBiM :: Applicative m => (Char -> m Char) -> [Char] -> m [Char]

Biplate (Ratio Integer) Integer

Defined in Data.Generics.Uniplate.Direct

Methods

biplate :: Ratio Integer -> (Str Integer, Str Integer -> Ratio Integer)

descendBi :: (Integer -> Integer) -> Ratio Integer -> Ratio Integer

descendBiM :: Applicative m => (Integer -> m Integer) -> Ratio Integer -> m (Ratio Integer)

Biplate [Char] [Char]

Defined in Data.Generics.Uniplate.Direct

Methods

biplate :: [Char] -> (Str [Char], Str [Char] -> [Char])

descendBi :: ([Char] -> [Char]) -> [Char] -> [Char]

descendBiM :: Applicative m => ([Char] -> m [Char]) -> [Char] -> m [Char]

Biplate (Ratio Integer) (Ratio Integer)

Defined in Data.Generics.Uniplate.Direct

Methods

biplate :: Ratio Integer -> (Str (Ratio Integer), Str (Ratio Integer) -> Ratio Integer)

descendBi :: (Ratio Integer -> Ratio Integer) -> Ratio Integer -> Ratio Integer

descendBiM :: Applicative m => (Ratio Integer -> m (Ratio Integer)) -> Ratio Integer -> m (Ratio Integer)

Single Type Operations

Queries

universe :: Uniplate on => on -> [on]

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]

children :: Uniplate on => on -> [on]

Get the direct children of a node. Usually using universe is more appropriate.

Transformations

transform :: Uniplate on => (on -> on) -> on -> on

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

transformM :: (Monad m, Applicative m, Uniplate on) => (on -> m on) -> on -> m on

Applicative variant of transform

rewrite :: Uniplate on => (on -> Maybe on) -> on -> on

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))

Usually transform is more appropriate, but rewrite can give better compositionality. Given two single transformations f and g, you can construct f mplus g which performs both rewrites until a fixed point.

rewriteM :: (Monad m, Applicative m, Uniplate on) => (on -> m (Maybe on)) -> on -> m on

Applicative variant of rewrite

Others

contexts :: Uniplate on => on -> [(on, on -> on)]

Return all the contexts and holes.

universe x == map fst (contexts x)
all (== x) [b a | (a,b) <- contexts x]

holes :: Uniplate on => on -> [(on, on -> on)]

The one depth version of contexts

children x == map fst (holes x)
all (== x) [b a | (a,b) <- holes x]

para :: Uniplate on => (on -> [r] -> r) -> on -> r

Perform a fold-like computation on each value, technically a paramorphism

Multiple Type Operations

Queries

universeBi :: Biplate from to => from -> [to]

childrenBi :: Biplate from to => from -> [to]

Return the children of a type. If to == from then it returns the original element (in contrast to children)

Transformations

transformBi :: Biplate from to => (to -> to) -> from -> from

transformBiM :: (Monad m, Applicative m, Biplate from to) => (to -> m to) -> from -> m from

rewriteBi :: Biplate from to => (to -> Maybe to) -> from -> from

rewriteBiM :: (Monad m, Applicative m, Biplate from to) => (to -> m (Maybe to)) -> from -> m from

Others

contextsBi :: Biplate from to => from -> [(to, to -> from)]

holesBi :: Biplate from to => from -> [(to, to -> from)]