Module Data.Traversal

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

Author: Sebastian Fischer

Version: December 2020

Summary of exported operations:

noChildren :: a -> ([b],[b] -> a)  Deterministic 
Traversal function for constructors without children.
children :: (a -> ([b],[b] -> a)) -> a -> [b]  Deterministic 
Yields the children of a value.
replaceChildren :: (a -> ([b],[b] -> a)) -> a -> [b] -> a  Deterministic 
Replaces the children of a value.
mapChildren :: (a -> ([b],[b] -> a)) -> (b -> b) -> a -> a  Deterministic 
Applies the given function to each child of a value.
family :: (a -> ([a],[a] -> a)) -> a -> [a]  Deterministic 
Computes a list of the given value, its children, those children, etc.
childFamilies :: (a -> ([b],[b] -> a)) -> (b -> ([b],[b] -> b)) -> a -> [b]  Deterministic 
Computes a list of family members of the children of a value.
mapFamily :: (a -> ([a],[a] -> a)) -> (a -> a) -> a -> a  Deterministic 
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  Deterministic 
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  Deterministic 
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  Deterministic 
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  Deterministic 
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  Deterministic 
Fold the children and combine the results.
replaceChildrenM :: Monad a => (b -> ([c],[c] -> b)) -> b -> a [c] -> a b  Deterministic 
Monadic version of replaceChildren
mapChildrenM :: Monad a => (b -> ([c],[c] -> b)) -> (c -> a c) -> b -> a b  Deterministic 
Monadic version of mapChildren
mapFamilyM :: Monad a => (b -> ([b],[b] -> b)) -> (b -> a b) -> b -> a b  Deterministic 
Monadic version of mapFamily
mapChildFamiliesM :: Monad a => (b -> ([c],[c] -> b)) -> (c -> ([c],[c] -> c)) -> (c -> a c) -> b -> a b  Deterministic 
Monadic version of mapChildFamilies
evalFamilyM :: Monad a => (b -> ([b],[b] -> b)) -> (b -> a (Maybe b)) -> b -> a b  Deterministic 
Monadic version of evalFamily
evalChildFamiliesM :: Monad a => (b -> ([c],[c] -> b)) -> (c -> ([c],[c] -> c)) -> (c -> a (Maybe c)) -> b -> a b  Deterministic 
Monadic 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)  Deterministic 

Traversal function for constructors without children.

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

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

Yields the children of a value.

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

Replaces the children of a value.

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

Applies the given function to each child of a value.

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

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

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

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  Deterministic 

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  Deterministic 

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  Deterministic 

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  Deterministic 

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  Deterministic 

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  Deterministic 

Fold the children and combine the results.

replaceChildrenM :: Monad a => (b -> ([c],[c] -> b)) -> b -> a [c] -> a b  Deterministic 

Monadic version of replaceChildren

mapChildrenM :: Monad a => (b -> ([c],[c] -> b)) -> (c -> a c) -> b -> a b  Deterministic 

Monadic version of mapChildren

mapFamilyM :: Monad a => (b -> ([b],[b] -> b)) -> (b -> a b) -> b -> a b  Deterministic 

Monadic version of mapFamily

mapChildFamiliesM :: Monad a => (b -> ([c],[c] -> b)) -> (c -> ([c],[c] -> c)) -> (c -> a c) -> b -> a b  Deterministic 

Monadic version of mapChildFamilies

evalFamilyM :: Monad a => (b -> ([b],[b] -> b)) -> (b -> a (Maybe b)) -> b -> a b  Deterministic 

Monadic version of evalFamily

evalChildFamiliesM :: Monad a => (b -> ([c],[c] -> b)) -> (c -> ([c],[c] -> c)) -> (c -> a (Maybe c)) -> b -> a b  Deterministic 

Monadic version of evalChildFamilies