# Research papers/Monads and arrows

### From HaskellWiki

< Research papers(Difference between revisions)

(Updated links) |
(Updated links) |
||

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

Line 86: | Line 86: | ||

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

Line 103: | 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) |
||

Line 145: | Line 145: | ||

;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) |
||

Line 164: | Line 164: | ||

: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 189: | Line 189: | ||

: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 |
:Eugenio Moggi. APPSEM'00 Summer School, LNCS 2395, 2002 |
||

Line 207: | Line 207: | ||

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

Line 248: | Line 248: | ||

: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 272: | Line 272: | ||

:Chris Heunen and Bart Jacobs. In Electronic Notes in Theoretical Computer Science, Volume 158, 5 May 2006, Pages 219-236. |
:Chris Heunen and Bart Jacobs. In Electronic Notes in Theoretical Computer Science, Volume 158, 5 May 2006, Pages 219-236. |
||

− | ;[ftp://ftp.dcs.qmw.ac.uk/pub/lfp/edmundr/premoncat.ps.gz Premonoidal Categories and Notions of Computation] |
+ | ;[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. |
||

## Revision as of 23:21, 17 November 2008

## 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)

- 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

### 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
- Eugenio Moggi. APPSEM'00 Summer School, LNCS 2395, 2002

- Correctness of Monadic State: An Imperative Call-by-Need Calculus
- Ariola, Sabry (1998)

- Promotional Transformation of Monadic Programs
- Hu, Iwasaki (1995)

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

## 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://citeseer.ist.psu.edu/alimarine05there.html 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.

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