https://wiki.haskell.org/api.php?action=feedcontributions&user=MitchellNCharity&feedformat=atomHaskellWiki - User contributions [en]2024-03-29T00:00:43ZUser contributionsMediaWiki 1.35.5https://wiki.haskell.org/index.php?title=Boston_Area_Haskell_Users%27_Group&diff=29590Boston Area Haskell Users' Group2009-08-17T17:26:09Z<p>MitchellNCharity: Next Meeting: updated to Aug 18. +emphase checking list.</p>
<hr />
<div>[[Category:Community]]<br />
== Purpose and Goals ==<br />
<br />
The purpose of the Boston Area Haskell Users' Group is to provide a regular forum in which area people interested in Haskell can get together, meet each other, share skills, and grow the community<br />
<br />
Join the [http://groups.google.com/group/bostonhaskell mailing list] for even more entertainment!<br />
<br />
== Next Meeting ==<br />
<br />
See '''http://groups.google.com/group/bostonhaskell''' for meeting announcements. They sometimes occur only a few days before the meeting, and this haskellwiki page is not always updated.<br />
<br />
The<br />
[http://groups.google.com/group/bostonhaskell/browse_thread/thread/71243e7d2ec57300 next meeting]<br />
of the Boston Area Haskell User's Group was once<br />
6:30pm - 8:30pm<br />
on August 18<br />
at MIT.<br />
<br />
''We're making a slight departure from our meeting format this month. Our featured speaker will be Edward Kmett, who will be sharing a two-part presentation focusing on monoids and parsing.''<br />
<br />
The two talks will be:<br />
<br />
* "Introduction to Monoids" by Edward Kmett<br />
* "A Parallel Parsing Trifecta: Iteratees, Parsec, and Monoids" by Edward Kmett<br />
<br />
== Meeting Format ==<br />
<br />
The Haskell Users' Group is '''not a forum for academic talks'''. The Boston area already provides plenty of opportunities for academics to give talks. The Haskell Users' Group is a forum for '''informal interactions''' and a place where you can '''show us the code'''.<br />
<br />
The ideal meeting will include two presentations and a break:<br />
* A presentation of '''code that even a beginner will appreciate'''<br />
* A break (which may also include Lightning Talks or other advertisements of interest)<br />
* A presentation of '''code that will make at least some experts say Ooh! and Aah!'''<br />
Demos are also encouraged, but we want to see at least a little bit of code, please.<br />
<br />
== Planned schedule ==<br />
<br />
Based on feedback fron the June 2009 meeting, we've switched to a monthly schedule. The previous calendar (below) is being kept as a reference for external events that can impact scheduling.<br />
<br />
The calendar is designed so that most meetings are scheduled at a time when people might have something new to show off.<br />
* A meeting in late January following POPL<br />
* A meeting at the end of March or the beginning of April, just after the ICFP deadline<br />
* A meeting in May after classes are out but before students and professors have dispersed for the summer<br />
* A meeting in July after the POPL deadline and perhaps just after the [http://icfpcontest.org ICFP programming contest]<br />
* A meeting in September following [http://www.icfpconference.org ICFP] and the Haskell Symposium<br />
* A meeting in November with a special emphasis on companies who may wish to recruit interns or new employees<br />
<br />
== Call for volunteers ==<br />
We need volunteers<br />
* To host one of the regular meetings<br />
* To present<br />
* To twist other people's arms to present<br />
* To provide refreshments at meetings<br />
* To talk to John Hughes and learn how to organize a "jobs fair" for the November meeting<br />
If you want to volunteer, please '''visit [[Boston Area Haskell Users' Group/Volunteers|the volunteers' page]]'''<br />
<br />
At some point we may be lucky enough to have a surplus of potential presenters. In that case we may need volunteers for a selection committee. A reasonable structure might be to have a committee of three who serve staggered six-month terms. If we can't find enough presenters, those same people could try to find some. In both cases people would be volunteering to help manage the program for three meetings.</div>MitchellNCharityhttps://wiki.haskell.org/index.php?title=Arrow&diff=22761Arrow2008-09-04T02:22:20Z<p>MitchellNCharity: Pointed the "See also" Research_papers/Monads_and_arrows link directly to #Arrows.</p>
<hr />
<div>{{Standard class|Arrow|module=Control.Arrow|module-doc=Control-Arrow|package=base}}<br />
<br />
__TOC__<br />
<br />
== Overview ==<br />
<br />
Arrows, or Freyd-categories, are a generalization of Monads.<br />
<br />
"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)''<br />
<br />
For an introduction, see [[#External links]].<br />
<br />
== Library ==<br />
<br />
* [http://www.haskell.org/ghc/docs/latest/html/libraries/base/Control-Arrow.html Control.Arrow] is the standard library for arrows.<br />
* [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).<br />
* [http://darcs.haskell.org/packages/arrows/ arrows package]<br />
<br />
== Examples ==<br />
<br />
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.).<br />
<br />
=== Practice ===<br />
<br />
Reasons, when it may be worth of solving a specific problem with arrows (instead of [[monad]]s) can be read in<br />
[http://caml.inria.fr/pub/ml-archives/caml-list/2000/08/3c42f0fad3b3ecaca4f6043af65f6315.en.html a message from Daan Leijen].<br />
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<br />
test = proc -> do<br />
question <- ask -< "what is the question ?"<br />
answer <- ask -< question<br />
returnA -< ("the answer to '" ++ question ++ "' is " ++ answer)<br />
(or something vaguely like that).<br />
<br />
=== Function ===<br />
<br />
Arow operations <hask>arr</hask> and <hask>>>></hask> are rather straightforward. For implementing <hask>first</hask> and related concepts, see [[Prelude extensions#Tuples]].<br />
<br />
=== Parser ===<br />
<br />
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].<br />
<br />
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):<br />
:<math>\mathrm{expr} ::= \mathrm{term}\;\mathrm{exprTail}</math><br />
:<math>\mathrm{exprTail} ::= \mathbf{PLUS}\;\mathrm{term}\;\mathrm{exprTail}\;\vert\;\mathbf{MINUS}\;\mathrm{term}\;\mathrm{exprTail}\;\vert\;\epsilon</math><br />
is represented with arrow parsers this way:<br />
<haskell><br />
data Expr = Plus Expr Expr | Minus Expr Expr | ...<br />
<br />
expr :: ParseArrow () Expr<br />
expr = proc () -> do<br />
t <- term -< ()<br />
exprTail -< t<br />
<br />
exprTail :: ParseArrow Expr Expr<br />
exprTail = proc e -> do<br />
symbol PLUS -< ()<br />
t <- term -< ()<br />
exprTail -< Plus e t<br />
<+> do<br />
symbol MINUS -< ()<br />
t <- term -< ()<br />
exprTail -< Minus e t<br />
<+> returnA -< e<br />
</haskell><br />
<br />
An arrow parser library: [http://www.cs.helsinki.fi/u/ekarttun/PArrows/ PArrows] written by [http://www.haskell.org/tmrwiki/EinarKarttunen Einar Karttunen].<br />
<br />
Another arrow parser implementation: [http://antti-juhani.kaijanaho.fi/tmp/LLParser.hs LLParser.hs] written by [http://antti-juhani.kaijanaho.fi/newblog/ Antti-Juhani Kaijanaho] (I read the [http://www.scannedinavian.com/~shae/blog/2006-03-14.html reference] to it in [http://www.scannedinavian.com/~shae/blog/index.html Shae Erisson's blog / journal]).<br />
<br />
The funny thing which took a long time for me to understand arrow parsers is a sort of differential approach -- in contrast to the [http://www.willamette.edu/~fruehr/haskell/seuss.html 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.)<br />
<br />
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.<br />
<br />
[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]<br />
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.<br />
I mean, even the mere definition of <hask>&&&</hask> operation<br />
<haskell><br />
p &&& q = arr dup >>> first p >>> second q<br />
</haskell><br />
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>):<br />
<haskell><br />
-- | Match zero or more occurrences of the given parser.<br />
many :: MD i o -> MD i [o]<br />
many = MStar<br />
<br />
-- | Match one or more occurrences of the given parser.<br />
many1 :: MD i o -> MD i [o]<br />
many1 x = (x &&& MStar x) >>> pure (\(b,bs) -> (b:bs))<br />
</haskell><br />
The definition of <hask>between</hask> parser combinator can show another example for the importance of the order in which the computation (e.g. the side effects) take place using <hask>&&&</hask> operation:<br />
<haskell><br />
between :: MD i t -> MD t close -> MD t o -> MD i o<br />
between open close real = open >>> (real &&& close) >>^ fst<br />
</haskell><br />
A more complicated example (from the same module):<br />
<haskell><br />
-- | Match one or more occurrences of the given parser separated by the separator.<br />
sepBy1 :: MD i o -> MD i o' -> MD i [o]<br />
sepBy1 p s = (many (p &&& s >>^ fst) &&& p) >>^ (\(bs,b) -> bs++[b])<br />
</haskell><br />
This makes clear that the order of effects of the operands of <hask>&&&</hask> operation can be important. But let us mention also a counterexample, e.g. nondeterministic functions arrows, or more generally, the various implementations of binary relation arrows -- there is no such sequencing of effect orders. Now let us see this fact on the mere mathematical concept of binary relations (not minding how it implemented):<br />
:<math>(\rho</math> <hask>&&&</hask> <math>\sigma) x \left\langle y_0, y_1\right\rangle \Leftrightarrow x \rho y_0 \land x \sigma y_1</math><br />
:<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><br />
<br />
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.<br />
<br />
=== Stream processor ===<br />
<br />
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.<br />
<br />
Arrows are useful also to grasp the concept of stream processors. See details in<br />
* [http://www.cse.ogi.edu/~magnus/ProdArrows/ ProdArrows -- Arrows for Fudgets] written by [http://www.cse.ogi.edu/~magnus/ Magnus Carlsson], 2001.<br />
* [http://www.haskell.org/arrows/biblio.html Generalising Monads to Arrows] written by [http://www.cs.chalmers.se/~rjmh/ John Hughes] (section 6, pages 20--24)<br />
<br />
==== Functional I/O, graphical user interfaces ====<br />
<br />
* [http://citeseer.ist.psu.edu/hudak89expressiveness.html On the Expressiveness of Purely Functional I/O Systems] written by Paul Hudak and Raman S. Sundaresh.<br />
* [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.<br />
* [http://kevin.atkinson.dhs.org/fg/doc/FG.html FG]<br />
* [[Phooey]]<br />
* [[Grapefruit]]<br />
<br />
==== Dataflow languages ====<br />
<br />
[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]].<br />
<br />
=== Automaton ===<br />
<br />
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].<br />
<br />
How these concepts can be implemented using the concept of arrow, can be found in the introductory articles on arrows mentioned above.<br />
<br />
== External links ==<br />
* [http://www.cs.chalmers.se/~rjmh/afp-arrows.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.<br />
* [http://www.haskell.org/arrows/index.html Arrows: A General Interface to Computation] written by [http://www.soi.city.ac.uk/%7Eross/ Ross Paterson].<br />
* [http://www.haskell.org/arrows/biblio.html ''Generalising Monads to Arrows'', and other papers]<br />
* [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].<br />
* [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].<br />
* [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.<br />
* HaWiki's [http://haskell.org/hawiki/UnderstandingArrows UnderstandingArrows].''broken link''<br />
<br />
== See also ==<br />
<br />
* [[Research papers/Monads and arrows#Arrows]].<br />
* [[Arrow tutorial]].<br />
<br />
[[Category:Arrow]]</div>MitchellNCharityhttps://wiki.haskell.org/index.php?title=Functional_Reactive_Programming&diff=21198Functional Reactive Programming2008-06-07T02:43:30Z<p>MitchellNCharity: Added a copy of haskell.org/frp/, 2003 :(, so a Wikipedia link could be repointed.</p>
<hr />
<div>Functional Reactive Programming integrates time flow and compositional events into functional programming. This provides an elegant way to express computation in domains such as interactive animations, robotics, computer vision, user interfaces, and simulation.<br />
<br />
The following libraries are implementations of FRP:<br />
* [[Grapefruit]]<br />
* [[Reactive]]<br />
* [[DataDriven]]<br />
* [[Yampa]]<br />
<br />
== From [http://www.haskell.org/frp/ www.haskell.org/frp/], last updated 2003 ==<br />
This is a copy of the obsolete /frp/, added so a link from http://en.wikipedia.org/wiki/Functional_reactive_programming could be losslessly repointed from there to here.<br />
<br />
*[http://www.haskell.org/yale/publications.html The Yale Haskell group's latest publications] - Most are related to FRP<br />
*[http://conal.net/fran Fran] - Functional Animation<br />
<br />
People:<br />
<br />
*[http://www.apocalypse.org/pub/u/antony/home.htm Antony Courtney]<br />
*[http://conal.net Conal Elliott]<br />
*[http://pantheon.yale.edu/~lh234/ Liwen Huang]''broken link''<br />
*[http://www.cs.yale.edu/homes/hudak-paul.html Paul Hudak]''broken link''<br />
*[http://www.cs.yale.edu/~nilsson Henrik Nilsson]<br />
*[http://mcis.western.edu/~jpeterson/ John Peterson]</div>MitchellNCharityhttps://wiki.haskell.org/index.php?title=Research_papers/Monads_and_arrows&diff=21197Research papers/Monads and arrows2008-06-07T02:11:07Z<p>MitchellNCharity: +link to "Directing JavaScript with Arrows"/Foster</p>
<hr />
<div>__TOC__<br />
<br />
==Monads==<br />
[[Category:Monad]] [[Category:Arrow]] [[Category:Research]]<br />
See also [[Monad]] and [[Arrow]] HaskellWiki pages.<br />
<br />
;[http://research.microsoft.com/~simonpj/Papers/state-lasc.ps.gz State in Haskell]<br />
:SL Peyton Jones and J Launchbury, Lisp and Symbolic Computation 8(4), Dec 1995, pp293-341. (Cited by 109)<br />
<br />
;[http://research.microsoft.com/~simonpj/Papers/lazy-functional-state-threads.ps.Z Lazy functional state threads] <br />
:SL Peyton Jones and J Launchbury, SIGPLAN Symposium on Programming Language Design and Implementation (PLDI'94), Orlando, June 1994, pp24-35. (Cited by 127))<br />
<br />
;[http://research.microsoft.com/~simonpj/Papers/imperative.ps.Z Imperative functional programming]<br />
:SL Peyton Jones and PL Wadler, 20th ACM Symposium on Principles of Programming Languages (POPL'93), Charleston, Jan 1993, pp71-84. (Cited by 289)<br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/publications/FLOPS98.ps.gz Prological features in a functional setting - axioms and implementations] <br />
:Ralf Hinze. In Masahiko Sato, Yoshihito Toyama, editors, Third Fuji International Symposium on Functional and Logic Programming (FLOPS'98), Kyoto University, Japan, April 1998, pp. 98-122. World Scientific, Singapore, New Jersey, London, Hong Kong. (Cited by 9)<br />
<br />
;[http://www.cse.ogi.edu/~mpj/pubs/composing.html Composing Monads]<br />
:Mark P. Jones and Luc Duponcheel Research Report YALEU/DCS/RR-1004, Yale University, New Haven, Connecticut, USA, December 1993. (Cited by 66))<br />
<br />
;[http://homepages.inf.ed.ac.uk/wadler/papers/effectstocl/effectstocl.ps.gz The marriage of effects and monads]<br />
:Philip Wadler and Peter Thiemann. Submitted to ACM Transactions on Computational Logic. (Cited by 62)<br />
<br />
;[http://homepages.inf.ed.ac.uk/wadler/papers/monadsdeclare/monadsdeclare.ps.gz How to declare an imperative] <br />
:Philip Wadler. ACM Computing Surveys, 29(3):240--263, September 1997. A shorter version was an invited paper at ILPS 95, appearing in John Lloyd, editor, International Logic Programming Symposium, MIT Press, December 1995. (Cited by 92)<br />
<br />
;[http://homepages.inf.ed.ac.uk/wadler/papers/composable/composable.ps.gz Monads and composable continuations]<br />
:Philip Wadler. Lisp and Symbolic Computation, Special issue on continuations, 7(1):39-56, January 1994. (Cited by 34)<br />
<br />
;[http://homepages.inf.ed.ac.uk/wadler/papers/marktoberdorf/marktoberdorf.ps.gz Monads for functional programming]<br />
:Philip Wadler. In M. Broy, editor, Marktoberdorf Summer School on Program Design Calculi, Springer Verlag, NATO ASI Series F: Computer and systems sciences, Volume 118, August 1992. Also in J. Jeuring and E. Meijer, editors, Advanced Functional Programming, Springer Verlag, LNCS 925, 1995. (Cited by 237)<br />
<br />
;[http://homepages.inf.ed.ac.uk/wadler/papers/monadscomb/monadscomb.ps.gz Combining monads]<br />
:David King and Philip Wadler. Glasgow Workshop on Functional Programming, Springer Verlag Workshops in Computing Series, Ayr, July 1992. (Cited by 42)<br />
<br />
;[http://homepages.inf.ed.ac.uk/wadler/papers/essence/essence.ps.gz The essence of functional programming] <br />
:Philip Wadler. Invited talk, 19'th Symposium on Principles of Programming Languages, ACM Press, Albuquerque, January 1992. (Cited by 407)<br />
<br />
;[http://okmij.org/ftp/Computation/proving-monad-laws.txt How to prove monad laws]<br />
:Oleg Kiselyov, v1.1, Sep 2, 2003, Originally posted as "Re: proving the monad laws" on the Haskell mailing list<br />
<br />
;[http://web.engr.oregonstate.edu/~erwig/papers/abstracts.html#SCP04 Monadification of Functional Programs]<br />
:Martin Erwig and Deling Ren. Science of Computer Programming, Vol. 52, No. 1-3, 101-129, 2004<br />
<br />
;[http://web.engr.oregonstate.edu/~erwig/papers/abstracts.html#IFL98 The Categorical Imperative - Or: How to Hide Your State Monads]<br />
:Martin Erwig. 10th Int. Workshop on Implementation of Functional Languages (IFL'98), 1-25, 1998<br />
<br />
;[http://www.cse.ogi.edu/~magnus/papers/icfp-2002.pdf Monads for Incremental Computing]<br />
:Magnus Carlsson, ICFP 2002, 2002. <br />
<br />
;[http://www.cse.ogi.edu/~magnus/Adaptive/ Monads for Incremental Computing]<br />
:Magnus Carlsson, ICFP'02.<br />
<br />
===Monad comprehensions===<br />
<br />
;[http://homepages.inf.ed.ac.uk/wadler/papers/monads/monads.ps.gz Comprehending monads]<br />
:Philip Wadler. Mathematical Structures in Computer Science, Special issue of selected papers from 6'th Conference on Lisp and Functional Programming, 2:461-493, 1992. (Cited by 469)<br />
<br />
===Monad transformers===<br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/publications/ICFP00.ps.gz Deriving Backtracking Monad Transformers]<br />
:Ralf Hinze. In Phil Wadler, editor, Proceedings of the 2000 International Conference on Functional Programming, Montreal, Canada, September 18-20, 2000.<br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/publications/IAI-TR-99-1.ps.gz Deriving monad transformers] <br />
:Ralf Hinze. Technical Report IAI-TR-99-1, Institut fr Informatik III, Universitt Bonn, January 1999.<br />
<br />
;[http://okmij.org/ftp/papers/LogicT.pdf Backtracking, Interleaving, and Terminating Monad Transformers]<br />
:Oleg Kiselyov, Chung-chieh Shan, Daniel P. Friedman and Amr Sabry, Functional Pearl, to be presented at ICFP 2005.<br />
<br />
;[http://citeseer.ist.psu.edu/harrison98modular.html Modular Compilers Based on Monad Transformers]<br />
:Harrison, Kamin (1998) <br />
<br />
;[http://citeseer.ist.psu.edu/188147.html Semantic Lego]<br />
:Espinosa (1995) <br />
<br />
===Recursion===<br />
<br />
;[http://haskell.readscheme.org/servlets/cite.ss?pattern=erkok-launchbury-moran-tia-02 Semantics of Value Recursion for Monadic Input/Output]<br />
:Levent Erkök, John Launchbury and Andrew Moran. Journal of Theoretical Informatics and Applications. 36. 2. 2002.<br />
<br />
;[http://www.cse.ogi.edu/PacSoft/projects/rmb/mdo.pdf A Recursive do for Haskell]<br />
:Levent Erkök and John Launchbury. Proceedings of the 2002 ACM SIGPLAN workshop on Haskell. Pittsburgh, Pennsylvania. 29 - 37 2002 ISBN 1-58113-605-6<br />
<br />
;[http://www.cse.ogi.edu/~erkok/rmb/erkok-thesis.ps.gz Value recursion in monadic computations]<br />
:Levent Erkök. PhD. Thesis. OGI School of Science and Engineering. October 2002.<br />
<br />
;[http://www.cse.ogi.edu/PacSoft/projects/rmb/fics.ps.gz Semantics of fixIO]<br />
:Levent Erkök, John Launchbury and Andrew Moran. Workshop on Fixed Points in Computer Science (FICS'01). 2001. <br />
<br />
;[http://www.cse.ogi.edu/PacSoft/projects/rmb/mfix.ps.gz Recursive Monadic Bindings]<br />
:Levent Erkok and John Launchbury. Proceedings of the International Conference on Functional Programming ICFP'00. 2000.<br />
<br />
===Applications of monads===<br />
<br />
;[http://www.cs.chalmers.se/~rjmh/Globals.ps Global Variables in Haskell]<br />
:John Hughes. 2004. JFP.<br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/publications/IAI-TR-96-9.ps.gz Monadic-style backtracking]<br />
:Ralf Hinze. Technical Report IAI-TR-96-9, Institut fr Informatik III, Universitt Bonn, October 1996.<br />
<br />
;[http://www.math.chalmers.se/~koen/pubs/entry-jfp99-monad.html A Poor Man's Concurrency Monad]<br />
:Koen Claessen, Journal of Functional Programming. 9(3). 313--323. 1999.<br />
<br />
;[http://www.swiss.ai.mit.edu/~dae/related-papers/steele.ps.Z Building Interpreters by Composing Monads]<br />
:Guy L. Steele, Jr.. Principles of Programming Languages (POPL'94). January 1994. (Cited by 67)<br />
<br />
;[http://www.cse.ogi.edu/~mpj/pubs/modinterp.html Monad Transformers and Modular Interpreters]<br />
:Sheng Liang, Paul Hudak, and Mark P. Jones, In Conference Record of POPL'95: 22nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, San Francisco, CA, January 1995 (110 citations)<br />
<br />
;[http://www.cs.cornell.edu/people/fluet/research/rgn-monad/index.html Monadic Regions]<br />
:Fluet and Morrisett; To appear in the Journal of Functional Programming. "Region-based type systems provide programmer control over memory management without sacrificing type-safety... we show that plain old parametric polymorphism, as found in Haskell, is all that is needed."<br />
<br />
;[http://research.microsoft.com/~emeijer/Papers/XLinq%20XML%20Programming%20Refactored%20(The%20Return%20Of%20The%20Monoids).htm XLinq: XML Programming Refactored (The Return Of The Monoids)]<br />
:Erik Meijer and Brian Beckman<br />
<br />
;[http://okmij.org/ftp/Computation/monadic-shell.html Monadic Shell]<br />
:Oleg Kiselyov<br />
<br />
;[http://citeseer.ist.psu.edu/ghani02coalgebraic.html Coalgebraic Monads]<br />
:Ghani, Lth, De Marchi (2002) <br />
<br />
;[http://citeseer.ist.psu.edu/uustalu03monad.html Monad Translating Inductive and Coinductive Types]<br />
:Uustalu (2003)<br />
<br />
;[http://citeseer.ist.psu.edu/meijer95merging.html Merging Monads and Folds for Functional Programming]<br />
:Meijer, Jeuring (1995) <br />
<br />
;[http://citeseer.ist.psu.edu/fokkinga94monadic.html Monadic Maps and Folds for Arbitrary Datatypes]<br />
:Fokkinga (1994) <br />
<br />
;[http://citeseer.ist.psu.edu/126221.html Modular Denotational Semantics for Compiler Construction]<br />
:Sheng Liang (1996) <br />
<br />
;[http://citeseer.ist.psu.edu/50754.html Monadic Parser Combinators]<br />
:Hutton, Meijer (1996) <br />
<br />
;[http://citeseer.ist.psu.edu/hudak96building.html Building Domain-Specific Embedded Languages]<br />
:Paul Hudak (1996)<br />
<br />
;[http://citeseer.ist.psu.edu/finne94programming.html Programming Reactive Systems in Haskell]<br />
;Finne, Jones (1994) <br />
<br />
;[http://citeseer.ist.psu.edu/jay98costing.html Costing Parallel Programs as a Function of Shapes]<br />
;Jay (1998)<br />
<br />
;[http://citeseer.ist.psu.edu/demeuter97monads.html Monads as a theoretical foundation for AOP]<br />
:De Meuter (1997) <br />
<br />
;[http://arxiv.org/pdf/cs.CL/0205026 Monads for natural language semantics]<br />
:Chung-chieh Shan (Harvard University). Journal-ref: Proceedings of the 2001 European Summer School in Logic, Language and Information student session, ed. Kristina Striegnitz, 285-298<br />
<br />
;[http://arxiv.org/abs/cs.NA/0605058 A Monadic, Functional Implementation of Real Numbers]<br />
:Russell O'Connor, 2006. Mathematical Structures in Computer Science.<br />
<br />
;[http://research.microsoft.com/%7Esimonpj/papers/control/ A monadic framework for delimited continuations]<br />
:Kent Dybvig, Simon Peyton Jones, and Amr Sabry.<br />
<br />
See also [[Monad#Monads_in_other_languages|monads in other languages]].<br />
<br />
===Comonads===<br />
<br />
;[http://citeseer.ist.psu.edu/kieburtz99codata.html Codata and Comonads in Haskell]<br />
:Kieburtz - 1999<br />
<br />
;[http://citeseer.ist.psu.edu/510658.html The Dual of Substitution is Redecoration]<br />
:Tarmo Uustalu, Varmo Vene. Trends in Functional Programming 3. (2002)<br />
<br />
;[http://citeseer.ist.psu.edu/context/1959424/0 Monads and Comonads]<br />
:Ghani et al.<br />
<br />
;[http://citeseer.ist.psu.edu/uustalu01recursion.html Recursion Schemes from Comonads]<br />
:Uustalu, Vene, Pardo (2001)<br />
<br />
;[http://citeseer.ist.psu.edu/brookes91computational.html Computational Comonads and Intensional Semantics]<br />
:Brookes, Geva, 1992<br />
<br />
;[http://sigfpe.blogspot.com/2006/06/monads-kleisli-arrows-comonads-and.html Tutorial: Monads, Kleisli Arrows, Comonads and other Rambling Thoughts]<br />
<br />
===Monad theory===<br />
<br />
;[http://www.disi.unige.it/person/MoggiE/ftp/ic91.ps.gz Notions of computation and monads]<br />
:Eugenio Moggi. Information and Computation, 93(1):55-92, July 1991 ( Cited by 649)<br />
<br />
;[http://www.disi.unige.it/person/MoggiE/ftp/lc88.ps.gz Computational lambda-calculus and monads]<br />
:Eugenio Moggi. Logic in Computer Science, 1989. LICS '89, Proceedings., Fourth Annual Symposium on (1989), pp. 14-23. <br />
<br />
;[http://citeseer.ist.psu.edu/filinski99representing.html Representing Layered Monads]<br />
:Andrzej Filinski. In Proceedings of the 26th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 175--188, San Antonio, Texas, USA, January 1999. ACM Press.<br />
<br />
;[http://www.disi.unige.it/person/MoggiE/APPSEM00/BHM-revised.ps.gz Monads and Effects]<br />
:Eugenio Moggi. APPSEM'00 Summer School, LNCS 2395, 2002<br />
<br />
;[http://citeseer.ist.psu.edu/ariola98correctness.html Correctness of Monadic State: An Imperative Call-by-Need Calculus]<br />
:Ariola, Sabry (1998) <br />
<br />
;[http://citeseer.ist.psu.edu/147178.html Promotional Transformation of Monadic Programs]<br />
:Hu, Iwasaki (1995)<br />
<br />
;[http://www.disi.unige.it/person/MoggiE/ftp/jfp01.ps.gz Monadic Encapsulation of Effects: A Revised Approach (extended version)]<br />
:Journal of Functional Programming, 11(6), 2001.<br />
<br />
;[http://citeseer.ist.psu.edu/150326.html Towards a Mathematical Operational Semantics] <br />
:Turi, Plotkin (1997) (53 citations)<br />
<br />
;[http://citeseer.ist.psu.edu/mason91equivalence.html Equivalence in Functional Languages with Effects]<br />
:Mason, Talcott (1991) (49 citations) <br />
<br />
;[http://citeseer.ist.psu.edu/124606.html Computational Types from a Logical Perspective]<br />
:Benton, Bierman (1995)<br />
<br />
;[http://citeseer.ist.psu.edu/wansbrough97modular.html A Modular Monadic Action Semantics]<br />
:Wansbrough (1997) <br />
<br />
;[http://citeseer.ist.psu.edu/moggi98functor.html Functor Categories and Two-Level Languages]<br />
:Moggi (1998) <br />
<br />
;[http://citeseer.ist.psu.edu/moggi94categorytheoretic.html A Category-Theoretic Account of Program Modules]<br />
:Moggi (1994)<br />
<br />
==Arrows==<br />
<br />
See also [[Arrow]] HaskellWiki page.<br />
<br />
===Arrows in Haskell===<br />
<br />
;[http://www.cs.chalmers.se/~rjmh/Papers/arrows.ps Generalising Monads to Arrows],<br />
:John Hughes, in Science of Computer Programming 37, pp67-111, May 2000. (draft online)<br />
<br />
;[http://www.soi.city.ac.uk/~ross/papers/notation.html A New Notation for Arrows]<br />
:Ross Paterson. In ICFP 2001, Firenze, Italy, pp229-240]<br />
<br />
;[http://www.soi.city.ac.uk/~ross/papers/fop.html Arrows and Computation]<br />
:Ross Paterson, in The Fun of Programming (Jeremy Gibbons and Oege de Moor, Eds.), pp201-222, Palgrave, 2003.<br />
<br />
===Applications of arrows===<br />
<br />
;[http://apocalypse.org/~antony/work/pubs/genuinely-functional-guis.pdf Genuinely Functional User Interfaces]<br />
:Anthony Courtney and Conal Elliott, in Haskell Workshop 2001, Firenze, Italy, pp41-69.<br />
<br />
;[http://cs-www.cs.yale.edu/homes/nilsson/Publications/afp2002.pdf Arrows, Robots, and Functional Reactive Programming]<br />
:Paul Hudak, Henrik Nilsson, Anthony Courtney and Jon Peterson, in Advanced Functional Programming, 4th International School, (Johan Jeuring and Simon Peyton Jones eds.), Oxford, Springer LNCS 2638, 2003.<br />
<br />
;[http://www.cs.chalmers.se/~patrikj/poly/dc/ Polytypic compact printing and parsing]<br />
:Patrik Jansson and Johan Jeuring, In Proceedings European Symposium on Programming, LNCS 1576, pp273-287, Springer, 1999.<br />
<br />
;[http://www.md.chalmers.se/~patrikj/poly/dataconv/ Polytypic data conversion programs]<br />
:Patrik Jansson and Johan Jeuring, Science of Computer Programming 43(1), pp35-75, 2002.<br />
<br />
;[http://www.cse.ogi.edu/~krstic/psfiles/hyperfunctions.pdf Hyperfunctions]<br />
:Sava Krstic, John Launchbury and Dusko Pavlovic, Workshop on Fixed Points in Computer Science, Sep 2001.<br />
<br />
;[http://cs-www.cs.yale.edu/homes/nilsson/Publications/hw2002.pdf Functional Reactive Programming, Continued]<br />
:Henrik Nilsson, Antony Courtney, and John Peterson. Proceedings of the 2002 ACM SIGPLAN Haskell Workshop (Haskell'02), pages 51 - 64, Pittsburgh, Pennsylvania, USA, October 2002. ACM Press.<br />
<br />
;[http://www.cs.ru.nl/A.vanWeelden/bi-arrows/ There and back again: arrows for invertible programming]<br />
:Artem Alimarine, Sjaak Smetsers, Arjen van Weelden, Marko van Eekelen, Rinus Plasmeijer. Proceedings of the 2005 ACM SIGPLAN workshop on Haskell. Tallinn, Estonia, 86 - 97 2005 ISBN 1-59593-071-X<br />
<br />
Free version of the above paper at http://citeseer.ist.psu.edu/alimarine05there.html or one of the other citeseer mirrors<br />
<br />
;[http://www.cse.ogi.edu/~magnus/ProdArrows/ ProdArrows -- Arrows for Fudgets]<br />
:Magnus Carlsson, 2001.<br />
<br />
;[http://www.cs.umd.edu/~jfoster/arrows.pdf Directing JavaScript with Arrows] :Jeffrey S. Foster et al, 2008 (submitted)<br />
<br />
===Arrow theory===<br />
<br />
;[http://www.math.mcgill.ca/~rags/bang/context1.ps.gz Categories for Computation in Context and Unified Logic]<br />
:Richard Blute, J.R.B. Cockett and R.A.G. Seely. In Journal of Pure and Applied Algebra 116:49-98, 1997.<br />
<br />
;[http://www.cs.ru.nl/~heunen/publications/2006/arrows/arrows.pdf Arrows, like Monads, are Monoids]<br />
:Chris Heunen and Bart Jacobs. In Electronic Notes in Theoretical Computer Science, Volume 158, 5 May 2006, Pages 219-236.<br />
<br />
;[ftp://ftp.dcs.qmw.ac.uk/pub/lfp/edmundr/premoncat.ps.gz Premonoidal Categories and Notions of Computation]<br />
:John Power and Edmund Robinson. In Mathematical Structures in Computer Science 7(5):453-468, 1997.<br />
<br />
;[http://www.cs.bham.ac.uk/~hxt/research/TACSfinal.ps Environments, Continuation Semantics and Indexed Categories]<br />
:John Power and Hayo Thielecke. In Proc. Theoretical Aspects of Computer Science, LNCS 1281, pp 391-414, 1997.<br />
<br />
;[http://www.cs.bham.ac.uk/~hxt/research/closed-freyd-and-kappa.ps Closed Freyd- and kappa-categories]<br />
:John Power and Hayo Thielecke. ICALP'99, LNCS 1644, Springer, 1999.</div>MitchellNCharityhttps://wiki.haskell.org/index.php?title=Arrow&diff=20542Arrow2008-04-12T20:33:58Z<p>MitchellNCharity: Added an introductory section. Neatened article hierarchy. Reordered external links. Caveated old "Practice" post. More cleanup needed.</p>
<hr />
<div>{{Standard class|Arrow|module=Control.Arrow|module-doc=Control-Arrow|package=base}}<br />
<br />
__TOC__<br />
<br />
== Overview ==<br />
<br />
Arrows, or Freyd-categories, are a generalization of Monads.<br />
<br />
"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)''<br />
<br />
For an introduction, see [[#External links]].<br />
<br />
== Library ==<br />
<br />
* [http://www.haskell.org/ghc/docs/latest/html/libraries/base/Control-Arrow.html Control.Arrow] is the standard library for arrows.<br />
* [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).<br />
* [http://darcs.haskell.org/packages/arrows/ arrows package]<br />
<br />
== Examples ==<br />
<br />
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.).<br />
<br />
=== Practice ===<br />
<br />
Reasons, when it may be worth of solving a specific problem with arrows (instead of [[monad]]s) can be read in<br />
[http://caml.inria.fr/pub/ml-archives/caml-list/2000/08/3c42f0fad3b3ecaca4f6043af65f6315.en.html a message from Daan Leijen].<br />
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<br />
test = proc -> do<br />
question <- ask -< "what is the question ?"<br />
answer <- ask -< question<br />
returnA -< ("the answer to '" ++ question ++ "' is " ++ answer)<br />
(or something vaguely like that).<br />
<br />
=== Function ===<br />
<br />
Arow operations <hask>arr</hask> and <hask>>>></hask> are rather straightforward. For implementing <hask>first</hask> and related concepts, see [[Prelude extensions#Tuples]].<br />
<br />
=== Parser ===<br />
<br />
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].<br />
<br />
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):<br />
:<math>\mathrm{expr} ::= \mathrm{term}\;\mathrm{exprTail}</math><br />
:<math>\mathrm{exprTail} ::= \mathbf{PLUS}\;\mathrm{term}\;\mathrm{exprTail}\;\vert\;\mathbf{MINUS}\;\mathrm{term}\;\mathrm{exprTail}\;\vert\;\epsilon</math><br />
is represented with arrow parsers this way:<br />
<haskell><br />
data Expr = Plus Expr Expr | Minus Expr Expr | ...<br />
<br />
expr :: ParseArrow () Expr<br />
expr = proc () -> do<br />
t <- term -< ()<br />
exprTail -< t<br />
<br />
exprTail :: ParseArrow Expr Expr<br />
exprTail = proc e -> do<br />
symbol PLUS -< ()<br />
t <- term -< ()<br />
exprTail -< Plus e t<br />
<+> do<br />
symbol MINUS -< ()<br />
t <- term -< ()<br />
exprTail -< Minus e t<br />
<+> returnA -< e<br />
</haskell><br />
<br />
An arrow parser library: [http://www.cs.helsinki.fi/u/ekarttun/PArrows/ PArrows] written by [http://www.haskell.org/tmrwiki/EinarKarttunen Einar Karttunen].<br />
<br />
Another arrow parser implementation: [http://antti-juhani.kaijanaho.fi/tmp/LLParser.hs LLParser.hs] written by [http://antti-juhani.kaijanaho.fi/newblog/ Antti-Juhani Kaijanaho] (I read the [http://www.scannedinavian.com/~shae/blog/2006-03-14.html reference] to it in [http://www.scannedinavian.com/~shae/blog/index.html Shae Erisson's blog / journal]).<br />
<br />
The funny thing which took a long time for me to understand arrow parsers is a sort of differential approach -- in contrast to the [http://www.willamette.edu/~fruehr/haskell/seuss.html 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.)<br />
<br />
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.<br />
<br />
[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]<br />
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.<br />
I mean, even the mere definition of <hask>&&&</hask> operation<br />
<haskell><br />
p &&& q = arr dup >>> first p >>> second q<br />
</haskell><br />
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>):<br />
<haskell><br />
-- | Match zero or more occurrences of the given parser.<br />
many :: MD i o -> MD i [o]<br />
many = MStar<br />
<br />
-- | Match one or more occurrences of the given parser.<br />
many1 :: MD i o -> MD i [o]<br />
many1 x = (x &&& MStar x) >>> pure (\(b,bs) -> (b:bs))<br />
</haskell><br />
The definition of <hask>between</hask> parser combinator can show another example for the importance of the order in which the computation (e.g. the side effects) take place using <hask>&&&</hask> operation:<br />
<haskell><br />
between :: MD i t -> MD t close -> MD t o -> MD i o<br />
between open close real = open >>> (real &&& close) >>^ fst<br />
</haskell><br />
A more complicated example (from the same module):<br />
<haskell><br />
-- | Match one or more occurrences of the given parser separated by the separator.<br />
sepBy1 :: MD i o -> MD i o' -> MD i [o]<br />
sepBy1 p s = (many (p &&& s >>^ fst) &&& p) >>^ (\(bs,b) -> bs++[b])<br />
</haskell><br />
This makes clear that the order of effects of the operands of <hask>&&&</hask> operation can be important. But let us mention also a counterexample, e.g. nondeterministic functions arrows, or more generally, the various implementations of binary relation arrows -- there is no such sequencing of effect orders. Now let us see this fact on the mere mathematical concept of binary relations (not minding how it implemented):<br />
:<math>(\rho</math> <hask>&&&</hask> <math>\sigma) x \left\langle y_0, y_1\right\rangle \Leftrightarrow x \rho y_0 \land x \sigma y_1</math><br />
:<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><br />
<br />
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.<br />
<br />
=== Stream processor ===<br />
<br />
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.<br />
<br />
Arrows are useful also to grasp the concept of stream processors. See details in<br />
* [http://www.cse.ogi.edu/~magnus/ProdArrows/ ProdArrows -- Arrows for Fudgets] written by [http://www.cse.ogi.edu/~magnus/ Magnus Carlsson], 2001.<br />
* [http://www.haskell.org/arrows/biblio.html Generalising Monads to Arrows] written by [http://www.cs.chalmers.se/~rjmh/ John Hughes] (section 6, pages 20--24)<br />
<br />
==== Functional I/O, graphical user interfaces ====<br />
<br />
* [http://citeseer.ist.psu.edu/hudak89expressiveness.html On the Expressiveness of Purely Functional I/O Systems] written by Paul Hudak and Raman S. Sundaresh.<br />
* [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.<br />
* [http://kevin.atkinson.dhs.org/fg/doc/FG.html FG]<br />
* [[Phooey]]<br />
* [[Grapefruit]]<br />
<br />
==== Dataflow languages ====<br />
<br />
[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]].<br />
<br />
=== Automaton ===<br />
<br />
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].<br />
<br />
How these concepts can be implemented using the concept of arrow, can be found in the introductory articles on arrows mentioned above.<br />
<br />
== External links ==<br />
* [http://www.cs.chalmers.se/~rjmh/afp-arrows.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.<br />
* [http://www.haskell.org/arrows/index.html Arrows: A General Interface to Computation] written by [http://www.soi.city.ac.uk/%7Eross/ Ross Paterson].<br />
* [http://www.haskell.org/arrows/biblio.html ''Generalising Monads to Arrows'', and other papers]<br />
* [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].<br />
* [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].<br />
* [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.<br />
* HaWiki's [http://haskell.org/hawiki/UnderstandingArrows UnderstandingArrows].''broken link''<br />
<br />
== See also ==<br />
<br />
* [[Research papers/Monads and arrows]].<br />
* [[Arrow tutorial]].<br />
<br />
[[Category:Standard classes]]<br />
[[Category:Arrow]]</div>MitchellNCharityhttps://wiki.haskell.org/index.php?title=Mathematical_prelude_discussion&diff=8263Mathematical prelude discussion2006-11-14T23:16:26Z<p>MitchellNCharity: Added an LtU link. Owned a comment. Moved sections around.</p>
<hr />
<div>== Purpose ==<br />
<br />
There have been many ideas for improving the prelude's support for mathematics. Including the addition of algebraic classes. But the discussion is spread over years of list archives and a half dozen websites. And the discussion has never gelled.<br />
<br />
This page is intended to collect links to past discussion, and to provide a focal point for advancing the discussion.<br />
<br />
== Todo ==<br />
<br />
*Flesh out list of proposals. First from [[Libraries_and_tools/Mathematics]].<br />
*Add links to discussions in list archive, and elsewhere.<br />
<br />
== Libraries and proposals ==<br />
<br />
=== Numeric prelude ===<br />
<br />
:[http://haskell.org/communities/06-2006/html/report.html#numericprelude 2006-06 report]<br />
:[http://darcs.haskell.org/numericprelude/ darcs.haskell.org/numericprelude/]<br />
<br />
=== Basic Algebra Library (BAL) ===<br />
<br />
:Is not in community report 2006-06.<br />
:[http://www.botik.ru/pub/local/Mechveliani/basAlgPropos/0.04/announce.txt 0.04/announce.txt (2006-02)]<br />
:[http://www.botik.ru/pub/local/Mechveliani/basAlgPropos/ www.botik.ru/pub/local/Mechveliani/basAlgPropos/]<br />
:Formerly refered to as "basic algebra proposal".<br />
<br />
=== See Also ===<br />
<br />
[[Libraries_and_tools/Mathematics]]<br />
<br />
== Discussion ==<br />
<br />
[http://magma.maths.usyd.edu.au/magma/htmlhelp/MAGMA.htm MAGMA] is an example of a language which embraced mathematical structure. [[User:MitchellNCharity|MitchellNCharity]] 23:16, 14 November 2006 (UTC)<br />
<br />
[http://lambda-the-ultimate.org/node/1655#comment-20299 LtU thread 1655]</div>MitchellNCharityhttps://wiki.haskell.org/index.php?title=Future_of_Haskell&diff=8262Future of Haskell2006-11-14T23:06:49Z<p>MitchellNCharity: Better "Basic algebra proposal" link.</p>
<hr />
<div>=Future development of Haskell=<br />
<br />
Haskell 98 is complete. It is<br />
the current official definition of Haskell (modulo some minor fixes,<br />
as detailed on the Haskell 98 bug page). We expect that this<br />
language will be supported in the long term even as new extensions are<br />
added to Haskell; compilers will continue to support Haskell 98 (via a<br />
special flag).<br />
<br />
The process of defining a successor to Haskell 98 has started. All <br />
information about this is on<br />
<blockquote><br />
<b>[http://hackage.haskell.org/trac/haskell-prime The Haskell' Wiki]</b><br />
</blockquote><br />
<br />
----<br />
<br />
The language evolves and numerous extensions have been proposed and many of them have been implemented in some Haskell systems; for example<br />
pattern guards, scoped type variables, multi-parameter type classes, local universal and existential quantification. <br />
The [[Haskell mailing lists]] <br />
are a forum for discussing new language features.<br />
People proposing an additional language feature should implement the new feature or convince the developers of one of the Haskell systems to do so.<br />
Then many people can test the practical usefulness of the extension.<br />
Finally, the people seriously interested in the new feature should define the new feature with respect to Haskell 98 in a document (a new mailing list can be set up for this purpose). This kind of addendum to the Haskell 98 report clearifies the details and can be used for adding the feature to other Haskell systems. The definition of the foreign function interface (FFI) for Haskell is a good example for this process.<br />
<br />
On a rather longer time schedule a committee lead by John Launchbury<br />
may develop Haskell II. Obviously well-tested and well-described extension<br />
proposals will have a higher chance of being adopted.<br />
<br />
<br />
== Extensions of Haskell == <br />
<br />
<DL><DT><B>[http://haskell.org/hawiki/HaskellTwo A Wiki page]</B><DD><br />
collects all kinds of extensions proposed for the language, libraries and specific implementations.<br />
</DL><br />
<br />
<P><br />
Below we present some of the various extensions that have<br />
been implemented or proposed.<br />
See also the [[Haskell mailing lists]].<br />
<br />
<UL><br />
<li id="views"><b>Views</b> allow multiple `logical' constructors to match<br />
against real constructors in patterns.<br />
<ul><br />
<li>A [http://www.haskell.org/development/views.html views proposal] has been submitted for consideration in<br />
future Haskell reports. Implemented in hbc (?)</li><br />
<li>See also HaWiki's [http://haskell.org/hawiki/Views Views]</li><br />
<li>[[Dependent type]]s provide a way for not-forgetful views: views who cannot lie.<br />
</ul><br />
<li><b>Pattern Guards</b> by Simon Peyton-Jones is a proposal<br />
to generalize guards used in function definitions. See the<br />
[http://research.microsoft.com/Users/simonpj/Haskell/guards.html proposal] for<br />
further details. Implemented in GHC, proposed for Haskell 2. <br />
<li> [[Mathematical prelude discussion#Basic Algebra Library (BAL)|Basic algebra proposal.]] In particular: Reformulating numeric classes,<br />
instance ruled type and domain conversion.<br />
<LI> [http://www.soi.city.ac.uk/~ross/notes/ArrowsInHaskell.html Haskell Proposal: Syntactic Sugar for Arrows]<br />
<li>Mark Shields and Simon Peyton Jones: [http://research.microsoft.com/Users/simonpj/Papers/first-class-modules/ First-class Modules for Haskell] discusses a lot of extension proposals integrated in a coherent design. See also [[First-class module]] page.<br />
<li>[[Extensible record]] page: problems where extensible records are useful, proposals, implementations etc.<br />
</UL><br />
<br />
== Variations of Haskell ==<br />
<br />
<br />
<DL><br />
<dt>[http://www.cs.mu.oz.au/~sulzmann/chameleon/ Chameleon]<br />
<dd>Chameleon is a Haskell-style language which provides a flexible<br />
overloading mechanism based on Constraint Handling Rules (CHRs).<br />
The user can impose conditions on overloaded identifiers via CHRs.<br />
<br />
<DT>[http://www.cse.ogi.edu/~mpj/goferarc/index.html Gofer]<br />
<DD><br />
Gofer is a small interpreter by Mark Jones supporting a language based on the Haskell report version 1.2.<br />
Gofer is intended as an experimental language, particularly where type classes<br />
are involved. Although Haskell has adopted a number of ideas from Gofer, the Gofer type class system is still more flexible than the Haskell one.<br />
Available for all Unix platforms including Linux, DOS, and Macs.<br />
Hugs is the successor to Gofer and Gofer is no longer supported.<BR><br />
[http://www.google.com/search?q=goferdoc Html-version of the Gofer manual]<br />
<br />
<DT>[http://www.cee.hw.ac.uk/~dsg/gph/ GPH, Glasgow Parallel Haskell]<DD><br />
is an extension of Haskell for parallel programming. It<br />
adds just two new primitives to the language, namely, a form of<br />
parallel composition <b>par</b>, and sequential composition <b>seq</b>. With<br />
judicious use of <b>par</b> and <b>seq</b> it is possible to express how a program<br />
should be evaluated in parallel. <br />
<br />
<DT>[http://abp.lcs.mit.edu/projects/ph/ pH - a parallel Haskell]<br />
<DD><br />
The pH language is is a parallel, eagerly-evaluated variant of Haskell with syntactic provisions for<br />
loops, barriers, and I- and M- structure storage. The eager evaluation model of pH is similar to<br />
that of Id; the current version of the pH compiler shares a back end with the Id compiler, producing<br />
code for the Monsoon dataflow machine. The front end of the pH compiler is a modification of<br />
hbc.<br />
<br />
<DT>[http://www.score.is.tsukuba.ac.jp/~chak/goffin/ Goffin]<DD><br />
A Haskell extension for parallel and distributed<br />
programming.<br />
<br />
<br />
<dt>[http://www.mondrian-script.org/ Mondrian]<dd><br />
<br />
Mondrian is evolving from "just" an internet scripting language to a "functional language for OO environments". Mondrian is a non-strict <br />
functional language with threads, exceptions and interlanguage <br />
working - a Haskell "light" with extras.<br />
<br />
<br />
<DT>[http://www.cs.chalmers.se/~patrikj/poly/polyp/ PolyP - a polytypic programming language]<DD><br />
PolyP extends a functional language (a subset of Haskell) with a construct for writing polytypic functions. A polytypic function is a function that is defined by induction on the structure of user-defined datatypes.<br />
<br />
<DT>[http://www.cs.chalmers.se/~nordland/ohaskell/ O'Haskell]<DD><br />
O'Haskell is an object-oriented extension to Haskell developed at<br />
Chalmers. O'Haskell conservatively adds two major features to the<br />
Haskell core: a monad of concurrent, state-encapsulating reactive <br />
objects, and a type system with subtyping between records as well <br />
as datatypes. An implementation is available, O'Hugs, which is a<br />
derivative of Hugs 1.3b.<br />
<br />
<DT>[http://www.mathematik.uni-marburg.de/~eden/ Eden]<dd> Eden<br />
is a parallel functional language that provides a new perspective on<br />
parallel programming. It gives programmers enough control to implement<br />
their parallel algorithms efficiently (including granularity issues)<br />
and at the same time frees them from the low level details of process<br />
management. Eden is explicit about processes and their incoming and<br />
outgoing data, but abstracts from the transfer of these data between<br />
processes and the necessary synchronisation. <br />
Eden extends the Haskell but overrules lazy evaluation whenever it is<br />
necessary to support parallelism. <br />
<br />
<dt>[http://www.informatik.uni-kiel.de/~mh/curry/ Curry]<br />
<dd>Curry combines in a seamless way features from functional programming (nested expressions, higher-order functions,<br />
lazy evaluation), logic programming (logical variables, partial data structures, built-in search), and concurrent<br />
programming (concurrent evaluation of expressions with synchronization on logical variables). Many Haskell programs are also valid Curry programs.<br />
<br />
<dt>[http://www.mrtc.mdh.se/projects/DFH/ Data Field Haskell]<br />
<dd>Data Field Haskell implements an instance of Data Fields, a generalization<br />
of arrays. The purpose is to support generic array- and data parallel<br />
programming on a very high level, for rapid prototyping of parallel<br />
algorithms. The most important language extension to Haskell is the<br />
<tt>forall</tt>-construct, which allows convenient definitions of data<br />
fields.<br />
<br />
<dt>[http://www.haskell.org/th/ Template Haskell]<br />
<dd>Template Haskell is an extension to Haskell 98 that allows you to do<br />
type-safe compile-time meta-programming, with Haskell both as the<br />
manipulating language and the language being manipulated.<br />
<br />
<dt>Dependent types</dt><br />
<dd><br />
[[Dependent type]] wikipage on<br />
* concept of dependent types, its usefulness in the world of programming;<br />
* dependently typed languages, possiblity of not-forgetful views;<br />
* simulating dependent types in Haskell, and extending Haskell to have them.<br />
</dd><br />
<br />
</DL><br />
<br />
[[Category:Proposals| ]]</div>MitchellNCharityhttps://wiki.haskell.org/index.php?title=MathematicalPreludeDiscussion&diff=8261MathematicalPreludeDiscussion2006-11-14T23:01:32Z<p>MitchellNCharity: MathematicalPreludeDiscussion moved to Mathematical prelude discussion: Conformance with HaskellWiki:Guidelines.</p>
<hr />
<div>#redirect [[Mathematical prelude discussion]]</div>MitchellNCharityhttps://wiki.haskell.org/index.php?title=Mathematical_prelude_discussion&diff=8260Mathematical prelude discussion2006-11-14T23:01:32Z<p>MitchellNCharity: MathematicalPreludeDiscussion moved to Mathematical prelude discussion</p>
<hr />
<div>== Purpose ==<br />
<br />
There have been many ideas for improving the prelude's support for mathematics. Including the addition of algebraic classes. But the discussion is spread over years of list archives and a half dozen websites. And the discussion has never gelled.<br />
<br />
This page is intended to collect links to past discussion, and to provide a focal point for advancing the discussion.<br />
<br />
== Links to proposals and discussion ==<br />
<br />
=== Numeric prelude ===<br />
<br />
:[http://haskell.org/communities/06-2006/html/report.html#numericprelude 2006-06 report]<br />
:[http://darcs.haskell.org/numericprelude/ darcs.haskell.org/numericprelude/]<br />
<br />
=== Basic Algebra Library (BAL) ===<br />
<br />
:Is not in community report 2006-06.<br />
:[http://www.botik.ru/pub/local/Mechveliani/basAlgPropos/0.04/announce.txt 0.04/announce.txt (2006-02)]<br />
:[http://www.botik.ru/pub/local/Mechveliani/basAlgPropos/ www.botik.ru/pub/local/Mechveliani/basAlgPropos/]<br />
:Formerly refered to as "basic algebra proposal".<br />
<br />
=== See Also ===<br />
<br />
[[Libraries_and_tools/Mathematics]]<br />
<br />
<br />
== Todo ==<br />
<br />
*Flesh out list of proposals. First from [[Libraries_and_tools/Mathematics]].<br />
*Add links to discussions in list archive, and elsewhere.<br />
<br />
<br />
== Discussion ==<br />
<br />
[http://magma.maths.usyd.edu.au/magma/htmlhelp/MAGMA.htm MAGMA] is an example of a language which embraced mathematical structure.</div>MitchellNCharityhttps://wiki.haskell.org/index.php?title=Mathematical_prelude_discussion&diff=8259Mathematical prelude discussion2006-11-14T22:54:50Z<p>MitchellNCharity: Added Basic Algebra Library.</p>
<hr />
<div>== Purpose ==<br />
<br />
There have been many ideas for improving the prelude's support for mathematics. Including the addition of algebraic classes. But the discussion is spread over years of list archives and a half dozen websites. And the discussion has never gelled.<br />
<br />
This page is intended to collect links to past discussion, and to provide a focal point for advancing the discussion.<br />
<br />
== Links to proposals and discussion ==<br />
<br />
=== Numeric prelude ===<br />
<br />
:[http://haskell.org/communities/06-2006/html/report.html#numericprelude 2006-06 report]<br />
:[http://darcs.haskell.org/numericprelude/ darcs.haskell.org/numericprelude/]<br />
<br />
=== Basic Algebra Library (BAL) ===<br />
<br />
:Is not in community report 2006-06.<br />
:[http://www.botik.ru/pub/local/Mechveliani/basAlgPropos/0.04/announce.txt 0.04/announce.txt (2006-02)]<br />
:[http://www.botik.ru/pub/local/Mechveliani/basAlgPropos/ www.botik.ru/pub/local/Mechveliani/basAlgPropos/]<br />
:Formerly refered to as "basic algebra proposal".<br />
<br />
=== See Also ===<br />
<br />
[[Libraries_and_tools/Mathematics]]<br />
<br />
<br />
== Todo ==<br />
<br />
*Flesh out list of proposals. First from [[Libraries_and_tools/Mathematics]].<br />
*Add links to discussions in list archive, and elsewhere.<br />
<br />
<br />
== Discussion ==<br />
<br />
[http://magma.maths.usyd.edu.au/magma/htmlhelp/MAGMA.htm MAGMA] is an example of a language which embraced mathematical structure.</div>MitchellNCharityhttps://wiki.haskell.org/index.php?title=Mathematical_prelude_discussion&diff=8258Mathematical prelude discussion2006-11-14T22:41:45Z<p>MitchellNCharity: Page created.</p>
<hr />
<div>== Purpose ==<br />
<br />
There have been many ideas for improving the prelude's support for mathematics. Including the addition of algebraic classes. But the discussion is spread over years of list archives and a half dozen websites. And the discussion has never gelled.<br />
<br />
This page is intended to collect links to past discussion, and to provide a focal point for advancing the discussion.<br />
<br />
== Links to proposals and discussion ==<br />
<br />
=== Numeric prelude ===<br />
<br />
[http://haskell.org/communities/06-2006/html/report.html#numericprelude 2006-06 report]<br />
<br />
[http://darcs.haskell.org/numericprelude/ darcs.haskell.org/numericprelude/]<br />
<br />
=== See Also ===<br />
<br />
[[Libraries_and_tools/Mathematics]]<br />
<br />
== Todo ==<br />
<br />
*Flesh out list of proposals. First from [[Libraries_and_tools/Mathematics]].<br />
*Add links to discussions in list archive, and elsewhere.<br />
<br />
== Discussion ==<br />
<br />
[http://magma.maths.usyd.edu.au/magma/htmlhelp/MAGMA.htm MAGMA] is an example of a language which embraced mathematical structure.</div>MitchellNCharity