# Zipper monad

### From HaskellWiki

EndreyMark (Talk | contribs) m (Updating links to Zipper, according to its un-camelcase redirection) |
DavidHouse (Talk | contribs) (version 2) |
||

Line 1: | Line 1: | ||

− | The | + | The Travel 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. |

− | + | 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. | |

== Definition == | == Definition == | ||

<haskell> | <haskell> | ||

− | + | 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) | ||

</haskell> | </haskell> | ||

− | + | 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 == | ||

− | |||

− | |||

− | + | === 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 [[Zipper_monad/TravelTree|TravelTree]] (binary trees) or [[Zipper_monad/TravelBTree|TravelBTree]] (B-Trees; trees where each node has an arbitrary number of branches). | |

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

=== Mutation === | === Mutation === | ||

− | There are | + | There are three generic functions available for changing the structure: |

<haskell> | <haskell> | ||

− | + | getStruct :: Travel (Loc c a) a | |

− | + | putStruct :: a -> Travel (Loc c a) 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 | + | 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 54: | Line 35: | ||

<haskell> | <haskell> | ||

− | traverse :: | + | 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> | + | 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: |

− | + | ||

− | + | ||

− | + | ||

<haskell> | <haskell> | ||

− | t = | + | let t = Branch (Leaf 1) (Branch (Leaf 2) (Leaf 3)) |

− | + | in (getTop t) `traverse` (left >> swap >> right) | |

− | + | ||

− | + | ||

</haskell> | </haskell> | ||

− | + | == 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 Zipper | + | Here's the base Zipper monad in full ([http://haskell.org/sitewiki/images/3/36/Zipper.hs download]): |

<haskell> | <haskell> | ||

+ | {-# OPTIONS_GHC -fglasgow-exts #-} | ||

module Zipper where | module Zipper where | ||

− | -- A monad implementing | + | -- A monad implementing for traversing data structures |

− | -- http://haskell.org/haskellwiki/ | + | -- http://haskell.org/haskellwiki/Zipper_monad |

-------------------------------------------------------------------------------- | -------------------------------------------------------------------------------- | ||

import Control.Monad.State | import Control.Monad.State | ||

− | |||

− | data | + | 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 | |

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

</haskell> | </haskell> | ||

[[Category:Idioms]] | [[Category:Idioms]] |

## Revision as of 21:21, 19 April 2006

The Travel 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.

## Contents |

## 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)

## 2 Functions

### 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).

### 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

### 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)

## 3 Examples

- TravelTree for binary trees.
- TravelBTree for B-Trees; trees where each node has an arbitrary number of branches.

## 4 Code

Here's the base Zipper monad in full (download):

{-# 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