Zipper monad
From HaskellWiki
DavidHouse (Talk  contribs) (adding heapise) 
(Added ref to the generic zipper.) 

(12 intermediate revisions by 4 users not shown)  
Line 1:  Line 1:  
−  The TravelTree Monad is a monad proposed and designed by Paolo Martini (xerox), and coded by David House (davidhouse). It is based on the State monad and is used for navigating around in binary trees, using the concept of [[TheZipper]]. 
+  The Zipper Monad is a generic monad for navigating around arbitrary data structures. It supports movement, mutation and classification of nodes (is this node the top node or a child node?, etc). It was proposed and designed by Paolo Martini (xerox), and coded by David House (davidhouse). It's designed for use with [[ZipperThe Zipper]] but in fact there is no requirement to use such an idiom. 
−  == Definition == 
+  At the moment there are two specific libraries that use the Travel monad: [[Zipper_monad/TravelTreeTravelTree]] for navigating around binary trees, and [[Zipper_monad/TravelBTreeTravelBTree]] for navigating around "BTrees", trees where each node has an arbitrary number of branches. Please see below for an alternative zipper implementation that works for any data structure whatsoever. 
−  <haskell> 

−  newtype Travel t a = Travel { unT :: State t a } 

−  deriving (Functor, Monad, MonadState t) 

−  type TravelTree a = Travel (Loc a) (Tree a) 

−  </haskell> 

