# Zipper monad/TravelBTree

### From HaskellWiki

< Zipper monad(Difference between revisions)

DavidHouse (Talk | contribs) (TravelBTree docs) |
DonStewart (Talk | contribs) m (category) |

## Latest revision as of 03:51, 8 October 2006

TravelBTree

## Contents |

## [edit] 1 Definition

data BTree a = Leaf a | Branch [BTree a] deriving (Show, Eq) data Cxt a = Top | Child { parent :: Cxt a, -- parent's context lefts :: [BTree a], -- siblings to the left rights :: [BTree a] -- siblings to the right } deriving (Show, Eq) type BTreeLoc a = Loc (Cxt a) (BTree a) type TravelBTree a = Travel (BTreeLoc a) (BTree a)

BTree

Branch

Cxt

*context*of a subtree. A

BTreeLoc

## [edit] 2 Functions

### [edit] 2.1 Moving around

There are five main functions for stringing togetherTravelBTree

-- moves down to the nth child (0-indexed) down :: Int -> TravelBTree a left, -- moves left a sibling right, -- moves right a sibling up, -- moves to the node's parent top -- moves to the top node :: TravelTree a

down

down 0

(!!)

### [edit] 2.2 Mutation

You get the three functions provided by the generic Zipper monad (modifyStruct

getStruct

putStruct

TravelBTree

insertLeft, -- insert a tree to the left of the current node insertRight, -- insert a tree to the right of the current node insertDown -- insert a tree as the last child of the current node :: BTree a -> TravelBTree a insertDownAt -- insert a tree as the nth child of the current node :: BTree a -> Int -> TravelBTree a -- delete the current node. If we're the last node of our siblings, move left. -- If not, move right. If we're an only child move up. delete :: TravelBTree a

### [edit] 2.3 Node classification

There are four functions you can call to find out what kind of node a given location points to:

isTop, -- is the location the top node? isChild, -- is the location the child of some other node (i.e. not the top)? isFirst, -- is the location the first of its siblings? isRight -- is the location the last of its siblings? :: TreeLoc a -> Bool

TreeBLoc

TreeBLoc

TravelBTree

do

liftM

do top <- liftM isTop get when top $ down 3 >> return ()

## [edit] 3 Examples

Watch this space.

## [edit] 4 Code

The code of this file is quite length, so you can just download it. Alternatively, download the entire zipper library.