Safe Haskell | None |
---|---|

Language | Haskell2010 |

## Synopsis

- data Zipper a = Zipper {}
- root :: Tree a -> Zipper a
- up :: Zipper a -> Maybe (Zipper a)
- firstChild :: Zipper a -> Maybe (Zipper a)
- nextSibling :: Zipper a -> Maybe (Zipper a)
- prevSibling :: Zipper a -> Maybe (Zipper a)
- allChildren :: Zipper a -> [Zipper a]
- allTrees :: Zipper a -> [Zipper a]
- unZipperLocal :: Zipper a -> Tree a
- constructTree :: [([Tree a], a, [Tree a])] -> Maybe (Tree a)
- findEvert :: (a -> Bool) -> Tree a -> Maybe (Tree a)
- findEvert' :: (Tree a -> Bool) -> Tree a -> Maybe (Tree a)
- findPath :: (a -> Bool) -> (a -> Bool) -> Tree a -> Maybe [a]
- findNode :: (a -> Bool) -> Tree a -> Maybe [a]
- findNodes :: (Tree a -> Bool) -> Tree a -> [[a]]

# Documentation

`>>>`

let myTree = Node 0 [ Node 1 [] , Node 2 [] , Node 3 [ Node 4 [] ] ] :}`:{`

# Zipper on rose trees

firstChild :: Zipper a -> Maybe (Zipper a) Source #

Move the focus to the first child of this node.

`>>>`

Just (Zipper {focus = Node {rootLabel = 1, subForest = []}, ancestors = [([],0,[Node {rootLabel = 2, subForest = []},Node {rootLabel = 3, subForest = [Node {rootLabel = 4, subForest = []}]}])]})`firstChild $ root myTree`

nextSibling :: Zipper a -> Maybe (Zipper a) Source #

Move the focus to the next sibling of this node

`>>>`

Just (Zipper {focus = Node {rootLabel = 2, subForest = []}, ancestors = [([Node {rootLabel = 1, subForest = []}],0,[Node {rootLabel = 3, subForest = [Node {rootLabel = 4, subForest = []}]}])]})`(firstChild $ root myTree) >>= nextSibling`

allChildren :: Zipper a -> [Zipper a] Source #

Given a zipper that focussses on some subtree t, construct a list with zippers that focus on each child.

allTrees :: Zipper a -> [Zipper a] Source #

Given a zipper that focussses on some subtree t, construct a list with zippers that focus on each of the nodes in the subtree of t.

unZipperLocal :: Zipper a -> Tree a Source #

Creates a new tree from the zipper that thas the current node as root. The ancestorTree (if there is any) forms the first child in this new root.

constructTree :: [([Tree a], a, [Tree a])] -> Maybe (Tree a) Source #

Constructs a tree from the list of ancestors (if there are any)

findEvert :: (a -> Bool) -> Tree a -> Maybe (Tree a) Source #

Given a predicate on an element, find a node that matches the predicate, and turn that node into the root of the tree.

running time: \(O(nT)\) where \(n\) is the size of the tree, and \(T\) is the time to evaluate a predicate.

`>>>`

Just (Node {rootLabel = 4, subForest = [Node {rootLabel = 3, subForest = [Node {rootLabel = 0, subForest = [Node {rootLabel = 1, subForest = []},Node {rootLabel = 2, subForest = []}]}]}]})`findEvert (== 4) myTree`

`>>>`

Nothing`findEvert (== 5) myTree`

findEvert' :: (Tree a -> Bool) -> Tree a -> Maybe (Tree a) Source #

Given a predicate matching on a subtree, find a node that matches the predicate, and turn that node into the root of the tree.

running time: \(O(nT(n))\) where \(n\) is the size of the tree, and \(T(m)\) is the time to evaluate a predicate on a subtree of size \(m\).

:: (a -> Bool) | is this node a starting node |

-> (a -> Bool) | is this node an ending node |

-> Tree a | |

-> Maybe [a] |

Function to extract a path between a start node and an end node (if such a path exists). If there are multiple paths, no guarantees are given about which one is returned.

running time: \(O(n(T_p+T_s)\), where \(n\) is the size of the tree, and
\(T_p\) and \(T_s\) are the times it takes to evaluate the `isStartingNode`

and `isEndingNode`

predicates.

`>>>`

Just [1,0,3,4]`findPath (== 1) (==4) myTree`

`>>>`

Just [1,0,2]`findPath (== 1) (==2) myTree`

`>>>`

Just [1]`findPath (== 1) (==1) myTree`

`>>>`

Just [1,0,2]`findPath (== 1) (==2) myTree`

`>>>`

Just [4,3,0,2]`findPath (== 4) (==2) myTree`

findNode :: (a -> Bool) -> Tree a -> Maybe [a] Source #

Given a predicate on a, find (the path to) a node that satisfies the predicate.

`>>>`

Just [0,3,4]`findNode (== 4) myTree`

findNodes :: (Tree a -> Bool) -> Tree a -> [[a]] Source #

Find all paths to nodes that satisfy the predicate

running time: \(O(nT(n))\) where \(n\) is the size of the tree, and \(T(m)\) is the time to evaluate a predicate on a subtree of size \(m\).

`>>>`

[[0],[0,1],[0,2],[0,3]]`findNodes ((< 4) . rootLabel) myTree`

`>>>`

[[0],[0,2],[0,3,4]]`findNodes (even . rootLabel) myTree`

`>>>`

[[0],[0,3]]`let size = length in findNodes ((> 1) . size) myTree`