Data.Generics.Fixplate

This library provides Uniplate-style generic traversals for fixed-point types. The advantages of using fixed-point types instead of explicit recursion are the following:

• we can 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 and Traversable, for which GHC can derive the instances for us;
• some operations can retain the structure of the tree, instead flattening it into a list;
• it is quite straightforward to provide a generic zipper.

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:

 Expr 
   = Kst Int 
   | Var String 
   | Add Expr Expr
   deriving (Eq,Show)

We can open up the recursion, and obtain a functor instead:

 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.

This module re-exports most of the functionality present in the library.

The library should be fully Haskell98 compatible, with the exception of the module Data.Generics.Fixplate.Structure, which needs the Rank2Types extension. For compatibility, the functionality of this module is at the moment only provided when compiled with GHC or Hugs.

Documentation

module Data.Generics.Fixplate.Base

module Data.Generics.Fixplate.Traversals

module Data.Generics.Fixplate.Morphisms

module Data.Generics.Fixplate.Attributes

module Data.Generics.Fixplate.Structure

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.

Methods

fmap :: (a -> b) -> f a -> f b

Instances

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 (StateR s)

Functor (StateL s)

Functor f => Functor (Attrib f)

Arrow a => Functor (WrappedArrow a b)

Functor f => Functor (Ann f a)

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

Methods

fold :: Monoid m => t m -> m

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

Right-associative fold of a structure.

foldr f z = foldr f z . toList

foldl :: (a -> b -> a) -> a -> t b -> a

Left-associative fold of a structure.

foldl f z = foldl f z . toList

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

A variant of foldl that has no base case, and thus may only be applied to non-empty structures.

foldl1 f = foldl1 f . toList

Instances

Foldable []

Foldable Maybe

Ix i => Foldable (Array i)

Foldable f => Foldable (Attrib f)

Foldable f => Foldable (Ann f 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).

Methods

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.

Instances

Traversable []

Traversable Maybe

Ix i => Traversable (Array i)

Traversable f => Traversable (Attrib f)

Traversable f => Traversable (Ann f a)