Arrow
From HaskellWiki
EndreyMark (Talk | contribs) m (``between'' example: expaining text rephrased) |
EndreyMark (Talk | contribs) (→Parser: Example quoted from Ross Paterson's A New Notation for Arrows) |
||
Line 32: | Line 32: | ||
The reasons why the arrow concept can solve important questions when designing a parser library are explained in [http://www.haskell.org/arrows/biblio.html Generalising Monads to Arrows] written by [http://www.cs.chalmers.se/~rjmh/ John Hughes]. |
The reasons why the arrow concept can solve important questions when designing a parser library are explained in [http://www.haskell.org/arrows/biblio.html Generalising Monads to Arrows] written by [http://www.cs.chalmers.se/~rjmh/ John Hughes]. |
||
− | A good example of the mentioned arrow parsers can be seen in [http://www.soi.city.ac.uk/~ross/papers/notation.html A New Notation for Arrows] written by [http://www.soi.city.ac.uk/%7Eross/ Ross Peterson]: figure 2, 4, 6 (page 3, 5, 6). |
+ | A good example of the mentioned arrow parsers can be seen in [http://www.soi.city.ac.uk/~ross/papers/notation.html A New Notation for Arrows] written by [http://www.soi.city.ac.uk/%7Eross/ Ross Paterson]: figure 2, 4, 6 (page 3, 5, 6): |
+ | :<math>\mathrm{expr} ::= \mathrm{term}\;\mathrm{exprTail}</math> |
||
+ | :<math>\mathrm{exprTail} ::= \mathbf{PLUS}\;\mathrm{term}\;\mathrm{exprTail}\;\vert\;\mathbf{MINUS}\;\mathrm{term}\;\mathrm{exprTail}\;\vert\;\epsilon</math> |
||
+ | is implemented by |
||
+ | <haskell> |
||
+ | data Expr = Plus Expr Expr | Minus Expr Expr | ... |
||
+ | |||
+ | expr :: ParseArrow () Expr |
||
+ | expr = proc () -> do |
||
+ | t <- term -< () |
||
+ | exprTail -< t |
||
+ | |||
+ | exprTail :: ParseArrow Expr Expr |
||
+ | exprTail = proc e -> do |
||
+ | symbol PLUS -< () |
||
+ | t <- term -< () |
||
+ | exprTail -< Plus e t |
||
+ | <+> do |
||
+ | symbol MINUS -< () |
||
+ | t <- term -< () |
||
+ | exprTail -< Minus e t |
||
+ | <+> returnA -< e |
||
+ | </haskell> |
||
An implementation: [http://www.cs.helsinki.fi/u/ekarttun/PArrows/ PArrows] written by [http://www.haskell.org/tmrwiki/EinarKarttunen Einar Karttunen]. |
An implementation: [http://www.cs.helsinki.fi/u/ekarttun/PArrows/ PArrows] written by [http://www.haskell.org/tmrwiki/EinarKarttunen Einar Karttunen]. |
Revision as of 19:10, 12 June 2006
import Control.Arrow |
Contents |
1 Introduction
Arrows: A General Interface to Computation written by Ross Peterson.
HaWiki's UnderstandingArrows.
Monad.Reader's ArrowsIntroduction article.
See also Research papers/Monads and arrows.
2 Practice
Reasons, when it may be worth of solving a specific problem with arrows (instead of monads) can be read in a message from Daan Leijen.
3 Library
Control.Arrow is the standard ibrary for arrows.
Arrow transformer library (see the bottom of the page) is an extension with arrow transformers, subclasses, useful data types (Data.Stream, Data.Sequence).
4 Examples
Various concepts follow here, which can be seen as concrete examples covered by the arrow concept. Not all of them provide links to Haskell-related materials: some of them are here only to give a self-contaned material (e.g. section #Automaton gives links only to the finite state concept itself.).
4.1 Parser
The reasons why the arrow concept can solve important questions when designing a parser library are explained in Generalising Monads to Arrows written by John Hughes.
A good example of the mentioned arrow parsers can be seen in A New Notation for Arrows written by Ross Paterson: figure 2, 4, 6 (page 3, 5, 6):
is implemented by
data Expr = Plus Expr Expr | Minus Expr Expr | ... expr :: ParseArrow () Expr expr = proc () -> do t <- term -< () exprTail -< t exprTail :: ParseArrow Expr Expr exprTail = proc e -> do symbol PLUS -< () t <- term -< () exprTail -< Plus e t <+> do symbol MINUS -< () t <- term -< () exprTail -< Minus e t <+> returnA -< e
An implementation: PArrows written by Einar Karttunen.
The funny thing which took a long time for me to understand arrow parsers is a sort of differential approach -- in contrast to the well-known parser approaches. (I mean, in some way well-known parsers are of differential approach too, in the sense that they manage state transitions where the states are remainder streams -- but here I mean being differential in another sense: arrow parsers seem to me differential in the way how they consume and produce values -- their input and output.)
The idea of borrowing this image from mathematical analysis comes from another topic: the version control systems article Integrals and derivatives written by Martin Pool uses a similar image.
Arrows and Computation written by Ross Paterson (pages 2, 6, 7) mentions that computation (e.g. state) is threaded through the operands of-- | Match zero or more occurences of the given parser. many :: MD i o -> MD i [o] many = MStar -- | Match one or more occurences of the given parser. many1 :: MD i o -> MD i [o] many1 x = (x &&& MStar x) >>> pure (\(b,bs) -> (b:bs))
between :: MD i t -> MD t close -> MD t o -> MD i o between open close real = open >>> (real &&& close) >>^ fst
A more complicated example (from the same module):
-- | Match one or more occurences of the given parser separated by the sepator. sepBy1 :: MD i o -> MD i o' -> MD i [o] sepBy1 p s = (many (p &&& s >>^ fst) &&& p) >>^ (\(bs,b) -> bs++[b])
4.2 Stream processor
The Lazy K programming language is an interesing esoteric language (from the family of pure, lazy functional languages), whose I/O concept is approached by streams.
4.2.1 Functional I/O, graphical user interfaces
On the Expressiveness of Purely Functional I/O Systems written by Paul Hudak and Raman S. Sundaresh.
Fudgets written by Thomas Hallgren and Magnus Carlsson. See also Arrows for Fudgets written by Magnus Carlsson, mentioning how these two concepts relate to each other.
4.2.2 Dataflow languages
Arrows and Computation written by Ross Paterson mentions how to mimick dataflow programming in (lazy) functional languages. See more on Lucid's own HaskellWiki page: Lucid.
5 Automaton
To see what the concept itself means, see the Wikipedia articles Finite state machine and also Automata theory.
How these concepts can be implemented using the concept of arrow, can be found in the introductory articles on arrows mentioned above.