−  Computations in <hask>TravelTree</hask> are stateful. <hask>Loc a</hask> and <hask>Tree a</hask> are defined as follows: 
+  You can [http://haskell.org/sitewiki/images/b/b7/Zipper.tar.gz download] the library in its entirety. To run the tests: 
+  tar xzf Zipper.tar.gz 

+  cd Zipper 

+  ghc o test make Main.hs 

+  ./test 

+  
+  == Definition == 

<haskell> 
<haskell> 

−  data Tree a = Leaf a  Branch (Tree a) (Tree a) 
+  data Loc c a = Loc { struct :: a, 
−  +  cxt :: c } 

−  data Cxt a = Top 
+  deriving (Show, Eq) 
−   L (Cxt a) (Tree a) 

−   R (Tree a) (Cxt a) 

−  deriving (Show) 

−  type Loc a = (Tree a, Cxt a) 
+  newtype Travel loc a = Travel { unT :: State loc a } 
+  deriving (Functor, Monad, MonadState loc, Eq) 

</haskell> 
</haskell> 

−  See [[TheZipper]] for an explanation of the <hask>Cxt</hask> and <hask>Loc</hask> concepts. 
+  Computations in <hask>Travel</hask> are stateful. <hask>Loc c a</hask> is a type for storing the location within a structure. <hask>struct</hask> should be the substructure that the <hask>Loc</hask> is refering to, and <hask>cxt</hask> the "context" of the substructure; i.e. the rest of the structure. <hask>Loc</hask> is designed to hold a [[Zipper]] (although it doesn't have to; for example if you wanted to traverse a list it would probably be more natural to hold the entire structure and an index). Indeed, both of the libraries provided with the generic <hask>Travel</hask> monad use a zipper. 
== Functions == 
== Functions == 

−  === Moving around === 

−  There are four main functions for stringing together <hask>TravelTree</hask> computations: 

−  <haskell> 
+  === Movement === 
−  left,  moves down a level, through the left branch 
+  At the moment, movement is specific to the structure you are traversing and as such, the movement functions are provided by libraries implementing specific structures. Try the documentation for [[Zipper_monad/TravelTreeTravelTree]] (binary trees) or [[Zipper_monad/TravelBTreeTravelBTree]] (BTrees; trees where each node has an arbitrary number of branches). 
−  right,  moves down a level, through the right branch 

−  up,  moves to the node's parent 

−  top  moves to the top node 

−  :: TravelTree a 

−  </haskell> 

−  
−  All four return the subtree at the new location. 

=== Mutation === 
=== Mutation === 

−  There are also functions available for changing the tree: 
+  There are three generic functions available for changing the structure: 
<haskell> 
<haskell> 

−  getTree :: TravelTree a 
+  getStruct :: Travel (Loc c a) a 
−  putTree :: Tree a > TravelTree a 
+  putStruct :: a > Travel (Loc c a) a 
−  modifyTree :: (Tree a > Tree a) > TravelTree a 
+  modifyStruct :: (a > a) > Travel (Loc c a) a 
</haskell> 
</haskell> 

−  These are direct frontdoors for State's <hask>get</hask>, <hask>put</hask> and <hask>modify</hask>, and all three return the subtree after any applicable modifications. 
+  These are direct frontdoors for State's <hask>get</hask>, <hask>put</hask> and <hask>modify</hask>, and all three return the substructure after any applicable modifications. 
=== Exit points === 
=== Exit points === 

Line 37:  Line 41:  
<haskell> 
<haskell> 

−  traverse :: Tree a > TravelTree a > Tree a 
+  traverse :: Loc c a  starting location (initial state) 
+  > Travel (Loc c a) a  locational computation to use 

+  > a  resulting substructure 

</haskell> 
</haskell> 

−  Again, this is just a frontdoor for <hask>evalState</hask>, with an initial state of <hask>(tt, Top)</hask> where <hask>tt</hask> is the <hask>TravelTree</hask> passed in. 
+  Again, this is just a frontdoor for <hask>evalState</hask>. Note that you have to give a <hask>Loc</hask> as a starting state. Both the libraries provided supply a <hask>getTop</hask> function, which takes a tree and returns the <hask>Loc</hask> corresponding to the top of the tree. Thus a typical call to <hask>traverse</hask> might look like: 
−  
−  == Examples == 

−  The following examples use as the example tree: 

<haskell> 
<haskell> 

−  t = Branch (Branch (Branch (Leaf 1) (Leaf 2)) 
+  let t = Branch (Leaf 1) (Branch (Leaf 2) (Leaf 3)) 
−  (Leaf 3)) 
+  in (getTop t) `traverse` (left >> swap >> right) 
−  (Branch (Leaf 4) 

−  (Leaf 5)) 

</haskell> 
</haskell> 

−  [[Image:Tree.pngframerightThe example tree]] 
+  == Examples == 
−  === A simple path === 
+  <hask>Travel</hask> is too general to be used in itself, so there are examples given on the documentation pages for the libraries. Here are the links again: 
−  This is a very simple example showing how to use the movement functions: 

−  <haskell> 

−  leftLeftRight :: TravelTree a 

−  leftLeftRight = do left 

−  left 

−  right 

−  </haskell> 

−  Result of evaluation: 
+  * [[Zipper_monad/TravelTreeTravelTree]] for binary trees. 
+  * [[Zipper_monad/TravelBTreeTravelBTree]] for BTrees; trees where each node has an arbitrary number of branches. 

−  *Tree> t `traverse` leftLeftRight 
+  == Code == 
−  Leaf 2 

−  === Tree reverser === 
+  Here's the base Zipper monad in full ([http://haskell.org/sitewiki/images/3/36/Zipper.hs download] or download the [http://haskell.org/sitewiki/images/b/b7/Zipper.tar.gz entire library]): 
−  This is a more indepth example showing <hask>getTree</hask> and <hask>putTree</hask>, but is still rather contrived as it's easily done without the zipper (the zipperless version is shown below). 

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

<haskell> 
<haskell> 

−  revTree :: Tree a > Tree a 
+  {# OPTIONS_GHC fglasgowexts #} 
−  revTree t = t `traverse` revTree' where 
+  module Zipper where 
−  revTree' :: TravelTree a 

−  revTree' = do t < getTree 

−  case t of 

−  Branch _ _ > do left 

−  l' < revTree' 

−  up 

−  right 

−  r' < revTree' 

−  up 

−  putTree $ Branch r' l' 

−  Leaf x > return $ Leaf x 

−   without using the zipper: 
+   A monad implementing for traversing data structures 
−  revTreeZipless :: Tree a > Tree a 
+   http://haskell.org/haskellwiki/Zipper_monad 
−  revTreeZipless (Leaf x) = Leaf x 
+   
−  revTreeZipless (Branch xs ys) = Branch (revTreeZipless ys) (revTreeZipless xs) 

−  </haskell> 

−  Result of evaluation: 
+  import Control.Monad.State 
−  *Tree> revTree $ Branch (Leaf 1) (Branch (Branch (Leaf 2) (Leaf 3)) (Leaf 4)) 
+  data Loc c a = Loc { struct :: a, 
−  Branch (Branch (Leaf 4) (Branch (Leaf 3) (Leaf 2))) (Leaf 1) 
+  cxt :: c } 
+  deriving (Show, Eq) 

−  ==== Generalisation ==== 
+  newtype Travel loc a = Travel { unT :: State loc a } 
−  Einar Karttunen (musasabi) suggested generalising this to a recursive tree combinator: 
+  deriving (Functor, Monad, MonadState loc, Eq) 
−  <haskell> 
+   Exit Points 
−  treeComb :: (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 

−  treeComb leaf branch = \t > t `traverse` treeComb' where 

−  treeComb' = do t < getTree 

−  case t of 

−  Branch _ _ > do left 

−  l' < treeComb' 

−  up 

−  right 

−  r' < treeComb' 

−  up 

−  putTree $ branch l' r' 

−  Leaf x > return $ leaf x 

−  </haskell> 

−  <hask>revTree</hask> is then easy: 
+   get out of the monad 
+  traverse :: Loc c a  starting location (initial state) 

+  > Travel (Loc c a) a  locational computation to use 

+  > a  resulting substructure 

+  traverse start tt = evalState (unT tt) start 

−  <haskell> 
+   Mutation 
−  revTreeZipper :: Tree a > Tree a 
+   
−  revTreeZipper = treeComb 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 a heap, 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>: 
+   modify the substructure at the current node 
+  modifyStruct :: (a > a) > Travel (Loc c a) a 

+  modifyStruct f = modify editStruct >> liftM struct get where 

+  editStruct (Loc s c) = Loc (f s) c 

−  <haskell> 
+   put a new substructure at the current node 
−  heapise :: Ord a => Tree a > Tree a 
+  putStruct :: a > Travel (Loc c a) a 
−  heapise = treeComb Leaf minLeaves where 
+  putStruct t = modifyStruct $ const t 
−  minLeaves l@(Branch _ _) r@(Leaf _ ) = Branch r l 
+  
−  minLeaves l@(Leaf _) r@(Branch _ _ ) = Branch l r 
+   get the current substructure 
−  minLeaves l@(Branch _ _) r@(Branch _ _ ) = Branch l r 
+  getStruct :: Travel (Loc c a) a 
−  minLeaves l@(Leaf x) r@(Leaf y ) = Branch (Leaf $ min x y) 
+  getStruct = modifyStruct id  works because modifyTree returns the 'new' tree 
−  (Leaf $ max x y) 

</haskell> 
</haskell> 

−  Result of evaluation: 
+  == Alternative implementation == 
−  *Tree> heapise t 
+  An alternative implementation, which is polymorphic over data structures 
−  Branch (Branch (Leaf 3) (Branch (Leaf 1) (Leaf 2))) (Branch (Leaf 4) (Leaf 5)) 
+  and so can be written once and for all, is available at 
+  [http://pobox.com/~oleg/ftp/Computation/Continuations.html#zipper Generic Zipper and its applications] 

+  The code on that page served as the basis for a Zipperbased file system. 

−  +  [[Category:Idioms]] 

−  == Code == 
+  [[Category:Monad]] 
−  
−  <haskell> 

−  {# GHC_OPTION fglasgowexts #} 

−  data Cxt a = Top 

−   L (Cxt a) (Tree a) 

−   R (Tree a) (Cxt a) 

−  deriving (Show) 

−  
−  type Loc a = (Tree a, Cxt a) 

−  
−  newtype Travel t a = Travel { unT :: State t a } 

−  deriving (Functor, Monad, MonadState t) 

−  type TravelTree a = Travel (Loc a) (Tree a) 

−  
−  left :: TravelTree a 

−  left = modify left' >> liftM fst get where 

−  left' (Branch l r, c) = (l, L c r) 

−  
−  right :: TravelTree a 

−  right = modify right' >> liftM fst get where 

−  right' (Branch l r, c) = (r, R l c) 

−  
−  up :: TravelTree a 

−  up = modify up' >> liftM fst get where 

−  up' (t, L c r) = (Branch t r, c) 

−  up' (t, R l c) = (Branch l t, c) 

−  
−  top :: TravelTree a 

−  top = modify (second $ const Top) >> liftM fst get 

−  
−  modifyTree :: (Tree a > Tree a) > TravelTree a 

−  modifyTree f = modify (first f) >> liftM fst get 

−  
−  putTree :: Tree a > TravelTree a 

−  putTree t = modifyTree $ const t 

−  
−  getTree :: TravelTree a 

−  getTree = modifyTree id  works because modifyTree returns the 'new' tree 

−  
−  traverse :: Tree a > TravelTree a > Tree a 

−  traverse t tt = evalState (unT tt) (t, Top) 

−  </haskell> 
Latest revision as of 01:00, 9 October 2006
The Zipper Monad is a generic monad for navigating around arbitrary data structures. It supports movement, mutation and classification of nodes (is this node the top node or a child node?, etc). It was proposed and designed by Paolo Martini (xerox), and coded by David House (davidhouse). It's designed for use with The Zipper but in fact there is no requirement to use such an idiom.
At the moment there are two specific libraries that use the Travel monad: TravelTree for navigating around binary trees, and TravelBTree for navigating around "BTrees", trees where each node has an arbitrary number of branches. Please see below for an alternative zipper implementation that works for any data structure whatsoever.
You can download the library in its entirety. To run the tests:
tar xzf Zipper.tar.gz cd Zipper ghc o test make Main.hs ./test
Contents 
[edit] 1 Definition
data Loc c a = Loc { struct :: a, cxt :: c } deriving (Show, Eq) newtype Travel loc a = Travel { unT :: State loc a } deriving (Functor, Monad, MonadState loc, Eq)
[edit] 2 Functions
[edit] 2.1 Movement
At the moment, movement is specific to the structure you are traversing and as such, the movement functions are provided by libraries implementing specific structures. Try the documentation for TravelTree (binary trees) or TravelBTree (BTrees; trees where each node has an arbitrary number of branches).
[edit] 2.2 Mutation
There are three generic functions available for changing the structure:
getStruct :: Travel (Loc c a) a putStruct :: a > Travel (Loc c a) a modifyStruct :: (a > a) > Travel (Loc c a) a
[edit] 2.3 Exit points
To get out of the monad, usetraverse :: Loc c a  starting location (initial state) > Travel (Loc c a) a  locational computation to use > a  resulting substructure
let t = Branch (Leaf 1) (Branch (Leaf 2) (Leaf 3)) in (getTop t) `traverse` (left >> swap >> right)
[edit] 3 Examples
 TravelTree for binary trees.
 TravelBTree for BTrees; trees where each node has an arbitrary number of branches.
[edit] 4 Code
Here's the base Zipper monad in full (download or download the entire library):
{# OPTIONS_GHC fglasgowexts #} module Zipper where  A monad implementing for traversing data structures  http://haskell.org/haskellwiki/Zipper_monad  import Control.Monad.State data Loc c a = Loc { struct :: a, cxt :: c } deriving (Show, Eq) newtype Travel loc a = Travel { unT :: State loc a } deriving (Functor, Monad, MonadState loc, Eq)  Exit Points   get out of the monad traverse :: Loc c a  starting location (initial state) > Travel (Loc c a) a  locational computation to use > a  resulting substructure traverse start tt = evalState (unT tt) start  Mutation   modify the substructure at the current node modifyStruct :: (a > a) > Travel (Loc c a) a modifyStruct f = modify editStruct >> liftM struct get where editStruct (Loc s c) = Loc (f s) c  put a new substructure at the current node putStruct :: a > Travel (Loc c a) a putStruct t = modifyStruct $ const t  get the current substructure getStruct :: Travel (Loc c a) a getStruct = modifyStruct id  works because modifyTree returns the 'new' tree
[edit] 5 Alternative implementation
An alternative implementation, which is polymorphic over data structures and so can be written once and for all, is available at Generic Zipper and its applications The code on that page served as the basis for a Zipperbased file system.