Arrow
From HaskellWiki
EndreyMark (Talk  contribs) (→Parser: The symmetric figure in Wikibooks' Programming:Haskell_arrows article suggests abstracting away side effect order) 
(→Function: Fix small typo.) 

(31 intermediate revisions by 12 users not shown)  
Line 3:  Line 3:  
__TOC__ 
__TOC__ 

−  == Introduction == 
+  == Overview == 
−  [http://www.haskell.org/arrows/index.html Arrows: A General Interface to Computation] written by [http://www.soi.city.ac.uk/%7Eross/ Ross Peterson]. 
+  Arrows, or Freydcategories, are a generalization of Monads. 
−  HaWiki's [http://haskell.org/hawiki/UnderstandingArrows UnderstandingArrows]. 
+  "They can do everything monads can do, and more. They are roughly comparable to monads with a static component." However "Arrows do have some problems". ''(need a more useful comparison)'' 
−  [http://www.haskell.org/tmrwiki/ArrowsIntroduction ArrowsIntroduction] written by [http://www.scannedinavian.com/~shae/blog/index.html Shae Erisson] and published in [http://www.haskell.org/tmrwiki/IssueFour The Monad.Reader IssueFour]. 
+  For an introduction, see [[#External links]]. 
−  [http://en.wikibooks.org/wiki/Programming:Haskell_arrows Programming:Haskell arrows] (article of the [http://en.wikibooks.org/wiki/Main_Page English Wikibooks]) is not only a good introduction, but it shows also a funny metaphor for arrows, the factory/conveyor belt metaphor, we know this image for monads, but it is modified here for arrows, too. 
+  == Library == 
−  [http://www.cse.ogi.edu/~magnus/ProdArrows/ 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 [http://www.cse.ogi.edu/~magnus/ Magnus Carlsson]. 
+  * [http://www.haskell.org/ghc/docs/latest/html/libraries/base/ControlArrow.html Control.Arrow] is the standard library for arrows. 
+  * [http://www.haskell.org/arrows/download.html Arrow transformer library] (see the bottom of the page) is an extension with arrow transformers, subclasses, useful data types (Data.Stream, Data.Sequence). 

+  * [http://hackage.haskell.org/package/arrows arrows package] 

−  See also [[Research papers/Monads and arrows]]. 
+  == Examples == 
−  == Practice == 
+  Various concepts follow here, which can be seen as concrete examples covered by the arrow concept. Not all of them provide links to Haskellrelated materials: some of them are here only to give a selfcontained material (e.g. section [[#Automaton]] gives links only to the finite state concept itself.). 
−  Reasons, when it may be worth of solving a specific problem with arrows (instead of monads) can be read in 
+  === Practice === 
+  
+  Reasons, when it may be worth of solving a specific problem with arrows (instead of [[monad]]s) can be read in 

[http://caml.inria.fr/pub/mlarchives/camllist/2000/08/3c42f0fad3b3ecaca4f6043af65f6315.en.html a message from Daan Leijen]. 
[http://caml.inria.fr/pub/mlarchives/camllist/2000/08/3c42f0fad3b3ecaca4f6043af65f6315.en.html a message from Daan Leijen]. 

+  But Leijen's post is rather old (2000). Arrows are now significantly easier to understand and use than they were back then. Eg, his example might be rewritten 

+  test = proc _ > do 

+  question < ask < "what is the question ?" 

+  answer < ask < question 

+  returnA < ("the answer to '" ++ question ++ "' is " ++ answer) 

+  (or something vaguely like that). 

−  == Library == 
+  === Function === 
−  [http://www.haskell.org/ghc/docs/latest/html/libraries/base/ControlArrow.html Control.Arrow] is the standard library for arrows. 
+  Arrow operations <hask>arr</hask> and <hask>>>></hask> are rather straightforward. For implementing <hask>first</hask> and related concepts, see [[Prelude extensions#Tuples]]. 
−  
−  [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). 

−  
−  == Examples == 

−  
−  Various concepts follow here, which can be seen as concrete examples covered by the arrow concept. Not all of them provide links to Haskellrelated materials: some of them are here only to give a selfcontained material (e.g. section [[#Automaton]] gives links only to the finite state concept itself.). 

=== Parser === 
=== Parser === 

−  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.cse.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 Paterson]: 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): 

Line 45:  Line 51:  
exprTail = proc e > do 
exprTail = proc e > do 

symbol PLUS < () 
symbol PLUS < () 

−  t < term < () 
+  t < term < () 
exprTail < Plus e t 
exprTail < Plus e t 

<+> do 
<+> do 

symbol MINUS < () 
symbol MINUS < () 

−  t < term < () 
+  t < term < () 
exprTail < Minus e t 
exprTail < Minus e t 

<+> returnA < e 
<+> returnA < e 

</haskell> 
</haskell> 

−  An arrow parser library: [http://www.cs.helsinki.fi/u/ekarttun/PArrows/ PArrows] written by [http://www.haskell.org/tmrwiki/EinarKarttunen Einar Karttunen]. 
+  An arrow parser library: [http://hackage.haskell.org/package/PArrows PArrows] written by Einar Karttunen. 
Another arrow parser implementation: [http://anttijuhani.kaijanaho.fi/tmp/LLParser.hs LLParser.hs] written by [http://anttijuhani.kaijanaho.fi/newblog/ AnttiJuhani Kaijanaho] (I read the [http://www.scannedinavian.com/~shae/blog/20060314.html reference] to it in [http://www.scannedinavian.com/~shae/blog/index.html Shae Erisson's blog / journal]). 
Another arrow parser implementation: [http://anttijuhani.kaijanaho.fi/tmp/LLParser.hs LLParser.hs] written by [http://anttijuhani.kaijanaho.fi/newblog/ AnttiJuhani Kaijanaho] (I read the [http://www.scannedinavian.com/~shae/blog/20060314.html reference] to it in [http://www.scannedinavian.com/~shae/blog/index.html Shae Erisson's blog / journal]). 

Line 62:  Line 68:  
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) and [http://www.cse.ogi.edu/~magnus/ProdArrows/ ProdArrows  Arrows for Fudgets] 
+  [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) and [http://www.carlssonia.org/ogi/ProdArrows/ ProdArrows  Arrows for Fudgets] 
−  written by [http://www.cse.ogi.edu/~magnus/ Magnus Carlsson] (page 9) mentions that computation (e.g. state) is threaded through the operands of <hask>&&&</hask> operation. 
+  written by [http://www.carlssonia.org/ Magnus Carlsson] (page 9) mentions that computation (e.g. state) is threaded through the operands of <hask>&&&</hask> operation. 
I mean, even the mere definition of <hask>&&&</hask> operation 
I mean, even the mere definition of <hask>&&&</hask> operation 

<haskell> 
<haskell> 

p &&& q = arr dup >>> first p >>> second q 
p &&& q = arr dup >>> first p >>> second q 

</haskell> 
</haskell> 

−  shows that the order of the computation (the side effects) is important when using <hask>&&&</hask>, and 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>): 
+  shows that the order of the computation (the side effects) is important when using <hask>&&&</hask>, and this can be exemplified very well with parser arrows. See an example found in [http://hackage.haskell.org/package/PArrows PArrows] written by Einar Karttunen (see module <hask>Text.ParserCombinators.PArrow.Combinator</hask>): 
<haskell> 
<haskell> 

  Match zero or more occurrences of the given parser. 
  Match zero or more occurrences of the given parser. 

Line 93:  Line 99:  
:<math>(\rho</math> <hask></hask> <math>\sigma) \left(i:x\right) y \Leftrightarrow i\begin{cases}0:&x\rho y\\1:&x\sigma y\end{cases}</math> 
:<math>(\rho</math> <hask></hask> <math>\sigma) \left(i:x\right) y \Leftrightarrow i\begin{cases}0:&x\rho y\\1:&x\sigma y\end{cases}</math> 

−  The picture illustrating <hask>***</hask> in [http://en.wikibooks.org/wiki/Programming:Haskell_arrows#.2A.2A.2A Programming:Haskell_arrows] article of Wikibooks suggests exactly such a view: order of side effects can be unimportant at some arrow instances, and the symmetry of the figure reflects this. In generally, however, the figure should use a notation for threading through side effects in a sequence. 
+  The picture illustrating <hask>***</hask> in [http://en.wikibooks.org/wiki/Haskell/Understanding_arrows#.2A.2A.2A Haskell/Understanding arrows] article of Wikibooks suggests exactly such a view: order of side effects can be unimportant at some arrow instances, and the symmetry of the figure reflects this. In generally, however, the figure should use a notation for threading through side effects in a sequence. 
=== Stream processor === 
=== Stream processor === 

Line 99:  Line 105:  
The [http://homepages.cwi.nl/~tromp/cl/lazyk.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. 
The [http://homepages.cwi.nl/~tromp/cl/lazyk.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 
−  written by [http://www.cse.ogi.edu/~magnus/ Magnus Carlsson], 2001. 
+  * [http://www.carlssonia.org/ogi/ProdArrows/ ProdArrows  Arrows for Fudgets] written by [http://www.carlssonia.org/ Magnus Carlsson], 2001. 
+  * [http://www.haskell.org/arrows/biblio.html Generalising Monads to Arrows] written by [http://www.cse.chalmers.se/~rjmh/ John Hughes] (section 6, pages 2024) 

==== Functional I/O, graphical user interfaces ==== 
==== Functional I/O, graphical user interfaces ==== 

−  [http://citeseer.ist.psu.edu/hudak89expressiveness.html On the Expressiveness of Purely Functional I/O Systems] written by Paul Hudak and Raman S. Sundaresh. 
+  * [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.49.695 On the Expressiveness of Purely Functional I/O Systems] written by Paul Hudak and Raman S. Sundaresh. 
−  +  * [http://www.altocumulus.org/Fudgets/ Fudgets] written by [http://www.altocumulus.org/~hallgren/ Thomas Hallgren] and [http://www.carlssonia.org/ Magnus Carlsson]. See also [http://www.carlssonia.org/ogi/ProdArrows/ Arrows for Fudgets] written by [http://www.carlssonia.org/ Magnus Carlsson], mentioning how these two concepts relate to each other. 

−  [http://www.cs.chalmers.se/Cs/Research/Functional/Fudgets/ Fudgets] written by [http://www.cs.chalmers.se/~hallgren/ Thomas Hallgren] and [http://www.cs.chalmers.se/~magnus/ Magnus Carlsson]. See also [http://www.cse.ogi.edu/PacSoft/seminar/magnus_abstract.html Arrows for Fudgets] written by [http://www.cse.ogi.edu/~magnus/ Magnus Carlsson], mentioning how these two concepts relate to each other. 
+  * [http://kevin.atkinson.dhs.org/fg/doc/FG.html FG] 
+  * [[Phooey]] 

+  * [[Grapefruit]] 

==== Dataflow languages ==== 
==== Dataflow languages ==== 

Line 112:  Line 118:  
[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]]. 
[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 === 
To see what the concept itself means, see the Wikipedia articles [http://en.wikipedia.org/wiki/Finite_state_machine Finite state machine] and also [http://en.wikipedia.org/wiki/Automata_theory Automata theory]. 
To see what the concept itself means, see the Wikipedia articles [http://en.wikipedia.org/wiki/Finite_state_machine Finite state machine] and also [http://en.wikipedia.org/wiki/Automata_theory Automata theory]. 

Line 118:  Line 124:  
How these concepts can be implemented using the concept of arrow, can be found in the introductory articles on arrows mentioned above. 
How these concepts can be implemented using the concept of arrow, can be found in the introductory articles on arrows mentioned above. 

−  [[Category:Standard classes]] 
+  === Haskell XML Toolbox === 
+  [[HXT]] is an example of a real application using Arrows 

+  
+  == External links == 

+  * [http://www.cse.chalmers.se/~rjmh/afparrows.pdf ''Programming with Arrows'']  A tutorial introduction to arrows and arrow notation. Very didactic, introducing the arrow subclasses with detailed examples and rich explanations on the motivations of each decision. 

+  * [http://www.haskell.org/arrows/ Arrows: A General Interface to Computation] written by [http://www.soi.city.ac.uk/%7Eross/ Ross Paterson]. 

+  * [http://www.haskell.org/arrows/biblio.html ''Generalising Monads to Arrows'', and other papers] 

+  * [http://www.carlssonia.org/ogi/ProdArrows/ 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 [http://www.carlssonia.org/ Magnus Carlsson]. 

+  * [http://en.wikibooks.org/wiki/Haskell/Arrows Haskell/Arrows] on Wikibooks, followed by [http://en.wikibooks.org/wiki/Haskell/Understanding_arrows Understanding arrows], which uses a factory/conveyor belt metaphor for arrows. We know this image for [[monad]]s, but it is modified here for arrows, too. 

+  * HaWiki's [http://web.archive.org/web/20060901030914/http://haskell.org/hawiki/UnderstandingArrows UnderstandingArrows]. (An old page in the Web Archive (slow)) 

+  * [http://www.haskell.org/haskellwiki/Upgrading_packages/Updating_to_GHC_6.10#Arrow_instances Upgrading packages]; packages using Control.Arrow must be changed when switching to GHC 6.10 

+  
+  == See also == 

+  
+  * [[Causal Commutative Arrows]] 

+  * [[Research papers/Monads and arrows#Arrows]]. 

+  * [[Arrow tutorial]]. 

+  
+  [[Category:Arrow]] 
Latest revision as of 10:31, 30 November 2012
import Control.Arrow 
Contents 
[edit] 1 Overview
Arrows, or Freydcategories, are a generalization of Monads.
"They can do everything monads can do, and more. They are roughly comparable to monads with a static component." However "Arrows do have some problems". (need a more useful comparison)
For an introduction, see #External links.
[edit] 2 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).
 arrows package
[edit] 3 Examples
Various concepts follow here, which can be seen as concrete examples covered by the arrow concept. Not all of them provide links to Haskellrelated materials: some of them are here only to give a selfcontained material (e.g. section #Automaton gives links only to the finite state concept itself.).
[edit] 3.1 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. But Leijen's post is rather old (2000). Arrows are now significantly easier to understand and use than they were back then. Eg, his example might be rewritten
test = proc _ > do question < ask < "what is the question ?" answer < ask < question returnA < ("the answer to '" ++ question ++ "' is " ++ answer)
(or something vaguely like that).
[edit] 3.2 Function
Arrow operations[edit] 3.3 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 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.
Another arrow parser implementation: LLParser.hs written by AnttiJuhani Kaijanaho (I read the reference to it in Shae Erisson's blog / journal).
The funny thing which took a long time for me to understand arrow parsers is a sort of differential approach  in contrast to the wellknown parser approaches. (I mean, in some way wellknown 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) and ProdArrows  Arrows for Fudgets
written by Magnus Carlsson (page 9) mentions that computation (e.g. state) is threaded through the operands ofp &&& q = arr dup >>> first p >>> second q
  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))
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])
 (ρ &&&
 (ρ 
[edit] 3.4 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.
 Generalising Monads to Arrows written by John Hughes (section 6, pages 2024)
[edit] 3.4.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.
 FG
 Phooey
 Grapefruit
[edit] 3.4.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.
[edit] 3.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.
[edit] 3.6 Haskell XML Toolbox
HXT is an example of a real application using Arrows
[edit] 4 External links
 Programming with Arrows  A tutorial introduction to arrows and arrow notation. Very didactic, introducing the arrow subclasses with detailed examples and rich explanations on the motivations of each decision.
 Arrows: A General Interface to Computation written by Ross Paterson.
 Generalising Monads to Arrows, and other papers
 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.
 Haskell/Arrows on Wikibooks, followed by Understanding arrows, which uses a factory/conveyor belt metaphor for arrows. We know this image for monads, but it is modified here for arrows, too.
 HaWiki's UnderstandingArrows. (An old page in the Web Archive (slow))
 Upgrading packages; packages using Control.Arrow must be changed when switching to GHC 6.10