Personal tools

Research papers/Monads and arrows

From HaskellWiki

< Research papers(Difference between revisions)
Jump to: navigation, search
(link)
(Arrows in Haskell: updating broken link to Generalizing Monads to Arrows with top google hit)
(16 intermediate revisions by 8 users not shown)
Line 2: Line 2:
   
 
==Monads==
 
==Monads==
[[Category:Monad]] [[Category:Research]]
+
[[Category:Monad]] [[Category:Arrow]] [[Category:Research]]
See also [[Monad]] HaskellWiki page.
+
See also [[Monad]] and [[Arrow]] HaskellWiki pages.
   
 
;[http://research.microsoft.com/~simonpj/Papers/state-lasc.ps.gz State in Haskell]
 
;[http://research.microsoft.com/~simonpj/Papers/state-lasc.ps.gz State in Haskell]
Line 17: Line 17:
 
: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)
 
: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)
   
;[http://www.cse.ogi.edu/~mpj/pubs/composing.html Composing Monads]
+
;[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.42.2605 Composing Monads]
 
:Mark P. Jones and Luc Duponcheel Research Report YALEU/DCS/RR-1004, Yale University, New Haven, Connecticut, USA, December 1993. (Cited by 66))
 
:Mark P. Jones and Luc Duponcheel Research Report YALEU/DCS/RR-1004, Yale University, New Haven, Connecticut, USA, December 1993. (Cited by 66))
   
Line 29: Line 29:
 
:Philip Wadler. Lisp and Symbolic Computation, Special issue on continuations, 7(1):39-56, January 1994. (Cited by 34)
 
:Philip Wadler. Lisp and Symbolic Computation, Special issue on continuations, 7(1):39-56, January 1994. (Cited by 34)
   
;[http://homepages.inf.ed.ac.uk/wadler/papers/marktoberdorf/marktoberdorf.ps.gz Monads for functional programming]
+
;[http://homepages.inf.ed.ac.uk/wadler/topics/monads.html#marktoberdorf Monads for functional programming]
 
: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)
 
: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)
   
Line 47: Line 47:
 
