Comprehending monads

ABSTRACT

Category theorists invented monads in the 1960's to concisely express certain aspects of universal algebra. Functional programmers invented list comprehensions in the 1970's to concisely express certain programs involving lists. This paper shows how list comprehensions may be generalised to an arbitrary monad, and how the resulting programming feature can concisely express in a pure functional language some programs that manipulate state, handle exceptions, parse text, or invoke continuations. A new solution to the old problem of destructive array update is also presented. No knowledge of category theory is assumed.

REFERENCES

• Blo89: Adrienne Bloss, Update analysis and the efficient implementation of functional aggregates, Proceedings of the fourth international conference on Functional programming languages and computer architecture, p.26-38, September 11-13, 1989, Imperial College, London, United Kingdom [doi>10.1145/99370.99373]
• BW85: M. Barr and C. Wells, Toposes, Triples, and Theories. Springer Verlag, 1985.
• BW88: Richard Bird , Philip Wadler, An introduction to functional programming, Prentice Hall International (UK) Ltd., Hertfordshire, UK, 1988
• Fai87: J. Fairbairn, Making form follow function: an exercise in functional programming style, Software—Practice & Experience, v.17 n.6, p.379-386, June 1987 [doi>10.1002/spe.4380170603]
• FL89: R. Frost , J. Launchbury, Constructing natural language interpreters in a lazy functional language, The Computer Journal, v.32 n.2, p.108-121, April 1989 [doi>10.1093/comjnl/32.2.108]
• Gog88: J.A. Goguen, Higher order functions considered unnecessary for higher order programming. Technical report SRI-CSL-88-1, SRI International, January 1988.
• GL88: David K. Gifford , John M. Lucassen, Integrating functional and imperative programming, Proceedings of the 1986 ACM conference on LISP and functional programming, p.28-38, August 1986, Cambridge, Massachusetts, United States [doi>10.1145/319838.319848]
• GH90: J. Guzm~n and P. Hudak, Single-threaded polymorphic lambda calculus. In {EEE Symposium on Logic in Computer Science, Philadelphia, June 1990.
• GMW79: M. Gordon, R. Milner, and C. Wadsworth, Edinburgh LCF. LNCS 78, Springer-Verlag, 1979.
• Hol83: S. HolmstrSm, A simple and emcient way to handle large data structures in applicative languges. In Proceedings $ERC/Chalmers Workshop on Declarative Programming, University College London, 1983.
• Hud86a: Paul Hudak, A semantic model of reference counting and its abstraction (detailed summary), Proceedings of the 1986 ACM conference on LISP and functional programming, p.351-363, August 1986, Cambridge, Massachusetts, United States [doi>10.1145/319838.319876]
• HMT88: Robin Milner , Mads Tofte , Robert Harper, The definition of Standard ML, MIT Press, Cambridge, MA, 1990
• Hud86b: Paul Hudak, Arrays, non-determinism, side-effects, and parallelism: A functional perspective, Proc. of a workshop on Graph reduction, p.312-327, September 1987, Santa Fe, New Mexico, United States
• Hug89: J. Hughes, Why functional programming matters, The Computer Journal, v.32 n.2, p.98-107, April 1989 [doi>10.1093/comjnl/32.2.98]
• HO89: John Hughes , John O'Donnell, Expressing and Reasoning About Non-Deterministic Functional Programs, Proceedings of the 1989 Glasgow Workshop on Functional Programming, p.308-328, August 21-23, 1989
• HW90: P. Hudak and P. Wadler, editors, Report on ~he Programming Language Haskell. Technical report, Yale University and Glasgow University, April 1990.
• LS86: J. Lambek , P. J. Scott, Introduction to higher order categorical logic, Cambridge University Press, New York, NY, 1986
• Mac71: S. Mac Lane, Categories for the Working Mathematician, Springer-Verlag, 1971.
• Mil84: Robin Milner, A proposal for standard ML, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.184-197, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802035]
• MT89: I. Mason and C. Talcott, Axiomatising operational equivalence in the presence of side effects. In IEEE Symposium on Logic in Computer Science, Asilomar, California, june 1989.
• Mog89a: E. Moggi, Computational lambda-calculus and monads, Proceedings of the Fourth Annual Symposium on Logic in computer science, p.14-23, June 1989, Pacific Grove, California, United States
• Mog89b: E. Moggi, An abstract view of programming languges. Course notes, University of Edinburgh.
• RC86: J Rees , W Clinger, Revised report on the algorithmic language scheme, ACM SIGPLAN Notices, v.21 n.12, p.37-79, Dec. 1986 [doi>10.1145/15042.15043]
• Rey74: John C. Reynolds, On the Relation between Direct and Continuation Semantics, Proceedings of the 2nd Colloquium on Automata, Languages and Programming, p.141-156, July 29-August 02, 1974
• Rey83: J.C. Reynolds, Types, abstraction, and parametric polymorphism. In R. E. A. Mason, editor, Information Processing 83, 513-523, North-Holland, Amsterdam.
• Sch85: David A. Schmidt, Detecting global variables in denotational specifications, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.2, p.299-310, April 1985 [doi>10.1145/3318.3323]
• Spi89: M. Spivey, Term rewriting without exceptions, Science of Computer Programming, 1989.
• Tur82: D.A. Turner, Recursion equations as a programming language. In J. Darlington, P. Henderson, and D. A. Turner, editors, Functional Programming and its Applications, Cambridge University Press, 1982.
• Tur85: D. A. Turner, Miranda: a non-strict functional language with polymorphic types, Proc. of a conference on Functional programming languages and computer architecture, p.1-16, January 1985, Nancy, France
• Wad85: Philip Wadler, How to replace failure by a list of successes, Proc. of a conference on Functional programming languages and computer architecture, p.113-128, January 1985, Nancy, France
• Wad87: P. Wadler, List comprehensions. In S. L. Peyton Jones, The lmplementalion of Functional Programming Languages, Prentice Hall, 1987.
• Wad89: Philip Wadler, Theorems for free!, Proceedings of the fourth international conference on Functional programming languages and computer architecture, p.347-359, September 11-13, 1989, Imperial College, London, United Kingdom [doi>10.1145/99370.99404]
• Wad90: P. Wadler, Linear types can change the world! In IFIP Working Conference on Programming Concepts and Methods, Sea of Gallilee, Israel, April 1990.

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
        D.2.10 Design**
            Subjects: Methodologies**
  D.3 PROGRAMMING LANGUAGES
      D.3.1 Formal Definitions and Theory
          Subjects: Semantics
      D.3.3 Language Constructs and Features
          Subjects: Abstract data types
      D.3.4 Processors
          Subjects: Parsing; Interpreters

  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Lambda calculus and related systems

General Terms:
Algorithms, Design, Languages, Theory