m (Pointed the "See also" Research_papers/Monads_and_arrows link directly to #Arrows.)
(updated the link to "ProdArrows -- Arrows for Fudgets")
Revision as of 23:02, 17 November 2008
Arrows, or Freyd-categories, 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.
- 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
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.).
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).
3.2 FunctionArow operations
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
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.Magnus Carlsson (page 9) mentions that computation (e.g. state) is threaded through the operands of
p &&& 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])
- (ρ &&&
- (ρ |||
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 20--24)
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.
3.4.2 Dataflow languages
How these concepts can be implemented using the concept of arrow, can be found in the introductory articles on arrows mentioned above.
- 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
- ArrowsIntroduction written by Shae Erisson and published in The Monad.Reader IssueFour.
- 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.broken link