Personal tools

Zipper monad

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
m (fix up code/hask mismatches)
(Added ref to the generic zipper.)
 
(15 intermediate revisions by 4 users not shown)
Line 1: Line 1:
  +
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 [[Zipper|The Zipper]] but in fact there is no requirement to use such an idiom.
   
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]].
+
At the moment there are two specific libraries that use the Travel monad: [[Zipper_monad/TravelTree|TravelTree]] for navigating around binary trees, and [[Zipper_monad/TravelBTree|TravelBTree]] for navigating around "B-Trees", 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.
   
== Definition ==
+
You can [http://haskell.org/sitewiki/images/b/b7/Zipper.tar.gz download] the library in its entirety. To run the tests:
<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:
+
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/TravelTree|TravelTree]] (binary trees) or [[Zipper_monad/TravelBTree|TravelBTree]] (B-Trees; 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 front-doors 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 front-doors 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 38: Line 38:
   
 
<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 front-door 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 front-door 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.png|frame|right|The example tree]]
+
== Examples ==
  +
  +
<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:
  +
  +
* [[Zipper_monad/TravelTree|TravelTree]] for binary trees.
  +
* [[Zipper_monad/TravelBTree|TravelBTree]] for B-Trees; trees where each node has an arbitrary number of branches.
   
 
== Code ==
 
== Code ==
  +
  +
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]):
   
 
<haskell>
 
<haskell>
data Cxt a = Top
+
{-# OPTIONS_GHC -fglasgow-exts #-}
| L (Cxt a) (Tree a)
+
module Zipper where
| R (Tree a) (Cxt a)
 
deriving (Show)
 
   
type Loc a = (Tree a, Cxt a)
+
-- A monad implementing for traversing data structures
  +
-- http://haskell.org/haskellwiki/Zipper_monad
  +
--------------------------------------------------------------------------------
   
newtype Travel t a = Travel { unT :: State t a }
+
import Control.Monad.State
deriving (Functor, Monad, MonadState t)
 
type TravelTree a = Travel (Loc a) (Tree a)
 
   
t = Branch (Branch (Branch (Leaf 1) (Leaf 2))
+
data Loc c a = Loc { struct :: a,
(Leaf 3))
+
cxt :: c }
(Branch (Leaf 4)
+
deriving (Show, Eq)
(Leaf 5))
 
   
left :: TravelTree a
+
newtype Travel loc a = Travel { unT :: State loc a }
left = modify left' >> liftM fst get where
+
deriving (Functor, Monad, MonadState loc, Eq)
left' (Branch l r, c) = (l, L c r)
 
   
right :: TravelTree a
+
-- Exit Points
right = modify right' >> liftM fst get where
+
--
right' (Branch l r, c) = (r, R l c)
 
   
up :: TravelTree a
+
-- get out of the monad
up = modify up' >> liftM fst get where
+
traverse :: Loc c a -- starting location (initial state)
up' (t, L c r) = (Branch t r, c)
+
-> Travel (Loc c a) a -- locational computation to use
up' (t, R l c) = (Branch l t, c)
+
-> a -- resulting substructure
  +
traverse start tt = evalState (unT tt) start
   
top :: TravelTree a
+
-- Mutation
top = modify (second $ const Top) >> liftM fst get
+
--
   
modifyTree :: (Tree a -> Tree a) -> TravelTree a
+
-- modify the substructure at the current node
modifyTree f = modify (first f) >> liftM fst get
+
modifyStruct :: (a -> a) -> Travel (Loc c a) a
  +
modifyStruct f = modify editStruct >> liftM struct get where
  +
editStruct (Loc s c) = Loc (f s) c
   
putTree :: Tree a -> TravelTree a
+
-- put a new substructure at the current node
putTree t = modifyTree $ const t
+
putStruct :: a -> Travel (Loc c a) a
  +
putStruct t = modifyStruct $ const t
   
getTree :: TravelTree a
+
-- get the current substructure
getTree = modifyTree id -- works because modifyTree returns the 'new' tree
+
getStruct :: Travel (Loc c a) a
  +
getStruct = modifyStruct id -- works because modifyTree returns the 'new' tree
  +
</haskell>
   
traverse :: Tree a -> TravelTree a -> Tree a
+
== Alternative implementation ==
traverse t tt = evalState (unT tt) (t, Top)
 
   
leftLeftRight :: TravelTree a
+
An alternative implementation, which is polymorphic over data structures
leftLeftRight = do left
+
and so can be written once and for all, is available at
left
+
[http://pobox.com/~oleg/ftp/Computation/Continuations.html#zipper Generic Zipper and its applications]
right
+
The code on that page served as the basis for a Zipper-based file system.
   
revTreeZipper :: Tree a -> Tree a
+
[[Category:Idioms]]
revTreeZipper t = t `traverse` revTreeZipper' where
+
[[Category:Monad]]
revTreeZipper' :: TravelTree a
 
revTreeZipper' = do t <- getTree
 
case t of
 
Branch _ _ -> do left
 
l' <- revTreeZipper'
 
up
 
right
 
r' <- revTreeZipper'
 
up
 
putTree $ Branch r' l'
 
Leaf x -> return $ Leaf x
 
</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 "B-Trees", 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)
Computations in
Travel
are stateful.
Loc c a
is a type for storing the location within a structure.
struct
should be the substructure that the
Loc
is refering to, and
cxt
the "context" of the substructure; i.e. the rest of the structure.
Loc
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
Travel
monad use a zipper.

[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 (B-Trees; 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
These are direct front-doors for State's
get
,
put
and
modify
, and all three return the substructure after any applicable modifications.

[edit] 2.3 Exit points

To get out of the monad, use
traverse
:
traverse :: Loc c a            -- starting location (initial state)
         -> Travel (Loc c a) a -- locational computation to use
         -> a                  -- resulting substructure
Again, this is just a front-door for
evalState
. Note that you have to give a
Loc
as a starting state. Both the libraries provided supply a
getTop
function, which takes a tree and returns the
Loc
corresponding to the top of the tree. Thus a typical call to
traverse
might look like:
let t = Branch (Leaf 1) (Branch (Leaf 2) (Leaf 3))
in (getTop t) `traverse` (left >> swap >> right)

[edit] 3 Examples

Travel
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:
  • TravelTree for binary trees.
  • TravelBTree for B-Trees; 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 -fglasgow-exts #-}
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 Zipper-based file system.