Control.Monad.Tree

This module contains the definition of a simple rose-tree-like datatype, parameterized by both the type of the labels for the branches, the type of elements contained in the leaves of the datatype, and the type f of containers used for the branching: Tree b f a.

Fixing the type of labels (usually b ~ () for simplicity), we have instances for Functor, Applicative, Monad, and Alternative. This is similar to the list monad, but because the underlying datastructure is a tree, and we can represent branchind non-determinism, there is more flexibility -- as when trying to extract data from a Tree, one can choose a search strategy for flattening the tree.

This module provides a simple breadth-first-search strategy bfs, and a depth-first strategy dfs, however, theoretically other strategies could be used, taking advantage of the information provided by the type of labels b for the tree. For instance, with b ~ Double, a best-first or probabilistic search could be used.

Tree data type

data Tree n f a

Simple rose-tree data structure, with labels of type n for nodel, labels of types b for branches, containers of type f used to branch on tree nodes, and values of type a at the leaves.

f will usually be [], but this was kept generic to allow for the use of more efficent containers if relevant.

Constructors

Leaf a

Node n (f (Tree n f a))

Instances

Functor f => Monad (Tree n f)

Defined in Control.Monad.Tree

Methods

(>>=) :: Tree n f a -> (a -> Tree n f b) -> Tree n f b

(>>) :: Tree n f a -> Tree n f b -> Tree n f b

return :: a -> Tree n f a

Functor f => Functor (Tree n f)

Defined in Control.Monad.Tree

Methods

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

(<$) :: a -> Tree n f b -> Tree n f a

Functor f => Applicative (Tree n f)

Defined in Control.Monad.Tree

Methods

pure :: a -> Tree n f a

(<*>) :: Tree n f (a -> b) -> Tree n f a -> Tree n f b

liftA2 :: (a -> b -> c) -> Tree n f a -> Tree n f b -> Tree n f c

(*>) :: Tree n f a -> Tree n f b -> Tree n f b

(<*) :: Tree n f a -> Tree n f b -> Tree n f a

Alternative f => Alternative (Tree () f)

Defined in Control.Monad.Tree

Methods

empty :: Tree () f a

(<|>) :: Tree () f a -> Tree () f a -> Tree () f a

some :: Tree () f a -> Tree () f [a]

many :: Tree () f a -> Tree () f [a]

(Eq a, Eq n, Eq1 f) => Eq (Tree n f a)

Defined in Control.Monad.Tree

Methods

(==) :: Tree n f a -> Tree n f a -> Bool

(/=) :: Tree n f a -> Tree n f a -> Bool

Search algorithms

dfs :: Tree n [] a -> [a]

Depth first search of a tree

dfs' :: (n -> Bool) -> Tree n [] a -> [a]

dfs with a predicate on the labels

bfs :: Tree n [] a -> [a]

Breadth first search algorithm for trees

bfs' :: (n -> Bool) -> Tree n [] a -> [a]

Breadth first search with a predicate on the labels.