Personal tools

Arrow

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
(Magnus Carlsson's name and homepage)
m (spell-check with ispell)
Line 22: Line 22:
 
== Library ==
 
== Library ==
   
[http://www.haskell.org/ghc/docs/latest/html/libraries/base/Control-Arrow.html Control.Arrow] is the standard ibrary for arrows.
+
[http://www.haskell.org/ghc/docs/latest/html/libraries/base/Control-Arrow.html Control.Arrow] is the standard library for arrows.
   
 
[http://www.haskell.org/arrows/download.html#bottom Arrow transformer library] (see the bottom of the page) is an extension with arrow transformers, subclasses, useful data types (Data.Stream, Data.Sequence).
 
[http://www.haskell.org/arrows/download.html#bottom Arrow transformer library] (see the bottom of the page) is an extension with arrow transformers, subclasses, useful data types (Data.Stream, Data.Sequence).
Line 28: Line 28:
 
== Examples ==
 
== 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.).
+
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-contained material (e.g. section [[#Automaton]] gives links only to the finite state concept itself.).
   
 
=== Parser ===
 
=== Parser ===
Line 64: Line 64:
 
The idea of borrowing this image from mathematical analysis comes from another topic: the version control systems article [http://sourcefrog.net/weblog/software/vc/derivatives.html Integrals and derivatives] written by Martin Pool uses a similar image.
 
The idea of borrowing this image from mathematical analysis comes from another topic: the version control systems article [http://sourcefrog.net/weblog/software/vc/derivatives.html Integrals and derivatives] written by Martin Pool uses a similar image.
   
[http://www.soi.city.ac.uk/~ross/papers/fop.html Arrows and Computation] written by [http://www.soi.city.ac.uk/%7Eross/ Ross Paterson] (pages 2, 6, 7) mentions that computation (e.g. state) is threaded through the operands of <hask>&&&</hask>. I think this can be examplified very well with parser arrows. See an example found in [http://www.cs.helsinki.fi/u/ekarttun/PArrows/ PArrows] written by [http://www.haskell.org/tmrwiki/EinarKarttunen Einar Karttunen] (see module <hask>Text.ParserCombinators.PArrow.Combinator</hask>):
+
[http://www.soi.city.ac.uk/~ross/papers/fop.html Arrows and Computation] written by [http://www.soi.city.ac.uk/%7Eross/ Ross Paterson] (pages 2, 6, 7) mentions that computation (e.g. state) is threaded through the operands of <hask>&&&</hask>. I think this can be exemplified very well with parser arrows. See an example found in [http://www.cs.helsinki.fi/u/ekarttun/PArrows/ PArrows] written by [http://www.haskell.org/tmrwiki/EinarKarttunen Einar Karttunen] (see module <hask>Text.ParserCombinators.PArrow.Combinator</hask>):
 
<haskell>
 
<haskell>
-- | Match zero or more occurences of the given parser.
+
-- | Match zero or more occurrences of the given parser.
 
many :: MD i o -> MD i [o]
 
many :: MD i o -> MD i [o]
 
many = MStar
 
many = MStar
   
-- | Match one or more occurences of the given parser.
+
-- | Match one or more occurrences of the given parser.
 
many1 :: MD i o -> MD i [o]
 
many1 :: MD i o -> MD i [o]
 
many1 x = (x &&& MStar x) >>> pure (\(b,bs) -> (b:bs))
 
many1 x = (x &&& MStar x) >>> pure (\(b,bs) -> (b:bs))
Line 81: Line 81:
 
A more complicated example (from the same module):
 
A more complicated example (from the same module):
 
<haskell>
 
<haskell>
-- | Match one or more occurences of the given parser separated by the sepator.
+
-- | Match one or more occurrences of the given parser separated by the separator.
 
sepBy1 :: MD i o -> MD i o' -> MD i [o]
 
sepBy1 :: MD i o -> MD i o' -> MD i [o]
 
sepBy1 p s = (many (p &&& s >>^ fst) &&& p) >>^ (\(bs,b) -> bs++[b])
 
sepBy1 p s = (many (p &&& s >>^ fst) &&& p) >>^ (\(bs,b) -> bs++[b])
Line 89: Line 89:
 
=== Stream processor ===
 
=== Stream processor ===
   
The [http://homepages.cwi.nl/~tromp/cl/lazy-k.html 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.
+
The [http://homepages.cwi.nl/~tromp/cl/lazy-k.html Lazy K programming language] is an interesting esoteric language (from the family of pure, lazy functional languages), whose I/O concept is approached by streams.
   
 
Arrows are useful also to grasp the concept of stream processors. See details in [http://www.cse.ogi.edu/~magnus/ProdArrows/ ProdArrows -- Arrows for Fudgets]
 
Arrows are useful also to grasp the concept of stream processors. See details in [http://www.cse.ogi.edu/~magnus/ProdArrows/ ProdArrows -- Arrows for Fudgets]
Line 102: Line 102:
 
==== Dataflow languages ====
 
==== Dataflow languages ====
   
[http://www.soi.city.ac.uk/~ross/papers/fop.html Arrows and Computation] written by [http://www.soi.city.ac.uk/%7Eross/ Ross Paterson] mentions how to mimick dataflow programming in (lazy) functional languages. See more on Lucid's own HaskellWiki page: [[Lucid]].
+
[http://www.soi.city.ac.uk/~ross/papers/fop.html Arrows and Computation] written by [http://www.soi.city.ac.uk/%7Eross/ Ross Paterson] mentions how to mimic dataflow programming in (lazy) functional languages. See more on Lucid's own HaskellWiki page: [[Lucid]].
   
 
== Automaton ==
 
== Automaton ==

Revision as of 20:29, 13 June 2006

Arrow class (base)
import Control.Arrow

Contents


1 Introduction

Arrows: A General Interface to Computation written by Ross Peterson.

HaWiki's UnderstandingArrows.

Monad.Reader's ArrowsIntroduction article.

ProdArrows -- Arrows for Fudgets is also a good general material on the arrow concept (and also good for seeing, how arrows can be used to implement stream processors and Fudgets). It is written by Magnus Carlsson.

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 library 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-contained 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):

\mathrm{expr} ::= \mathrm{term}\;\mathrm{exprTail}
\mathrm{exprTail} ::= \mathbf{PLUS}\;\mathrm{term}\;\mathrm{exprTail}\;\vert\;\mathbf{MINUS}\;\mathrm{term}\;\mathrm{exprTail}\;\vert\;\epsilon

is represented with arrow parsers this way:

 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 arrow parser library: 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
&&&
. I think this can be exemplified very well with parser arrows. See an example found in PArrows written by Einar Karttunen (see module
Text.ParserCombinators.PArrow.Combinator
):
 -- | Match zero or more occurrences of the given parser.
 many :: MD i o -> MD i [o]
 many = MStar
 
 -- | Match one or more occurrences of the given parser.
 many1 :: MD i o -> MD i [o]
 many1 x = (x &&& MStar x) >>> pure (\(b,bs) -> (b:bs))
The definition of
between
parser combinator can show another example for the non-commutativeness of
&&&
operation:
 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 occurrences of the given parser separated by the separator.
 sepBy1 :: MD i o -> MD i o' -> MD i [o]
 sepBy1 p s = (many (p &&& s >>^ fst) &&& p) >>^ (\(bs,b) -> bs++[b])
This makes clear that the order of the operands of
&&&
operation can be important. Of course, in some cases (e.g. nondeterministic functions arrows, or more generally, at the various implementations of binary relation arrows) the order of the operands of fan-in and fan-out is not important.

4.2 Stream processor

The Lazy K programming language is an interesting esoteric language (from the family of pure, lazy functional languages), whose I/O concept is approached by streams.

Arrows are useful also to grasp the concept of stream processors. See details in ProdArrows -- Arrows for Fudgets written by Magnus Carlsson, 2001.

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 mimic 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.