Library to support lightweight generic traversals through tree-structured data. See here for a description of the library.

Author: Sebastian Fischer

Version: February 2008

Summary of exported operations:

noChildren :: a -> ([b],[b] -> a)   
Traversal function for constructors without children.
children :: (a -> ([b],[b] -> a)) -> a -> [b]   
Yields the children of a value.
replaceChildren :: (a -> ([b],[b] -> a)) -> a -> [b] -> a   
Replaces the children of a value.
mapChildren :: (a -> ([b],[b] -> a)) -> (b -> b) -> a -> a   
Applies the given function to each child of a value.
family :: (a -> ([a],[a] -> a)) -> a -> [a]   
Computes a list of the given value, its children, those children, etc.
childFamilies :: (a -> ([b],[b] -> a)) -> (b -> ([b],[b] -> b)) -> a -> [b]   
Computes a list of family members of the children of a value.
mapFamily :: (a -> ([a],[a] -> a)) -> (a -> a) -> a -> a   
Applies the given function to each member of the family of a value.
mapChildFamilies :: (a -> ([b],[b] -> a)) -> (b -> ([b],[b] -> b)) -> (b -> b) -> a -> a   
Applies the given function to each member of the families of the children of a value.
evalFamily :: (a -> ([a],[a] -> a)) -> (a -> Maybe a) -> a -> a   
Applies the given function to each member of the family of a value as long as possible.
evalChildFamilies :: (a -> ([b],[b] -> a)) -> (b -> ([b],[b] -> b)) -> (b -> Maybe b) -> a -> a   
Applies the given function to each member of the families of the children of a value as long as possible.
fold :: (a -> ([a],[a] -> a)) -> (a -> [b] -> b) -> a -> b   
Implements a traversal similar to a fold with possible default cases.
foldChildren :: (a -> ([b],[b] -> a)) -> (b -> ([b],[b] -> b)) -> (a -> [c] -> d) -> (b -> [c] -> c) -> a -> d   
Fold the children and combine the results.
replaceChildrenIO :: (a -> ([b],[b] -> a)) -> a -> IO [b] -> IO a   
IO version of replaceChildren
mapChildrenIO :: (a -> ([b],[b] -> a)) -> (b -> IO b) -> a -> IO a   
IO version of mapChildren
mapFamilyIO :: (a -> ([a],[a] -> a)) -> (a -> IO a) -> a -> IO a   
IO version of mapFamily
mapChildFamiliesIO :: (a -> ([b],[b] -> a)) -> (b -> ([b],[b] -> b)) -> (b -> IO b) -> a -> IO a   
IO version of mapChildFamilies
evalFamilyIO :: (a -> ([a],[a] -> a)) -> (a -> IO (Maybe a)) -> a -> IO a   
IO version of evalFamily
evalChildFamiliesIO :: (a -> ([b],[b] -> a)) -> (b -> ([b],[b] -> b)) -> (b -> IO (Maybe b)) -> a -> IO a   
IO version of evalChildFamilies

Exported datatypes:


Traversable

A datatype is Traversable if it defines a function that can decompose a value into a list of children of the same type and recombine new children to a new value of the original type.

Type synonym: Traversable a b = a -> ([b],[b] -> a)


Exported operations:

noChildren :: a -> ([b],[b] -> a)   

Traversal function for constructors without children.

Further infos:
  • solution complete, i.e., able to compute all solutions

children :: (a -> ([b],[b] -> a)) -> a -> [b]   

Yields the children of a value.

replaceChildren :: (a -> ([b],[b] -> a)) -> a -> [b] -> a   

Replaces the children of a value.

mapChildren :: (a -> ([b],[b] -> a)) -> (b -> b) -> a -> a   

Applies the given function to each child of a value.

family :: (a -> ([a],[a] -> a)) -> a -> [a]   

Computes a list of the given value, its children, those children, etc.

childFamilies :: (a -> ([b],[b] -> a)) -> (b -> ([b],[b] -> b)) -> a -> [b]   

Computes a list of family members of the children of a value. The value and its children can have different types.

mapFamily :: (a -> ([a],[a] -> a)) -> (a -> a) -> a -> a   

Applies the given function to each member of the family of a value. Proceeds bottom-up.

mapChildFamilies :: (a -> ([b],[b] -> a)) -> (b -> ([b],[b] -> b)) -> (b -> b) -> a -> a   

Applies the given function to each member of the families of the children of a value. The value and its children can have different types. Proceeds bottom-up.

evalFamily :: (a -> ([a],[a] -> a)) -> (a -> Maybe a) -> a -> a   

Applies the given function to each member of the family of a value as long as possible. On each member of the family of the result the given function will yield Nothing. Proceeds bottom-up.

evalChildFamilies :: (a -> ([b],[b] -> a)) -> (b -> ([b],[b] -> b)) -> (b -> Maybe b) -> a -> a   

Applies the given function to each member of the families of the children of a value as long as possible. Similar to evalFamily.

fold :: (a -> ([a],[a] -> a)) -> (a -> [b] -> b) -> a -> b   

Implements a traversal similar to a fold with possible default cases.

foldChildren :: (a -> ([b],[b] -> a)) -> (b -> ([b],[b] -> b)) -> (a -> [c] -> d) -> (b -> [c] -> c) -> a -> d   

Fold the children and combine the results.

replaceChildrenIO :: (a -> ([b],[b] -> a)) -> a -> IO [b] -> IO a   

IO version of replaceChildren

mapChildrenIO :: (a -> ([b],[b] -> a)) -> (b -> IO b) -> a -> IO a   

IO version of mapChildren

mapFamilyIO :: (a -> ([a],[a] -> a)) -> (a -> IO a) -> a -> IO a   

IO version of mapFamily

mapChildFamiliesIO :: (a -> ([b],[b] -> a)) -> (b -> ([b],[b] -> b)) -> (b -> IO b) -> a -> IO a   

IO version of mapChildFamilies

evalFamilyIO :: (a -> ([a],[a] -> a)) -> (a -> IO (Maybe a)) -> a -> IO a   

IO version of evalFamily

evalChildFamiliesIO :: (a -> ([b],[b] -> a)) -> (b -> ([b],[b] -> b)) -> (b -> IO (Maybe b)) -> a -> IO a   

IO version of evalChildFamilies