https://wiki.haskell.org/api.php?action=feedcontributions&user=Iavor&feedformat=atomHaskellWiki - User contributions [en]2024-03-29T00:10:51ZUser contributionsMediaWiki 1.35.5https://wiki.haskell.org/index.php?title=Zipper&diff=21074Zipper2008-05-24T22:49:58Z<p>Iavor: </p>
<hr />
<div>The Zipper is an idiom that uses the idea of “context” to the means of<br />
manipulating locations in a data structure. [[Zipper monad]] is a monad<br />
which implements the zipper for binary trees.<br />
<br />
__TOC__<br />
<br />
Sometimes you want to manipulate a ''location'' inside a data structure,<br />
rather than the data itself. For example, consider a simple binary tree type:<br />
<br />
<haskell><br />
data Tree a = Fork (Tree a) (Tree a) | Leaf a<br />
</haskell><br />
<br />
and a sample tree t:<br />
{|<br />
| <haskell><br />
t = Fork (Fork (Leaf 1)<br />
(Leaf 2))<br />
(Fork (Leaf 3)<br />
(Leaf 4))<br />
</haskell><br />
| [[Image:Tree-12-34.png]]<br />
|}<br />
Each subtree of this tree occupies a certain location in the tree taken as a whole. The location consists of the subtree, along with the rest of the tree, which we think of the ''context'' of that subtree. For example, the context of<br />
<br />
<haskell><br />
Leaf 2<br />
</haskell><br />
<br />
in the above tree is<br />
<br />
{|<br />
| <haskell><br />
Fork (Fork (Leaf 1) @)<br />
(Fork (Leaf 3) (Leaf 4))<br />
</haskell><br />
| [[Image:Context-1X-34.png]]<br />
|}<br />
where @ marks a hole: the spot that the subtree appears in. This is the way we shall implement a tree with a focus. One way of expressing this context is as a path from the root of the tree to the hole (to which the required subtree will be attached). To reach our subtree, we needed to go down the left branch, and then down the right one. Note that the context is essentially a way of representing the tree, “missing out” a subtree (the subtree we are interested in). <br />
<br />
A naive implementation of the context, inspired directly by the graphical representation might be to use <hask>Tree (Maybe a)</hask> instead of <hask>Tree a</hask>. However, this would lose an essential point: in any given context, there is exactly one hole.<br />
<br />
Therefore, we will represent a context as follows:<br />
<br />
<haskell><br />
data Cxt a = Top | L (Cxt a) (Tree a) | R (Tree a) (Cxt a)<br />
</haskell><br />
<br />
<code>L c t</code> represents the left part of a branch of which the right part was <code>t</code> and whose parent had context <code>c</code>. The <code>R</code> constructor is similar. <code>Top</code> represents the top of a tree.<br />
<br />
Remarks:<br />
* In fact, this is equivalent to a list, whose elements are the appropriate collateral trees, each element labeled with the information which direction was chosen:<br />
:<hask>type Context a = [(Direction, Tree a)]</hask><br />
:<hask>data Direction = Lft | Rght</hask><br />
* We chose to propagate from the hole towards the root. This is an independent idea of the above considerations: it is not the unicity of the hole that forced us to do so. It is simply more efficient if we want to define operations later for a tree with a focus (move focus left, right, up).<br />
* Note that in the original paper, Huet dealt with B-trees (ones where nodes have arbitrary numbers of branches), so at each node, a list is used instead of the two (Tree a) parameters to represent children. Later we shall see that the solution of the problem can be formalized in a general way which covers solutions for both kinds of trees, as special cases.<br />
<br />
Using this datatype, we can rewrite the sample context above in proper Haskell:<br />
<br />
<haskell><br />
R (Leaf 1) (L Top (Fork (Leaf 3) (Leaf 4)))<br />
</haskell><br />
<br />
Note that the context is actually written by giving the path from the subtree to the root (rather than the other way round):<br />
{| border=1<br />
| <math>c_0</math><br />
| <math>\begin{matrix}\mathrm{R\;(Leaf\;1)}\;\underbrace{\mathrm{(L\;Top\;(Fork\;(Leaf\;3)\;(Leaf\;4)))}}\\\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;c_1\end{matrix}</math><br />
| [[Image:Context-1X-34.png]]<br />
|-<br />
| <math>c_1</math><br />
| <math>\begin{matrix}\mathrm{L}\;\underbrace{\mathrm{Top}}\;\mathrm{(Fork\;(Leaf\;3)\;(Leaf\;4))}\\\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!c_2\end{matrix}</math><br />
| [[Image:Context-X-34.png]]<br />
|-<br />
| <math>c_2</math><br />
| Top<br />
| [[Image:Top.png]]<br />
|}<br />
<br />
Or the more deconstructed representation:<br />
{| border=1<br />
| <math>\left[\begin{matrix}\mathrm{(Rght,\;Leaf\;1),\;\underbrace{\mathrm{(Lft,\;Fork\;(Leaf\;3)\;(Leaf\;4))}}}\\\underbrace{\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;c_1\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;}\\c_0\end{matrix}\right]</math><br />
| [[Image:Path-1X-34.png]]<br />
|}<br />
where <math>c_0</math>, <math>c_1</math> are the appropriate correspondents of the <math>c_0</math>, <math>c_1</math> of the previous image. It is the empty list that represents <math>c_2</math>.<br />
<br />
Now we can define a tree location:<br />
<br />
<haskell><br />
type Loc a = (Tree a, Cxt a)<br />
</haskell><br />
{|<br />
| [[Image:Circum-op12cl-34.png]]<br />
| [[Image:Mount-op12cl-34.png]]<br />
|}<br />
thus, a tree with a focus (drawn here as a tree with a marked subtree) shall be represented as “mounting” the focus (a tree) into the hole of the appropriate context.<br />
<br />
Now, we can define some useful functions for manipulating locations in a tree:<br />
<br />
<haskell><br />
left :: Loc a -> Loc a<br />
left (Fork l r, c) = (l, L c r)<br />
<br />
right :: Loc a -> Loc a<br />
right (Fork l r, c) = (r, R l c)<br />
<br />
top :: Tree a -> Loc a<br />
top t = (t, Top)<br />
<br />
up :: Loc a -> Loc a<br />
up (t, L c r) = (Fork t r, c)<br />
up (t, R l c) = (Fork l t, c)<br />
<br />
upmost :: Loc a -> Loc a<br />
upmost l@(t, Top) = l<br />
upmost l = upmost (up l)<br />
<br />
modify :: Loc a -> (Tree a -> Tree a) -> Loc a<br />
modify (t, c) f = (f t, c)<br />
</haskell><br />
<br />
It is instructive to look at an example of how a location gets transformed as we move from root to leaf. Recall our sample tree t. Let's name some of the relevant subtrees for brevity:<br />
<br />
<haskell><br />
t = let tl = Fork (Leaf 1) (Leaf 2)<br />
tr = Fork (Leaf 3) (Leaf 4)<br />
in Fork tl tr<br />
</haskell><br />
<br />
Then to reach the location of <code>Leaf 2</code>:<br />
<br />
<haskell><br />
(right . left . top) t<br />
= (right . left) (t, Top)<br />
= right (tl, L Top tr)<br />
= (Leaf 2, R (Leaf 1) (L Top tr))<br />
</haskell><br />
<br />
To reach that location and replace <code>Leaf 2</code> by <code>Leaf 0</code>:<br />
<br />
<haskell><br />
modify ((right . left . top) t) (\_ -> Leaf 0)<br />
= ...<br />
= (Leaf 0, R (Leaf 1) (L Top tr))<br />
</haskell><br />
<br />
Afterwards some may like to continue walking to other parts of the new tree, in which case continue applying <code>left</code>, <code>right</code>, and <code>up</code>.<br />
<br />
Some others may like to retrieve the new tree (and possibly forget about locations), in which case <code>upmost</code> is useful:<br />
<br />
<haskell><br />
(fst . upmost) (modify ((right . left . top) t) (\_ -> Leaf 0))<br />
= (fst . upmost) (Leaf 0, R (Leaf 1) (L Top tr))<br />
= fst (Fork (Fork (Leaf 1)<br />
(Leaf 0))<br />
tr<br />
, Top)<br />
= Fork (Fork (Leaf 1)<br />
(Leaf 0))<br />
tr<br />
</haskell><br />
<br />
== Automation ==<br />
<br />
There's a principled way to get the necessary types for contexts and the<br />
context filling functions, namely by differentiating the data structure.<br />
[http://www.cs.nott.ac.uk/~ctm/ Some relevant papers].<br />
<br />
For an actual implementation in [[Generic Haskell]], see the paper [http://www.cs.uu.nl/~johanj/publications/tidata.pdf Type-indexed data types] by Ralf Hinze, Johan Jeuring and Andres Löh, or a similar paper [http://www.cs.uu.nl/~johanj/publications/ghpractice.pdf Generic Haskell: Applications] by Ralf Hinze and Johan Jeuring<br />
<br />
== Alternative formulation ==<br />
<br />
The dual of Huet zipper is generic zipper -- which is a derivative of<br />
a traversal function rather than that of a data structure.<br />
Unlike Huet zipper,<br />
generic zipper can be implemented once and for all data structures,<br />
in the existing Haskell.<br />
[http://pobox.com/~oleg/ftp/Computation/Continuations.html#zipper Generic Zipper and its applications]<br />
<br />
== Comonads and monads ==<br />
<br />
Comonads<br />
* [http://cs.ioc.ee/~tarmo/tsem05/uustalu0812-slides.pdf Structured Computation on Trees or, What’s Behind That Zipper? (A Comonad)], slides by Tarmo Uustalu<br />
* [http://cs.ioc.ee/~tarmo/papers/tfp05-book.pdf Comonadic functional attribute evaluation] by Tarmo Uustalu1 and Varmo Vene, a more detailed treatment<br />
* [http://www.cs.nott.ac.uk/~txa/monads-more-4.pdf Monads and more (Part 4)] by Tarmo Uustalu<br />
* [http://sigfpe.blogspot.com/2006/12/evaluating-cellular-automata-is.html Evaluating cellular automata is comonadic], part of Sigfpe's ''A Neighborhood of Infinity''<br />
Monads:<br />
* [http://sigfpe.blogspot.com/2007/01/monads-hidden-behind-every-zipper.html The Monads Hidden Behind Every Zipper], part of Sigfpe's ''A Neighborhood of Infinity''<br />
<br />
== Applications ==<br />
<br />
;[http://okmij.org/ftp/Computation/Continuations.html#zipper-fs ZipperFS] <br />
:Oleg Kiselyov's zipper-based [[Libraries and tools/Operating system|file server/OS]] where threading and exceptions are all realized via [[Library/CC-delcont|delimited continuation]]s.<br />
;[http://cgi.cse.unsw.edu.au/~dons/blog/2007/05/17 Roll Your Own Window Manager: Tracking Focus with a Zipper]<br />
:describes the use of zippers in [http://www.xmonad.org/ xmonad].<br />
* The [http://hackage.haskell.org/cgi-bin/hackage-scripts/package/AvlTree AVL Tree] package contains a zipper for navigating AVL trees.<br />
* A zipper for navigating rose trees (as found in the standard <code>Data.Tree</code> library) is available in the [http://code.haskell.org/yi/Data/Tree/ Yi code repository].<br />
* [[Image:RoseZipper.hs|An implementation of a zipper]] for navigating rose trees (as found in the standard <code>Data.Tree</code> library).<br />
<br />
<br />
== Further reading ==<br />
* Gerard Huet's [http://www.st.cs.uni-sb.de/edu/seminare/2005/advanced-fp/docs/huet-zipper.pdf paper] where he originally proposed the concept of a zipper<br />
* [http://www.informatik.uni-bonn.de/~ralf/publications/TheWeb.ps.gz The Web] extends this pattern.<br />
* [http://sigfpe.blogspot.com/2006/09/infinitesimal-types.html Infinitesimal Types] writes on interesting generalizations (e.g. derivative of a type — to the analogy of the notion of derivative in rings, e.g. in analysis or for polinomials)<br />
* [http://en.wikibooks.org/wiki/Haskell/Zippers Haskell/Zippers] on Wikibooks, a detailed treatment of zippers, and generalizing the notion as derivative<br />
* [http://okmij.org/ftp/Computation/Continuations.html#zipper Generic Zipper and its applications], writing that “Zipper can be viewed as a [[Library/CC-delcont|delimited continuation]] reified as a data structure” (link added).<br />
<br />
[[Category:Idioms]]</div>Iavorhttps://wiki.haskell.org/index.php?title=File:RoseZipper.hs&diff=21073File:RoseZipper.hs2008-05-24T22:48:25Z<p>Iavor: An implementation of a zipper for navigating rose trees.</p>
<hr />
<div>An implementation of a zipper for navigating rose trees.</div>Iavorhttps://wiki.haskell.org/index.php?title=New_monads&diff=18690New monads2008-01-26T22:46:33Z<p>Iavor: </p>
<hr />
<div>__TOC__<br />
<br />
Remember to add a [ [ Category:Code ] ] tag to any new sub-pages.<br />
<br />
== MonadBase ==<br />
<br />
It seems that the liftIO function from MonadIO can be generalized to access whatever the base of a transformer stack happens to be. So there is no need for a liftSTM, liftST, etc.<br />
<br />
View [[New monads/MonadBase]].<br />
<br />
== MonadLib ==<br />
<br />
This is by Iavor S. Diatchki and can be found at <br />
<br />
http://www.galois.com/~diatchki/monadLib/<br />
<br />
The most recent version is available from a darcs repository located at:<br />
<br />
http://darcs.haskell.org/packages/monadLib/<br />
<br />
It is a new version of the mtl package with base monads: Id, and Lift, and transformers ReaderT, WriterT, StateT, ExceptionT, ChoiceT, and ContT.<br />
<br />
It also defines BaseM which is like MonadBase above.<br />
<br />
== MonadRandom ==<br />
<br />
A simple monad transformer to allow computations in the transformed monad to generate random values.<br />
<br />
View [[New monads/MonadRandom]].<br />
<br />
===MonadRandomSplittable===<br />
A refinement of MonadRandom to integrate RandomGen's split function.<br />
<br />
View at [[New monads/MonadRandomSplittable]]<br />
<br />
== MaybeT ==<br />
<br />
The Maybe monad deserves a transformer, just like the other classic monads.<br />
<br />
View [[New monads/MaybeT]].<br />
<br />
== MonadSupply ==<br />
<br />
Here is a simple monad/monad transformer for computations which consume values from a (finite or infinite) supply. Note that due to pattern matching, running out of supply in a non-MonadZero monad will cause an error.<br />
<br />
View [[New monads/MonadSupply]].<br />
<br />
== MonadUndo ==<br />
<br />
Here is a modified state monad transformer for keeping track of undo/redo states automatically.<br />
<br />
View [[New monads/MonadUndo]].<br />
<br />
== MonadUnique ==<br />
<br />
This is a simple (trivial) monad transformer for supplying unique integer values to an algorithm.<br />
<br />
View [[New monads/MonadUnique]].<br />
<br />
== MonadSTO ==<br />
<br />
Here's an extension of the ST monad in which the references are ordered and showable (they list their creation index).<br />
<br />
View [[New monads/MonadSTO]].<br />
<br />
== MonadNondet ==<br />
<br />
There is a [[Sudoku#Monadic_Non-Deterministic_Solver | MonadNondet]] that when compiled with optimizations outperforms List.<br />
<br />
== Stateful nondeterminism ==<br />
<br />
There is a [[Stateful nondeterminism]] monad for if you want to do nondeterministic computation with local states for each of your threads and a global state shared by all your threads.<br />
<br />
== MonadAdvSTM ==<br />
<br />
Here is an extension of STM to easy interaction with IO after committing or retrying. Inspired by Simon P-J.<br />
<br />
View [[New monads/MonadAdvSTM]].<br />
<br />
== TimedStateT ==<br />
<br />
A monad transformer which combines State, Reader, and Error functionality to give the effect of a StateT monad which checks clock-time and stops the current computation if a period is exceeded.<br />
<br />
darcs get http://www.mapcar.org/haskell/TimedStateT/<br />
<br />
Haddocks: http://www.mapcar.org/haskell/TimedStateT/dist/doc/html/<br />
<br />
== MonadExit ==<br />
<br />
The Exit monad provides [[short-circuiting]] for complex program flow logic.<br />
<br />
If you are using CPS or MonadCont only for this purpose, the Exit monad will likely simplify your program considerably.<br />
<br />
View [[New monads/MonadExit|MonadExit]].<br />
<br />
== MonadSplit ==<br />
<br />
Represents the class of monads such that <br />
<br />
<haskell>l == (msplit l >>= \(x,xs) -> return x `mplus` xs)</haskell><br />
<br />
In English, msplit is a counterpart to "mplus".<br />
<br />
Using this, you can redefine many of the functions which previously depended on lists: foldM, scanM, inits, tails, and some derived functions.<br />
<br />
Note: A more general form of this monad,<br />
[http://haskell.org/ghc/docs/latest/html/libraries/base/Data-Foldable.html Data.Foldable], is now part of the<br />
[http://haskell.org/ghc/docs/latest/html/libraries/ standard libraries].<br />
<br />
View [[New monads/MonadSplit]].<br />
<br />
== Lazy and Strict variants ==<br />
<br />
This section contains monads that have interesting Strict or Lazy properties.<br />
<br />
=== LazyWriterT ===<br />
<br />
This came up on the mailing list: Why is WriterT never lazy? The answer is it does not use lazy patterns with "~". So here is a more useful [[New monads/LazyWriterT]] that add two "~" to the definition of (>>=) and renames WriterT to LazyWriterT.<br />
<br />
=== Strict RWS ===<br />
<br />
This was contribute by John Meacham on on the haskell-cafe mailing list. [[New monads/UnboxedRWS]] is an strict variant of RWS.<br />
<br />
[[Category:Idioms]]<br />
[[Category:Monad]]<br />
[[Category:Proposals]]</div>Iavorhttps://wiki.haskell.org/index.php?title=New_monads&diff=18689New monads2008-01-26T22:43:49Z<p>Iavor: </p>
<hr />
<div>__TOC__<br />
<br />
Remember to add a [ [ Category:Code ] ] tag to any new sub-pages.<br />
<br />
== MonadBase ==<br />
<br />
It seems that the liftIO function from MonadIO can be generalized to access whatever the base of a transformer stack happens to be. So there is no need for a liftSTM, liftST, etc.<br />
<br />
View [[New monads/MonadBase]].<br />
<br />
== MonadLib ==<br />
<br />
This is by Iavor S. Diatchki and can be found at <br />
http://www.galois.com/~diatchki/monadLib/. The most recent version<br />
is available from a darcs repository located at:<br />
http://darcs.haskell.org/packages/monadLib/<br />
It is a new version of the mtl package with transformers: ReaderT WriterT StateT ExceptionT ChoiceT ContT<br />
<br />
It also defines BaseM which is like MonadBase above.<br />
<br />
== MonadRandom ==<br />
<br />
A simple monad transformer to allow computations in the transformed monad to generate random values.<br />
<br />
View [[New monads/MonadRandom]].<br />
<br />
===MonadRandomSplittable===<br />
A refinement of MonadRandom to integrate RandomGen's split function.<br />
<br />
View at [[New monads/MonadRandomSplittable]]<br />
<br />
== MaybeT ==<br />
<br />
The Maybe monad deserves a transformer, just like the other classic monads.<br />
<br />
View [[New monads/MaybeT]].<br />
<br />
== MonadSupply ==<br />
<br />
Here is a simple monad/monad transformer for computations which consume values from a (finite or infinite) supply. Note that due to pattern matching, running out of supply in a non-MonadZero monad will cause an error.<br />
<br />
View [[New monads/MonadSupply]].<br />
<br />
== MonadUndo ==<br />
<br />
Here is a modified state monad transformer for keeping track of undo/redo states automatically.<br />
<br />
View [[New monads/MonadUndo]].<br />
<br />
== MonadUnique ==<br />
<br />
This is a simple (trivial) monad transformer for supplying unique integer values to an algorithm.<br />
<br />
View [[New monads/MonadUnique]].<br />
<br />
== MonadSTO ==<br />
<br />
Here's an extension of the ST monad in which the references are ordered and showable (they list their creation index).<br />
<br />
View [[New monads/MonadSTO]].<br />
<br />
== MonadNondet ==<br />
<br />
There is a [[Sudoku#Monadic_Non-Deterministic_Solver | MonadNondet]] that when compiled with optimizations outperforms List.<br />
<br />
== Stateful nondeterminism ==<br />
<br />
There is a [[Stateful nondeterminism]] monad for if you want to do nondeterministic computation with local states for each of your threads and a global state shared by all your threads.<br />
<br />
== MonadAdvSTM ==<br />
<br />
Here is an extension of STM to easy interaction with IO after committing or retrying. Inspired by Simon P-J.<br />
<br />
View [[New monads/MonadAdvSTM]].<br />
<br />
== TimedStateT ==<br />
<br />
A monad transformer which combines State, Reader, and Error functionality to give the effect of a StateT monad which checks clock-time and stops the current computation if a period is exceeded.<br />
<br />
darcs get http://www.mapcar.org/haskell/TimedStateT/<br />
<br />
Haddocks: http://www.mapcar.org/haskell/TimedStateT/dist/doc/html/<br />
<br />
== MonadExit ==<br />
<br />
The Exit monad provides [[short-circuiting]] for complex program flow logic.<br />
<br />
If you are using CPS or MonadCont only for this purpose, the Exit monad will likely simplify your program considerably.<br />
<br />
View [[New monads/MonadExit|MonadExit]].<br />
<br />
== MonadSplit ==<br />
<br />
Represents the class of monads such that <br />
<br />
<haskell>l == (msplit l >>= \(x,xs) -> return x `mplus` xs)</haskell><br />
<br />
In English, msplit is a counterpart to "mplus".<br />
<br />
Using this, you can redefine many of the functions which previously depended on lists: foldM, scanM, inits, tails, and some derived functions.<br />
<br />
Note: A more general form of this monad,<br />
[http://haskell.org/ghc/docs/latest/html/libraries/base/Data-Foldable.html Data.Foldable], is now part of the<br />
[http://haskell.org/ghc/docs/latest/html/libraries/ standard libraries].<br />
<br />
View [[New monads/MonadSplit]].<br />
<br />
== Lazy and Strict variants ==<br />
<br />
This section contains monads that have interesting Strict or Lazy properties.<br />
<br />
=== LazyWriterT ===<br />
<br />
This came up on the mailing list: Why is WriterT never lazy? The answer is it does not use lazy patterns with "~". So here is a more useful [[New monads/LazyWriterT]] that add two "~" to the definition of (>>=) and renames WriterT to LazyWriterT.<br />
<br />
=== Strict RWS ===<br />
<br />
This was contribute by John Meacham on on the haskell-cafe mailing list. [[New monads/UnboxedRWS]] is an strict variant of RWS.<br />
<br />
[[Category:Idioms]]<br />
[[Category:Monad]]<br />
[[Category:Proposals]]</div>Iavorhttps://wiki.haskell.org/index.php?title=Tying_the_Knot&diff=10039Tying the Knot2007-01-10T22:33:23Z<p>Iavor: </p>
<hr />
<div>== Introduction ==<br />
<br />
This example illustrates different ways to define recursive data structures.<br />
To demonstrate the different techniques we show how to solve the same problem---writing an interpreter for a simple programming language---in three different ways. This is a nice example because, (i) it is interesting, (ii) the abstract syntax of the language contains mutually recursive structures, and (iii) the interpreter illustrates how to work with the recursive structures.<br />
<br />
(It would be useful to have some more text describing the examples.)<br />
<br />
== Download the Files ==<br />
* [[Media:Interp1.lhs|Direct Recursion]]<br />
* [[Media:Interp2.lhs|Tying the Knot]]<br />
* [[Media:Interp3.lhs|Tying the Knot with GADTs]]<br />
<br />
<br />
[[Category:Code]]<br />
[[Category:Idioms]]</div>Iavorhttps://wiki.haskell.org/index.php?title=Tying_the_Knot&diff=10037Tying the Knot2007-01-10T21:57:42Z<p>Iavor: </p>
<hr />
<div>== Introduction ==<br />
<br />
This example illustrates different ways to define recursive data structures.<br />
To demonstrate the different techniques we show how to solve the same problem---writing an interpreter for a simple programming language---in three different ways. This is a nice example because, (i) it is interesting, (ii) the abstract syntax of the language contains mutually recursive structures, and (iii) the interpreter illustrates how to work with the recursive structures.<br />
<br />
(It would be useful to have some more text describing the examples.)<br />
<br />
== Download the Files ==<br />
* [[Image:Interp1.lhs|Direct Recursion]]<br />
* [[Image:Interp2.lhs|Tying the Knot]]<br />
* [[Image:Interp3.lhs|Tying the Knot with GADTs]]<br />
<br />
<br />
[[Category:Code]]<br />
[[Category:Idioms]]</div>Iavorhttps://wiki.haskell.org/index.php?title=Tying_the_Knot&diff=10036Tying the Knot2007-01-10T21:57:13Z<p>Iavor: </p>
<hr />
<div>== Introduction ==<br />
<br />
This example illustrates different ways to define recursive data structures.<br />
To demonstrate the different techniques we show how to solve the same problem---writing an interpreter for a simple programming language---in three different ways. This is a nice example because, (i) it is interesting, (ii) the abstract syntax of the language contains mutually recursive structures, and (iii) the interpreter illustrates how to work with the recursive structures.<br />
<br />
(It would be useful to have some more text describing the examples.)<br />
<br />
== Download the Files ==<br />
* [[Image:Interp1.lhs|Direct Recursion]]<br />
* [[Image:Interp2.lhs|Tying the Knot]]<br />
* [[Image:Interp3.lhs|Tying the Knot with GADTS]]<br />
<br />
<br />
[[Category:Code]]<br />
[[Category:Idioms]]</div>Iavorhttps://wiki.haskell.org/index.php?title=Tying_the_Knot&diff=10035Tying the Knot2007-01-10T21:56:11Z<p>Iavor: </p>
<hr />
<div>== Introduction ==<br />
<br />
This example illustrates different ways to define recursive data structures.<br />
To demonstrate the different techniques we show how to solve the same problem---writing an interpreter for a simple programming language---in three different ways. This is a nice example because, (i) it is interesting, (ii) the abstract syntax of the language contains mutually recursive structures, and (iii) the interpreter illustrates how to work with recursive structures.<br />
<br />
(It would be useful to have some more text describing the examples.)<br />
<br />
== Download the Files ==<br />
* [[Image:Interp1.lhs|Direct Recursion]]<br />
* [[Image:Interp2.lhs|Tying the Knot]]<br />
* [[Image:Interp3.lhs|Tying the Knot with GADTS]]<br />
<br />
<br />
[[Category:Code]]<br />
[[Category:Idioms]]</div>Iavorhttps://wiki.haskell.org/index.php?title=Tying_the_Knot&diff=10034Tying the Knot2007-01-10T21:40:17Z<p>Iavor: </p>
<hr />
<div>This example illustrates different ways to define recursive data structures.<br />
<br />
== Download the files ==<br />
* [[Image:Interp1.lhs|Direct Recursion]]<br />
* [[Image:Interp2.lhs|Tying the Knot]]<br />
* [[Image:Interp3.lhs|Tying the Knot with GADTS]]</div>Iavorhttps://wiki.haskell.org/index.php?title=Tying_the_Knot&diff=10033Tying the Knot2007-01-10T21:37:54Z<p>Iavor: </p>
<hr />
<div>This example illustrates different ways to define recursive data structures.<br />
<br />
* [[Image:Interp1.lhs|Direct Recursion]]<br />
* [[Image:Interp2.lhs|Tying the Knot]]<br />
* [[Image:Interp3.lhs|Tying the Knot with GADTS]]</div>Iavorhttps://wiki.haskell.org/index.php?title=File:Interp3.lhs&diff=10032File:Interp3.lhs2007-01-10T21:36:24Z<p>Iavor: </p>
<hr />
<div></div>Iavorhttps://wiki.haskell.org/index.php?title=File:Interp2.lhs&diff=10031File:Interp2.lhs2007-01-10T21:36:12Z<p>Iavor: </p>
<hr />
<div></div>Iavorhttps://wiki.haskell.org/index.php?title=Tying_the_Knot&diff=10030Tying the Knot2007-01-10T21:35:45Z<p>Iavor: </p>
<hr />
<div>This example illustrates different ways to define recursive data structures.<br />
<br />
* [[Image:Interp1.lhs]]<br />
* [[Image:Interp2.lhs]]<br />
* [[Image:Interp3.lhs]]</div>Iavorhttps://wiki.haskell.org/index.php?title=File:Interp1.lhs&diff=10029File:Interp1.lhs2007-01-10T21:34:37Z<p>Iavor: </p>
<hr />
<div></div>Iavorhttps://wiki.haskell.org/index.php?title=Tying_the_Knot&diff=10027Tying the Knot2007-01-10T21:30:16Z<p>Iavor: </p>
<hr />
<div>This example illustrates different ways to define recursive data structures.</div>Iavorhttps://wiki.haskell.org/index.php?title=Example_code&diff=10026Example code2007-01-10T21:29:16Z<p>Iavor: </p>
<hr />
<div>To get a feel for what real world Haskell looks like, here are some<br />
examples from various popular [[Libraries_and_tools|Haskell projects]].<br />
To start learning the language, good places to start are<br />
[[Learning_Haskell|here]], [[Haskell_in_5_steps|here]] and<br />
[[Books_and_tutorials|here]].<br />
<br />
More code may be found [http://haskell.org/haskellwiki/Category:Code on the wiki].<br />
<br />
<br />
=== Library code ===<br />
<br />
Library code usually differs from application code: it is often highly<br />
structured, and documented with [http://haskell.org/haddock haddock],<br />
and can be rather optimised. Some instructive examples (syntax<br />
highlighting by [http://www.cs.york.ac.uk/fp/darcs/hscolour/ hscolour]):<br />
<br />
* [http://www.cse.unsw.edu.au/~dons/data/Prelude.html A Haskell 98 Prelude.hs], foundational Haskell library ([http://www.cse.unsw.edu.au/~dons/data/Prelude.hs raw], [http://haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html docs])<br />
* [[Simple_unix_tools|Unix.hs]], simple unix tools, for beginner Haskellers ([http://www.cse.unsw.edu.au/~dons/data/Basics.hs raw])<br />
* [http://www.cse.unsw.edu.au/~dons/data/List.html List.hs], the standard list library ([http://www.cse.unsw.edu.au/~dons/data/List.hs raw], [http://haskell.org/ghc/docs/latest/html/libraries/base/Data-List.html docs])<br />
* [http://www.cse.unsw.edu.au/~dons/data/Maybe.html Maybe.hs], the <code>Maybe</code> type ([http://www.cse.unsw.edu.au/~dons/data/Maybe.hs raw], [http://haskell.org/ghc/docs/latest/html/libraries/base/Data-Maybe.html docs])<br />
* [http://www.cse.unsw.edu.au/~dons/data/Map.html Map.hs], the standard finite map ([http://darcs.haskell.org/packages/base/Data/Map.hs raw], [http://haskell.org/ghc/docs/latest/html/libraries/base/Data-Map.html docs])<br />
* [http://www.cse.unsw.edu.au/~dons/data/Graph.html Graph.hs], a graph type ([http://darcs.haskell.org/packages/base/Data/Graph.hs raw], [http://haskell.org/ghc/docs/latest/html/libraries/base/Data-Graph.html docs])<br />
* [http://www.cse.unsw.edu.au/~dons/data/Monad.html Monad.hs], basic monad support ([http://darcs.haskell.org/packages/base/Control/Monad.hs raw], [http://haskell.org/ghc/docs/latest/html/libraries/base/Control-Monad.html docs])<br />
* [http://www.cse.unsw.edu.au/~dons/data/QuickCheck.html QuickCheck.hs], a testing framework ([http://darcs.haskell.org/packages/QuickCheck/Test/QuickCheck.hs raw], [http://haskell.org/ghc/docs/latest/html/libraries/QuickCheck/Test-QuickCheck.html docs])<br />
* [http://www.cse.unsw.edu.au/~dons/data/HughesPJ.html PrettyPrint.hs], a pretty printing library ([http://darcs.haskell.org/packages/base/Text/PrettyPrint/HughesPJ.hs raw], [http://haskell.org/ghc/docs/latest/html/libraries/base/Text-PrettyPrint-HughesPJ.html docs])<br />
* [http://www.cse.unsw.edu.au/~dons/data/State.html State.hs], a state monad ([http://darcs.haskell.org/packages/mtl/Control/Monad/State.hs raw], [http://haskell.org/ghc/docs/latest/html/libraries/mtl/Control-Monad-State.html docs])<br />
* [http://www.cse.unsw.edu.au/~dons/data/Music.html Music.hs], a music composition system (literate latex-style Haskell) ([http://darcs.haskell.org/haskore/src/Haskore/Music.lhs raw], [http://haskell.org/haskore/ home])<br />
* [http://www.ninebynine.org/Software/Swish-0.2.1/HaskellRDF/Dfa/Dfa.lhs Dfa.lhs], finite automata (literate Bird-style Haskell)<br />
* [http://www.cse.unsw.edu.au/~dons/data/RedBlackTree.html RedBlackTree.hs], a red-black tree ([http://www.polyomino.f2s.com/david/haskell/hs/redblacktree.hs.txt raw])<br />
* [http://www.cse.unsw.edu.au/~dons/data/Prime.html Prime.hs], prime numbers ([http://andrew.bromage.org/darcs/numbertheory/Math/Prime.hs raw])<br />
* [http://www.cse.unsw.edu.au/~dons/data/Foldable.html Foldable.hs], traversable data structures ([http://darcs.haskell.org/packages/base/Data/Foldable.hs raw])<br />
* [http://www.cse.unsw.edu.au/~dons/data/ByteString.html ByteString.hs], high-performance string type ([http://darcs.haskell.org/packages/base/Data/ByteString.hs raw], [http://www.cse.unsw.edu.au/~dons/fps/Data-ByteString.html docs], [http://www.cse.unsw.edu.au/~dons/fps.html home])<br />
* [http://www.cse.unsw.edu.au/~dons/data/SmallCheck.html SmallCheck.hs], a testing framework ([http://www.cse.unsw.edu.au/~dons/code/lambdabot/scripts/SmallCheck.hs raw])<br />
* [http://haskell.org/haskellwiki/Darcs_repositories More code ...]<br />
<br />
=== Application code ===<br />
<br />
Code from popular Haskell applications. Such code often makes use of a<br />
monadic IO, and sometimes other advanced features such as concurrency:<br />
<br />
* [http://www.abridgegame.org/repos/darcs-unstable/PatchCommute.lhs Darcs], a revision control system (uses literate latex Haskell style) ([http://darcs.net home])<br />
* [http://svn.openfoundry.org/pugs/src/Pugs/Eval.hs Pugs], a perl6 implementation ([http://pugscode.org home])<br />
* [http://www.cse.unsw.edu.au/~dons/code/yi/Yi/Core.hs Yi], a text editor, ([http://www.cse.unsw.edu.au/~dons/yi.html home])<br />
* [http://j.mongers.org/pub/haskell/darcs/conjure/Conjure/Torrent.hs Conjure], a bittorrent client<br />
* [http://darcs.haskell.org/~lemmih/downNova/src/Torrent.hs DownNova], a file downloading program<br />
* [http://www.cs.york.ac.uk/fp/darcs/cpphs/Language/Preprocessor/Cpphs/Tokenise.hs cpphs], an implementation of the C preprocessor ([http://www.cs.york.ac.uk/fp/cpphs/ home])<br />
* [http://darcs.haskell.org/ghc/compiler/simplCore/Simplify.lhs GHC], a Haskell compiler (literate latex style) ([http://haskell.org/ghc home])<br />
* [http://www.augustsson.net/Darcs/Djinn/LJT.hs Djinn], a theorem prover ([http://darcs.augustsson.net/Darcs/Djinn home])<br />
* [http://darcs.haskell.org/c2hs/c2hs/c/CTrav.hs c2hs], a C to Haskell interface generator ([http://www.cse.unsw.edu.au/~chak/haskell/c2hs/ home])<br />
* [http://www.cse.unsw.edu.au/~dons/code/lambdabot/LBState.hs Lambdabot], an IRC bot ([http://www.cse.unsw.edu.au/~dons/lambdabot.html home])<br />
* [http://www.cse.unsw.edu.au/~dons/code/hmp3/Core.hs hmp3], an curses mp3 player ([http://www.cse.unsw.edu.au/~dons/hmp3.html home])<br />
* [http://haskell.org/haskellwiki/Darcs_repositories More code ...]<br />
<br />
== Examples ==<br />
<br />
; [[Tying the Knot]] : An example that illustrates different ways to define recursive data structures. The example defines a simple language (illustrating how to define some recursive structures) and an interpreter for the language (illustrating how to work with the recursive structures).<br />
<br />
<br />
[[Category:Code]]</div>Iavor