Safe Haskell | Safe-Infered |
---|
This library provides Uniplate-style generic traversals and other recursion schemes for fixed-point types. There are many advantages of using fixed-point types instead of explicit recursion:
- we can easily add attributes to the nodes of an existing tree;
- there is no need for a custom type class, we can build everything on the top of
Functor
,Foldable
andTraversable
, for which GHC can derive the instances for us; - we can provide interesting recursion schemes
- some operations can retain the structure of the tree, instead flattening it into a list;
- it is relatively straightforward to provide generic implementations of the zipper, tries, tree drawing, hashing, etc...
The main disadvantage is that it does not work well for mutually recursive data types, and that pattern matching becomes more tedious (but there are partial solutions for the latter).
Consider as an example the following simple expression language, encoded by a recursive algebraic data type:
data Expr = Kst Int | Var String | Add Expr Expr deriving (Eq,Show)
We can open up the recursion, and obtain a functor instead:
data Expr1 e = Kst Int | Var String | Add e e deriving (Eq,Show,Functor,Foldable,Traversable)
The fixed-point type Mu
Expr1
is isomorphic to Expr
.
However, we can also add some attributes to the nodes:
The type Attr
Expr1 a =
Mu
(
Ann
Expr1 a)
is the type of
with the same structure, but with each node having an extra
field of type a
.
The functions in this library work on types like that: Mu
f
,
where f
is a functor, and sometimes explicitely on Attr
f a
.
The organization of the modules (excluding Util.*) is the following:
- Data.Generics.Fixplate.Base - core types and type classes
- Data.Generics.Fixplate.Traversals - Uniplate-style traversals
- Data.Generics.Fixplate.Morphisms - recursion schemes
- Data.Generics.Fixplate.Attributes - annotated trees
- Data.Generics.Fixplate.Open - functions operating on functors
- Data.Generics.Fixplate.Zipper - generic zipper
- Data.Generics.Fixplate.Draw - generic tree drawing (both ASCII and graphviz)
- Data.Generics.Fixplate.Trie - generic generalized tries
- Data.Generics.Fixplate.Hash - annotating trees with their hashes
This module re-exports the most common functionality present in the library (but not for example the zipper, tries, hashing).
The library itself should be fully Haskell98 compatible; no language extensions are used.
Note: to obtain Eq
, Ord
, Show
, Read
and other instances for
fixed point types like Mu Expr1
, consult the documentation of the
EqF
type class (cf. the related OrdF
, ShowF
and ReadF
classes)
- module Data.Generics.Fixplate.Base
- module Data.Generics.Fixplate.Traversals
- module Data.Generics.Fixplate.Morphisms
- module Data.Generics.Fixplate.Attributes
- module Data.Generics.Fixplate.Draw
- class Functor f where
- fmap :: (a -> b) -> f a -> f b
- class Foldable t where
- class (Functor t, Foldable t) => Traversable t where
- traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
- sequenceA :: Applicative f => t (f a) -> f (t a)
- mapM :: Monad m => (a -> m b) -> t a -> m (t b)
- sequence :: Monad m => t (m a) -> m (t a)
Documentation
module Data.Generics.Fixplate.Base
module Data.Generics.Fixplate.Draw
class Functor f where
The Functor
class is used for types that can be mapped over.
Instances of Functor
should satisfy the following laws:
fmap id == id fmap (f . g) == fmap f . fmap g
The instances of Functor
for lists, Maybe
and IO
satisfy these laws.
fmap :: (a -> b) -> f a -> f b
Functor [] | |
Functor IO | |
Functor ZipList | |
Functor ReadPrec | |
Functor ReadP | |
Functor Maybe | |
Functor Id | |
Functor ((->) r) | |
Functor (Either a) | |
Functor ((,) a) | |
Ix i => Functor (Array i) | |
Functor (Const m) | |
Monad m => Functor (WrappedMonad m) | |
Functor (Map k) | |
Functor (StateR s) | |
Functor (StateL s) | |
Functor f => Functor (CoAttrib f) | |
Functor f => Functor (Attrib f) | |
Arrow a => Functor (WrappedArrow a b) | |
Functor f => Functor (CoAnn f a) | |
Functor f => Functor (Ann f a) | |
Functor f => Functor (HashAnn hash f) |
class Foldable t where
Data structures that can be folded.
Minimal complete definition: foldMap
or foldr
.
For example, given a data type
data Tree a = Empty | Leaf a | Node (Tree a) a (Tree a)
a suitable instance would be
instance Foldable Tree where foldMap f Empty = mempty foldMap f (Leaf x) = f x foldMap f (Node l k r) = foldMap f l `mappend` f k `mappend` foldMap f r
This is suitable even for abstract types, as the monoid is assumed
to satisfy the monoid laws. Alternatively, one could define foldr
:
instance Foldable Tree where foldr f z Empty = z foldr f z (Leaf x) = f x z foldr f z (Node l k r) = foldr f (f k (foldr f z r)) l
Combine the elements of a structure using a monoid.
foldMap :: Monoid m => (a -> m) -> t a -> m
Map each element of the structure to a monoid, and combine the results.
foldr :: (a -> b -> b) -> b -> t a -> b
foldl :: (a -> b -> a) -> a -> t b -> a
foldr1 :: (a -> a -> a) -> t a -> a
A variant of foldr
that has no base case,
and thus may only be applied to non-empty structures.
foldr1
f =foldr1
f .toList
foldl1 :: (a -> a -> a) -> t a -> a
class (Functor t, Foldable t) => Traversable t where
Functors representing data structures that can be traversed from left to right.
Minimal complete definition: traverse
or sequenceA
.
Instances are similar to Functor
, e.g. given a data type
data Tree a = Empty | Leaf a | Node (Tree a) a (Tree a)
a suitable instance would be
instance Traversable Tree where traverse f Empty = pure Empty traverse f (Leaf x) = Leaf <$> f x traverse f (Node l k r) = Node <$> traverse f l <*> f k <*> traverse f r
This is suitable even for abstract types, as the laws for <*>
imply a form of associativity.
The superclass instances should satisfy the following:
- In the
Functor
instance,fmap
should be equivalent to traversal with the identity applicative functor (fmapDefault
). - In the
Foldable
instance,foldMap
should be equivalent to traversal with a constant applicative functor (foldMapDefault
).
traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
Map each element of a structure to an action, evaluate these actions from left to right, and collect the results.
sequenceA :: Applicative f => t (f a) -> f (t a)
Evaluate each action in the structure from left to right, and collect the results.
mapM :: Monad m => (a -> m b) -> t a -> m (t b)
Map each element of a structure to a monadic action, evaluate these actions from left to right, and collect the results.
sequence :: Monad m => t (m a) -> m (t a)
Evaluate each monadic action in the structure from left to right, and collect the results.
Traversable [] | |
Traversable Maybe | |
Ix i => Traversable (Array i) | |
Traversable (Map k) | |
Traversable f => Traversable (CoAttrib f) | |
Traversable f => Traversable (Attrib f) | |
Traversable f => Traversable (CoAnn f a) | |
Traversable f => Traversable (Ann f a) | |
Traversable f => Traversable (HashAnn hash f) |