:Martin Erwig. 10th Int. Workshop on Implementation of Functional Languages (IFL'98), 1-25, 1998
 
:Martin Erwig. 10th Int. Workshop on Implementation of Functional Languages (IFL'98), 1-25, 1998
   
;[http://www.cse.ogi.edu/~magnus/papers/icfp-2002.pdf Monads for Incremental Computing]
+
;[http://portal.acm.org/citation.cfm?id=581482 Monads for Incremental Computing]
 
:Magnus Carlsson, ICFP 2002, 2002.
 
:Magnus Carlsson, ICFP 2002, 2002.
   
;[http://www.cse.ogi.edu/~magnus/Adaptive/ Monads for Incremental Computing]
+
;[http://portal.acm.org/citation.cfm?id=581482 Monads for Incremental Computing]
 
:Magnus Carlsson, ICFP'02.
 
:Magnus Carlsson, ICFP'02.
   
Line 69: Line 69:
 
:Oleg Kiselyov, Chung-chieh Shan, Daniel P. Friedman and Amr Sabry, Functional Pearl, to be presented at ICFP 2005.
 
:Oleg Kiselyov, Chung-chieh Shan, Daniel P. Friedman and Amr Sabry, Functional Pearl, to be presented at ICFP 2005.
   
;[http://citeseer.ist.psu.edu/harrison98modular.html Modular Compilers Based on Monad Transformers]
+
;[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.53.2151 Modular Compilers Based on Monad Transformers]
 
:Harrison, Kamin (1998)
 
:Harrison, Kamin (1998)
   
;[http://citeseer.ist.psu.edu/188147.html Semantic Lego]
+
;[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.40.8121 Semantic Lego]
 
:Espinosa (1995)
 
:Espinosa (1995)
   
Line 80: Line 80:
 
:Levent Erkök, John Launchbury and Andrew Moran. Journal of Theoretical Informatics and Applications. 36. 2. 2002.
 
:Levent Erkök, John Launchbury and Andrew Moran. Journal of Theoretical Informatics and Applications. 36. 2. 2002.
   
;[http://www.cse.ogi.edu/PacSoft/projects/rmb/mdo.pdf A Recursive do for Haskell]
+
;[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.6.5172 A Recursive do for Haskell]
 
: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
 
: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
   
;[http://www.cse.ogi.edu/~erkok/rmb/erkok-thesis.ps.gz Value recursion in monadic computations]
+
;[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.15.1543 Value recursion in monadic computations]
 
:Levent Erkök. PhD. Thesis. OGI School of Science and Engineering. October 2002.
 
:Levent Erkök. PhD. Thesis. OGI School of Science and Engineering. October 2002.
   
;[http://www.cse.ogi.edu/PacSoft/projects/rmb/fics.ps.gz Semantics of fixIO]
+
;[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.15.736 Semantics of fixIO]
 
:Levent Erkök, John Launchbury and Andrew Moran. Workshop on Fixed Points in Computer Science (FICS'01). 2001.
 
:Levent Erkök, John Launchbury and Andrew Moran. Workshop on Fixed Points in Computer Science (FICS'01). 2001.
   
;[http://www.cse.ogi.edu/PacSoft/projects/rmb/mfix.ps.gz Recursive Monadic Bindings]
+
;[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.43.5313 Recursive Monadic Bindings]
 
:Levent Erkok and John Launchbury. Proceedings of the International Conference on Functional Programming ICFP'00. 2000.
 
:Levent Erkok and John Launchbury. Proceedings of the International Conference on Functional Programming ICFP'00. 2000.
   
 
===Applications of monads===
 
===Applications of monads===
  +
  +
;[http://www.cs.chalmers.se/~rjmh/Globals.ps Global Variables in Haskell]
  +
:John Hughes. 2004. JFP.
   
 
;[http://www.informatik.uni-bonn.de/~ralf/publications/IAI-TR-96-9.ps.gz Monadic-style backtracking]
 
;[http://www.informatik.uni-bonn.de/~ralf/publications/IAI-TR-96-9.ps.gz Monadic-style backtracking]
Line 100: Line 103:
 
:Koen Claessen, Journal of Functional Programming. 9(3). 313--323. 1999.
 
:Koen Claessen, Journal of Functional Programming. 9(3). 313--323. 1999.
   
;[http://www.swiss.ai.mit.edu/~dae/related-papers/steele.ps.Z Building Interpreters by Composing Monads]
+
;[http://groups.csail.mit.edu/mac/users/dae/related-papers/steele.ps.Z Building Interpreters by Composing Monads]
 
:Guy L. Steele, Jr.. Principles of Programming Languages (POPL'94). January 1994. (Cited by 67)
 
:Guy L. Steele, Jr.. Principles of Programming Languages (POPL'94). January 1994. (Cited by 67)
   
;[http://www.cse.ogi.edu/~mpj/pubs/modinterp.html Monad Transformers and Modular Interpreters]
+
;[http://www.cs.yale.edu/users/liang-sheng/popl95.ps.gz Monad Transformers and Modular Interpreters]
 
: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)
 
: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)
   
Line 115: Line 118:
 
:Oleg Kiselyov
 
:Oleg Kiselyov
   
;[http://citeseer.ist.psu.edu/ghani02coalgebraic.html Coalgebraic Monads]
+
;[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.15.7796 Coalgebraic Monads]
 
:Ghani, Lth, De Marchi (2002)
 
:Ghani, Lth, De Marchi (2002)
   
;[http://citeseer.ist.psu.edu/uustalu03monad.html Monad Translating Inductive and Coinductive Types]
+
;[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.8.9817 Monad Translating Inductive and Coinductive Types]
 
:Uustalu (2003)
 
:Uustalu (2003)
   
;[http://citeseer.ist.psu.edu/meijer95merging.html Merging Monads and Folds for Functional Programming]
+
;[http://citeseer.ist.psu.edu/old/meijer95merging.html Merging Monads and Folds for Functional Programming]
 
:Meijer, Jeuring (1995)
 
:Meijer, Jeuring (1995)
   
;[http://citeseer.ist.psu.edu/fokkinga94monadic.html Monadic Maps and Folds for Arbitrary Datatypes]
+
;[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.53.3718 Monadic Maps and Folds for Arbitrary Datatypes]
 
:Fokkinga (1994)
 
:Fokkinga (1994)
   
;[http://citeseer.ist.psu.edu/126221.html Modular Denotational Semantics for Compiler Construction]
+
;[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.7816 Modular Denotational Semantics for Compiler Construction]
 
:Sheng Liang (1996)
 
:Sheng Liang (1996)
   
;[http://citeseer.ist.psu.edu/50754.html Monadic Parser Combinators]
+
;[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.53.340 Monadic Parser Combinators]
 
:Hutton, Meijer (1996)
 
:Hutton, Meijer (1996)
   
;[http://citeseer.ist.psu.edu/hudak96building.html Building Domain-Specific Embedded Languages]
+
;[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.49.6020l Building Domain-Specific Embedded Languages]
 
:Paul Hudak (1996)
 
:Paul Hudak (1996)
   
;[http://citeseer.ist.psu.edu/finne94programming.html Programming Reactive Systems in Haskell]
+
;[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.46.1260 Programming Reactive Systems in Haskell]
 
;Finne, Jones (1994)
 
;Finne, Jones (1994)
   
;[http://citeseer.ist.psu.edu/jay98costing.html Costing Parallel Programs as a Function of Shapes]
+
;[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.8225 Costing Parallel Programs as a Function of Shapes]
 
;Jay (1998)
 
;Jay (1998)
   
;[http://citeseer.ist.psu.edu/demeuter97monads.html Monads as a theoretical foundation for AOP]
+
;[http://citeseer.ist.psu.edu/old/demeuter97monads.html Monads as a theoretical foundation for AOP]
 
:De Meuter (1997)
 
:De Meuter (1997)
  +
  +
;[http://arxiv.org/pdf/cs.CL/0205026 Monads for natural language semantics]
  +
: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
  +
  +
;[http://arxiv.org/abs/cs.NA/0605058 A Monadic, Functional Implementation of Real Numbers]
  +
:Russell O'Connor, 2006. Mathematical Structures in Computer Science.
  +
  +
;[http://research.microsoft.com/%7Esimonpj/papers/control/ A monadic framework for delimited continuations]
  +
:Kent Dybvig, Simon Peyton Jones, and Amr Sabry.
   
 
See also [[Monad#Monads_in_other_languages|monads in other languages]].
 
See also [[Monad#Monads_in_other_languages|monads in other languages]].
Line 149: Line 161:
 
===Comonads===
 
===Comonads===
   
;[http://citeseer.ist.psu.edu/kieburtz99codata.html Codata and Comonads in Haskell]
+
;[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.45.4741 Codata and Comonads in Haskell]
 
:Kieburtz - 1999
 
:Kieburtz - 1999
   
;[http://citeseer.ist.psu.edu/510658.html The Dual of Substitution is Redecoration]
+
;[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.16.9369 The Dual of Substitution is Redecoration]
 
:Tarmo Uustalu, Varmo Vene. Trends in Functional Programming 3. (2002)
 
:Tarmo Uustalu, Varmo Vene. Trends in Functional Programming 3. (2002)
   
Line 158: Line 170:
 
:Ghani et al.
 
:Ghani et al.
   
;[http://citeseer.ist.psu.edu/uustalu01recursion.html Recursion Schemes from Comonads]
+
;[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.18.5587 Recursion Schemes from Comonads]
 
:Uustalu, Vene, Pardo (2001)
 
:Uustalu, Vene, Pardo (2001)
   
;[http://citeseer.ist.psu.edu/brookes91computational.html Computational Comonads and Intensional Semantics]
+
;[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.45.4952 Computational Comonads and Intensional Semantics]
 
:Brookes, Geva, 1992
 
:Brookes, Geva, 1992
   
Line 174: Line 186:
 
:Eugenio Moggi. Logic in Computer Science, 1989. LICS '89, Proceedings., Fourth Annual Symposium on (1989), pp. 14-23.
 
:Eugenio Moggi. Logic in Computer Science, 1989. LICS '89, Proceedings., Fourth Annual Symposium on (1989), pp. 14-23.
   
;[http://citeseer.ist.psu.edu/filinski99representing.html Representing Layered Monads]
+
;[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.46.2016 Representing Layered Monads]
 
: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.
 
: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.
   
;[http://www.disi.unige.it/person/MoggiE/APPSEM00/BHM-revised.ps.gz Monads and Effects]
+
;[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.37.5845 Monads and Effects]
:Eugenio Moggi. APPSEM'00 Summer School, LNCS 2395, 2002
+
:Nick Benton, John Hughes and Eugenio Moggi. APPSEM'00 Summer School, LNCS 2395, 2002
   
;[http://citeseer.ist.psu.edu/ariola98correctness.html Correctness of Monadic State: An Imperative Call-by-Need Calculus]
+
;[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.27.9631 Correctness of Monadic State: An Imperative Call-by-Need Calculus]
 
:Ariola, Sabry (1998)
 
:Ariola, Sabry (1998)
 
;[http://citeseer.ist.psu.edu/147178.html Promotional Transformation of Monadic Programs]
 
:Hu, Iwasaki (1995)
 
   
 
;[http://www.disi.unige.it/person/MoggiE/ftp/jfp01.ps.gz Monadic Encapsulation of Effects: A Revised Approach (extended version)]
 
;[http://www.disi.unige.it/person/MoggiE/ftp/jfp01.ps.gz Monadic Encapsulation of Effects: A Revised Approach (extended version)]
 
:Journal of Functional Programming, 11(6), 2001.
 
:Journal of Functional Programming, 11(6), 2001.
   
;[http://citeseer.ist.psu.edu/150326.html Towards a Mathematical Operational Semantics]
+
;[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.730 Towards a Mathematical Operational Semantics]
 
:Turi, Plotkin (1997) (53 citations)
 
:Turi, Plotkin (1997) (53 citations)
   
;[http://citeseer.ist.psu.edu/mason91equivalence.html Equivalence in Functional Languages with Effects]
+
;[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.9447 Equivalence in Functional Languages with Effects]
 
:Mason, Talcott (1991) (49 citations)
 
:Mason, Talcott (1991) (49 citations)
   
;[http://citeseer.ist.psu.edu/124606.html Computational Types from a Logical Perspective]
+
;[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.2029 Computational Types from a Logical Perspective]
 
:Benton, Bierman (1995)
 
:Benton, Bierman (1995)
   
;[http://citeseer.ist.psu.edu/wansbrough97modular.html A Modular Monadic Action Semantics]
+
;[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.35.4895 A Modular Monadic Action Semantics]
 
:Wansbrough (1997)
 
:Wansbrough (1997)
   
;[http://citeseer.ist.psu.edu/moggi98functor.html Functor Categories and Two-Level Languages]
+
;[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.41.5895 Functor Categories and Two-Level Languages]
 
:Moggi (1998)
 
:Moggi (1998)
   
;[http://citeseer.ist.psu.edu/moggi94categorytheoretic.html A Category-Theoretic Account of Program Modules]
+
;[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.41.3812 A Category-Theoretic Account of Program Modules]
 
:Moggi (1994)
 
:Moggi (1994)
  +
  +
===Reasoning about Monads===
  +
  +
;[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.52.8527 Promotional Transformation of Monadic Programs]
  +
:Hu, Iwasaki (1995)
  +
  +
;[http://www.itu.dk/~kss/papers/icfp07.pdf Inductive Reasoning about Effectful Data Types]
  +
:Andrzej Filinski and Kristian Støvring. International Conference on Functional Programming (ICFP'07), Proceedings, ACM Press, 2007.
  +
  +
;[http://wwwtcs.inf.tu-dresden.de/~voigt/icfp09.pdf Free Theorems Involving Type Constructor Classes]
  +
:Janis Voigtländer. International Conference on Functional Programming (ICFP'09), Proceedings, ACM Press, 2009.
  +
   
 
==Arrows==
 
==Arrows==
Line 213: Line 234:
 
===Arrows in Haskell===
 
===Arrows in Haskell===
   
;[http://www.cs.chalmers.se/~rjmh/Papers/arrows.ps Generalising Monads to Arrows],
+
;[http://www.ittc-ku.net/Projects/SLDG/filing_cabinet/Hughes_Generalizing_Monads_to_Arrows.pdf Generalising Monads to Arrows],
 
:John Hughes, in Science of Computer Programming 37, pp67-111, May 2000. (draft online)
 
:John Hughes, in Science of Computer Programming 37, pp67-111, May 2000. (draft online)
   
Line 236: Line 257:
 
:Patrik Jansson and Johan Jeuring, Science of Computer Programming 43(1), pp35-75, 2002.
 
:Patrik Jansson and Johan Jeuring, Science of Computer Programming 43(1), pp35-75, 2002.
   
;[http://www.cse.ogi.edu/~krstic/psfiles/hyperfunctions.pdf Hyperfunctions]
+
;[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.20.7652 Hyperfunctions]
 
:Sava Krstic, John Launchbury and Dusko Pavlovic, Workshop on Fixed Points in Computer Science, Sep 2001.
 
:Sava Krstic, John Launchbury and Dusko Pavlovic, Workshop on Fixed Points in Computer Science, Sep 2001.
   
Line 245: Line 266:
 
: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
 
: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
   
;[http://www.cse.ogi.edu/~magnus/ProdArrows/ ProdArrows -- Arrows for Fudgets]
+
Free version of the above paper at http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.60.7278 or one of the other citeseer mirrors
  +
  +
;[http://web.archive.org/web/20071225224717/http://www.cse.ogi.edu/~magnus/ProdArrows/ ProdArrows -- Arrows for Fudgets]
 
:Magnus Carlsson, 2001.
 
:Magnus Carlsson, 2001.
  +
  +
;[http://www.cs.umd.edu/~jfoster/arrows.pdf Directing JavaScript with Arrows] :Jeffrey S. Foster et al, 2008 (submitted)
   
 
===Arrow theory===
 
===Arrow theory===
Line 253: Line 276:
 
:Richard Blute, J.R.B. Cockett and R.A.G. Seely. In Journal of Pure and Applied Algebra 116:49-98, 1997.
 
:Richard Blute, J.R.B. Cockett and R.A.G. Seely. In Journal of Pure and Applied Algebra 116:49-98, 1997.
   
;[ftp://ftp.dcs.qmw.ac.uk/pub/lfp/edmundr/premoncat.ps.gz Premonoidal Categories and Notions of Computation]
+
;[http://www.cs.ru.nl/~heunen/publications/2006/arrows/arrows.pdf Arrows, like Monads, are Monoids]
  +
:Chris Heunen and Bart Jacobs. In Electronic Notes in Theoretical Computer Science, Volume 158, 5 May 2006, Pages 219-236.
  +
  +
;[http://www.dcs.qmw.ac.uk/~edmundr/pubs/mscs97/premoncat.ps Premonoidal Categories and Notions of Computation]
 
:John Power and Edmund Robinson. In Mathematical Structures in Computer Science 7(5):453-468, 1997.
 
:John Power and Edmund Robinson. In Mathematical Structures in Computer Science 7(5):453-468, 1997.
  +
  +
;[http://research.microsoft.com/~nick/premonitapdf.pd Traced Premonoidal Categories]
  +
:Nick Benton and Martin Hyland. In Theoretical Informatics and Applications 37(4):273-299, 2003.
   
 
;[http://www.cs.bham.ac.uk/~hxt/research/TACSfinal.ps Environments, Continuation Semantics and Indexed Categories]
 
;[http://www.cs.bham.ac.uk/~hxt/research/TACSfinal.ps Environments, Continuation Semantics and Indexed Categories]

Revision as of 03:21, 18 October 2011

Contents


1 Monads

See also Monad and Arrow HaskellWiki pages.

State in Haskell
SL Peyton Jones and J Launchbury, Lisp and Symbolic Computation 8(4), Dec 1995, pp293-341. (Cited by 109)
Lazy functional state threads
SL Peyton Jones and J Launchbury, SIGPLAN Symposium on Programming Language Design and Implementation (PLDI'94), Orlando, June 1994, pp24-35. (Cited by 127))
Imperative functional programming
SL Peyton Jones and PL Wadler, 20th ACM Symposium on Principles of Programming Languages (POPL'93), Charleston, Jan 1993, pp71-84. (Cited by 289)
Prological features in a functional setting - axioms and implementations
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)
Composing Monads
Mark P. Jones and Luc Duponcheel Research Report YALEU/DCS/RR-1004, Yale University, New Haven, Connecticut, USA, December 1993. (Cited by 66))
The marriage of effects and monads
Philip Wadler and Peter Thiemann. Submitted to ACM Transactions on Computational Logic. (Cited by 62)
How to declare an imperative
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)
Monads and composable continuations
Philip Wadler. Lisp and Symbolic Computation, Special issue on continuations, 7(1):39-56, January 1994. (Cited by 34)
Monads for functional programming
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)
Combining monads
David King and Philip Wadler. Glasgow Workshop on Functional Programming, Springer Verlag Workshops in Computing Series, Ayr, July 1992. (Cited by 42)
The essence of functional programming
Philip Wadler. Invited talk, 19'th Symposium on Principles of Programming Languages, ACM Press, Albuquerque, January 1992. (Cited by 407)
How to prove monad laws
Oleg Kiselyov, v1.1, Sep 2, 2003, Originally posted as "Re: proving the monad laws" on the Haskell mailing list
Monadification of Functional Programs
Martin Erwig and Deling Ren. Science of Computer Programming, Vol. 52, No. 1-3, 101-129, 2004
The Categorical Imperative - Or: How to Hide Your State Monads
Martin Erwig. 10th Int. Workshop on Implementation of Functional Languages (IFL'98), 1-25, 1998
Monads for Incremental Computing
Magnus Carlsson, ICFP 2002, 2002.
Monads for Incremental Computing
Magnus Carlsson, ICFP'02.

1.1 Monad comprehensions

Comprehending monads
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)

1.2 Monad transformers

Deriving Backtracking Monad Transformers
Ralf Hinze. In Phil Wadler, editor, Proceedings of the 2000 International Conference on Functional Programming, Montreal, Canada, September 18-20, 2000.
Deriving monad transformers
Ralf Hinze. Technical Report IAI-TR-99-1, Institut fr Informatik III, Universitt Bonn, January 1999.
Backtracking, Interleaving, and Terminating Monad Transformers
Oleg Kiselyov, Chung-chieh Shan, Daniel P. Friedman and Amr Sabry, Functional Pearl, to be presented at ICFP 2005.
Modular Compilers Based on Monad Transformers
Harrison, Kamin (1998)
Semantic Lego
Espinosa (1995)

1.3 Recursion

Semantics of Value Recursion for Monadic Input/Output
Levent Erkök, John Launchbury and Andrew Moran. Journal of Theoretical Informatics and Applications. 36. 2. 2002.
A Recursive do for Haskell
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
Value recursion in monadic computations
Levent Erkök. PhD. Thesis. OGI School of Science and Engineering. October 2002.
Semantics of fixIO
Levent Erkök, John Launchbury and Andrew Moran. Workshop on Fixed Points in Computer Science (FICS'01). 2001.
Recursive Monadic Bindings
Levent Erkok and John Launchbury. Proceedings of the International Conference on Functional Programming ICFP'00. 2000.

1.4 Applications of monads

Global Variables in Haskell
John Hughes. 2004. JFP.
Monadic-style backtracking
Ralf Hinze. Technical Report IAI-TR-96-9, Institut fr Informatik III, Universitt Bonn, October 1996.
A Poor Man's Concurrency Monad
Koen Claessen, Journal of Functional Programming. 9(3). 313--323. 1999.
Building Interpreters by Composing Monads
Guy L. Steele, Jr.. Principles of Programming Languages (POPL'94). January 1994. (Cited by 67)
Monad Transformers and Modular Interpreters
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)
Monadic Regions
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."
XLinq: XML Programming Refactored (The Return Of The Monoids)
Erik Meijer and Brian Beckman
Monadic Shell
Oleg Kiselyov
Coalgebraic Monads
Ghani, Lth, De Marchi (2002)
Monad Translating Inductive and Coinductive Types
Uustalu (2003)
Merging Monads and Folds for Functional Programming
Meijer, Jeuring (1995)
Monadic Maps and Folds for Arbitrary Datatypes
Fokkinga (1994)
Modular Denotational Semantics for Compiler Construction
Sheng Liang (1996)
Monadic Parser Combinators
Hutton, Meijer (1996)
Building Domain-Specific Embedded Languages
Paul Hudak (1996)
Programming Reactive Systems in Haskell
Finne, Jones (1994)
Costing Parallel Programs as a Function of Shapes
Jay (1998)
Monads as a theoretical foundation for AOP
De Meuter (1997)
Monads for natural language semantics
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
A Monadic, Functional Implementation of Real Numbers
Russell O'Connor, 2006. Mathematical Structures in Computer Science.
A monadic framework for delimited continuations
Kent Dybvig, Simon Peyton Jones, and Amr Sabry.

See also monads in other languages.

1.5 Comonads

Codata and Comonads in Haskell
Kieburtz - 1999
The Dual of Substitution is Redecoration
Tarmo Uustalu, Varmo Vene. Trends in Functional Programming 3. (2002)
Monads and Comonads
Ghani et al.
Recursion Schemes from Comonads
Uustalu, Vene, Pardo (2001)
Computational Comonads and Intensional Semantics
Brookes, Geva, 1992
Tutorial: Monads, Kleisli Arrows, Comonads and other Rambling Thoughts

1.6 Monad theory

Notions of computation and monads
Eugenio Moggi. Information and Computation, 93(1):55-92, July 1991 ( Cited by 649)
Computational lambda-calculus and monads
Eugenio Moggi. Logic in Computer Science, 1989. LICS '89, Proceedings., Fourth Annual Symposium on (1989), pp. 14-23.
Representing Layered Monads
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.
Monads and Effects
Nick Benton, John Hughes and Eugenio Moggi. APPSEM'00 Summer School, LNCS 2395, 2002
Correctness of Monadic State: An Imperative Call-by-Need Calculus
Ariola, Sabry (1998)
Monadic Encapsulation of Effects: A Revised Approach (extended version)
Journal of Functional Programming, 11(6), 2001.
Towards a Mathematical Operational Semantics
Turi, Plotkin (1997) (53 citations)
Equivalence in Functional Languages with Effects
Mason, Talcott (1991) (49 citations)
Computational Types from a Logical Perspective
Benton, Bierman (1995)
A Modular Monadic Action Semantics
Wansbrough (1997)
Functor Categories and Two-Level Languages
Moggi (1998)
A Category-Theoretic Account of Program Modules
Moggi (1994)

1.7 Reasoning about Monads

Promotional Transformation of Monadic Programs
Hu, Iwasaki (1995)
Inductive Reasoning about Effectful Data Types
Andrzej Filinski and Kristian Støvring. International Conference on Functional Programming (ICFP'07), Proceedings, ACM Press, 2007.
Free Theorems Involving Type Constructor Classes
Janis Voigtländer. International Conference on Functional Programming (ICFP'09), Proceedings, ACM Press, 2009.


2 Arrows

See also Arrow HaskellWiki page.

2.1 Arrows in Haskell

Generalising Monads to Arrows,
John Hughes, in Science of Computer Programming 37, pp67-111, May 2000. (draft online)
A New Notation for Arrows
Ross Paterson. In ICFP 2001, Firenze, Italy, pp229-240]
Arrows and Computation
Ross Paterson, in The Fun of Programming (Jeremy Gibbons and Oege de Moor, Eds.), pp201-222, Palgrave, 2003.

2.2 Applications of arrows

Genuinely Functional User Interfaces
Anthony Courtney and Conal Elliott, in Haskell Workshop 2001, Firenze, Italy, pp41-69.
Arrows, Robots, and Functional Reactive Programming
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.
Polytypic compact printing and parsing
Patrik Jansson and Johan Jeuring, In Proceedings European Symposium on Programming, LNCS 1576, pp273-287, Springer, 1999.
Polytypic data conversion programs
Patrik Jansson and Johan Jeuring, Science of Computer Programming 43(1), pp35-75, 2002.
Hyperfunctions
Sava Krstic, John Launchbury and Dusko Pavlovic, Workshop on Fixed Points in Computer Science, Sep 2001.
Functional Reactive Programming, Continued
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.
There and back again: arrows for invertible programming
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

Free version of the above paper at http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.60.7278 or one of the other citeseer mirrors

ProdArrows -- Arrows for Fudgets
Magnus Carlsson, 2001.
Directing JavaScript with Arrows 
Jeffrey S. Foster et al, 2008 (submitted)

2.3 Arrow theory

Categories for Computation in Context and Unified Logic
Richard Blute, J.R.B. Cockett and R.A.G. Seely. In Journal of Pure and Applied Algebra 116:49-98, 1997.
Arrows, like Monads, are Monoids
Chris Heunen and Bart Jacobs. In Electronic Notes in Theoretical Computer Science, Volume 158, 5 May 2006, Pages 219-236.
Premonoidal Categories and Notions of Computation
John Power and Edmund Robinson. In Mathematical Structures in Computer Science 7(5):453-468, 1997.
Traced Premonoidal Categories
Nick Benton and Martin Hyland. In Theoretical Informatics and Applications 37(4):273-299, 2003.
Environments, Continuation Semantics and Indexed Categories
John Power and Hayo Thielecke. In Proc. Theoretical Aspects of Computer Science, LNCS 1281, pp 391-414, 1997.
Closed Freyd- and kappa-categories
John Power and Hayo Thielecke. ICALP'99, LNCS 1644, Springer, 1999.