Editing Zipper monad/TravelTree (section)

=== Tree reverser ===
This is a more in-depth example showing <hask>getTree</hask> and <hask>putTree</hask>, but is still rather contrived as it's easily done without the zipper (the zipper-less version is shown below).

The algorithm ''reverses'' the tree, in the sense that at every branch, the two subtrees are swapped over.

<haskell>
revTree :: Tree a -> Tree a
revTree t = (getTop t) `traverse` revTree' where
    revTree' :: TravelTree a
    revTree' = do t <- getTree
                        case t of
                          Branch _ _ -> do left
                                           l' <- revTree'
                                           swap
                                           r' <- revTree'
                                           up
                                           putTree $ Branch r' l'
                          Leaf x     -> return $ Leaf x

-- without using the zipper:
revTreeZipless :: Tree a -> Tree a
revTreeZipless (Leaf x)       = Leaf x
revTreeZipless (Branch xs ys) = Branch (revTreeZipless ys) (revTreeZipless xs)
</haskell>

Result of evaluation:

 *Tree> revTree $ Branch (Leaf 1) (Branch (Branch (Leaf 2) (Leaf 3)) (Leaf 4))
 Branch (Branch (Leaf 4) (Branch (Leaf 3) (Leaf 2))) (Leaf 1)

==== Generalisation ====
Einar Karttunen (musasabi) suggested generalising this to a recursive tree mapper:

<haskell>
treeMap :: (a -> Tree a)                -- what to put at leaves
        -> (Tree a -> Tree a -> Tree a) -- what to put at branches
        -> (Tree a -> Tree a)           -- combinator function
treeMap leaf branch = \t -> (getTop t) `traverse` treeMap' where
    treeMap' = do t <- getTree
                  case t of
                    Branch _ _ -> do left
                                     l' <- treeMap'
                                     swap
                                     r' <- treeMap'
                                     up
                                     putTree $ branch l' r'
                    Leaf x     -> return $ leaf x
</haskell>

<hask>revTree</hask> is then easy:

<haskell>
revTreeZipper :: Tree a -> Tree a
revTreeZipper = treeMap Leaf (flip Branch)
</haskell>

It turns out this is a fairly powerful combinator. As with <hask>revTree</hask>, it can change the structure of a tree. Here's another example which turns a tree into one where siblings are sorted, i.e. given a <hask>Branch l r</hask>, if <hask>l</hask> and <hask>r</hask> are leaves, then the value of <hask>l</hask> is less than or equal to that of <hask>r</hask>. Also, if one of <hask>l</hask> or <hask>r</hask> is a <hask>Branch</hask> and the other a <hask>Leaf</hask>, then <hask>l</hask> is the <hask>Leaf</hask> and <hask>r</hask> the <hask>Branch</hask>:

<haskell>
sortSiblings :: Ord a => Tree a -> Tree a
sortSiblings = treeMap Leaf minLeaves where
    minLeaves l@(Branch _ _) r@(Leaf _       ) = Branch r l
    minLeaves l@(Leaf _)     r@(Branch _ _   ) = Branch l r
    minLeaves l@(Branch _ _) r@(Branch _ _   ) = Branch l r
    minLeaves l@(Leaf x)     r@(Leaf y       ) = Branch (Leaf $ min x y)
                                                        (Leaf $ max x y)
</haskell>

Result of evaluation:

 *Tree> sortSiblings t
 Branch (Branch (Leaf 3) (Branch (Leaf 1) (Leaf 2))) (Branch (Leaf 4) (Leaf 5))