Toy example: Consider our favourite data type
data Expr e
= Kst Int
| Var String
| Add e e
instance ShowF Expr where showsPrecF = showsPrec
and write a function simplifying additions with zero:
simplifyAdd :: Mu Expr -> Mu Expr
simplifyAdd = transform worker where
worker expr = case expr of
Fix (Add x (Fix (Kst 0))) -> x -- 0+x = x
Fix (Add (Fix (Kst 0)) y) -> y -- x+0 = 0
_ -> expr
Unfortunately, all these Fix wrappers are rather ugly; but they are straightforward to put in,
and in principle one could use Template Haskell quasi-quotation to generate patterns.
|The list of direct descendants.
The list of all substructures. Together with list-comprehension syntax
this is a powerful query tool. For example the following is how you get
the list of all variable names in an expression:
variables expr = [ s | Fix (Var s) <- universe expr ]
|Top-down transformation. This provided only for completeness;
usually, it is transform what you want use instead.
|Non-recursive top-down transformation. This is basically just fmap.
|Similarly, this is basically just mapM.
|Bottom-up transformation until a normal form is reached.
|Bottom-up transformation (typically "shallow", that is, restricted to a single level)
which can change the structure functor (actually transform is a special case of this).
|We annotate the nodes of the tree with functions which replace that
|Flattened version of context.
|(Strict) left fold. Since Mu f is not a functor, but a data type, we cannot make
it an instance of the Foldable type class.
|Produced by Haddock version 2.6.1|