Hostname: page-component-78c5997874-4rdpn Total loading time: 0 Render date: 2024-11-05T16:05:10.191Z Has data issue: false hasContentIssue false
  • English
  • Français

Comprehending monads†

Published online by Cambridge University Press:  04 March 2009

Philip Wadler
Philip Wadler
Affiliation:
Department of Computing Science, University of Glasgow, G12 8QQ, [email protected].
Get access Rights & Permissions [Opens in a new window]

Abstract

Category theorists invented monads in the 1960's to express concisely certain aspects of universal algebra. Functional programmers invented list comprehensions in the 1970's to express concisely certain programs involving lists. This paper shows how list comprehensions may be generalised to an arbitrary monad, and how the resulting programming feature can express concisely 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.

Type
Research Article
Information
Mathematical Structures in Computer Science , Volume 2 , Issue 4 , December 1992 , pp. 461 - 493
Copyright
Copyright © Cambridge University Press 1992

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Appel, A. and Jim, T. (1989) Continuation-passing, closure-passing style. In: 16th ACM Symposium on Principles of Programming Languages, Austin, Texas.Google Scholar
Barr, M. and Wells, C. (1985) Toposes, Triples, and Theories. Springer Verlag.CrossRefGoogle Scholar
Bird, R. and Wadler, P. (1988) Introduction to Functional Programming. Prentice Hall.Google Scholar
Bloss, A. (1989) Update analysis and the efficient implementation of functional aggregates. In: 4th Symposium on Functional Programming Languages and Computer Architecture, ACM, London.Google Scholar
Fairbairn, J. (1987) Form follows function. Software — Practice and Experience, 17(6) 379–386.CrossRefGoogle Scholar
Gifford, D. K. and Lucassen, J. M. (1986) Integrating functional and imperative programming. In: ACM Conference on Lisp and Functional Programming. Cambridge, Massachusetts, 28–39.Google Scholar
Goguen, J. A. (1988) Higher order functions considered unnecessary for higher order programming. Technical report SRI-CSL-88–1, SRI International.Google Scholar
Gordon, M.Milner, R. and Wadsworth, C. (1979) Ediburgh LCF. LNCS 78, Springer-Verlag.CrossRefGoogle Scholar
Guzmán, J. and Hudak, P. (1990) Single-threaded polymorphic lambda calculus. In: IEEE Symposium on Logic in Computer Science, Philadelphia.Google Scholar
Harper, R., Milner, R. and Tofte, M. (1988) The definition of Standard ML, version 2. Report ECS-LFCS-88–62, Edinburgh Uiversity, Dept. of Computer Science.Google Scholar
Holmström, S. (1983) A simple and efficient way to handle large data structures in applicative languages. In: Proceedings SERC/Chalmers Workshop on Declarative Programming, University College London.Google Scholar
Hudak, P. (1986a) A semantic model of reference counting and its abstraction (detailed summary). In: ACM Conference on Lisp and Functional Programming, Cambridge, Massachusetts, 351–363.Google Scholar
Hudak, P. (1986) Arrays, non-determinism, side-effects, and parallelism: a functional perspective. In: Fasel, J. H. and Keller, R. M., editors, Workshop o Graph Reduction, Santa Fe, New Mexico, LNCS 279, Springer-Verlag.Google Scholar
Hudak, P., Peyton Jones, S. and Wadler, P., editors, (1991) Report on the Programming Language Haskell: Version 1.1. Technical report, Yale University and Glasgow University.Google Scholar
Hughes, J. (1989) Why functional programming matters. The Computer Journal, 32(2) 98–107.CrossRefGoogle Scholar
Hughes, J. and O'Donnell, J. (1989) Expressing and reasoing about non-deterministic functional programs. In: Davis, K. and Hughes, J., editors, Functional Programming, Glasgow 1989 (Glasgow workshop, Fraserburgh, August), Workshops in Computing, Springer Verlag.Google Scholar
Lambek, J. and Scott, P. (1986) Introduction to Higher Order Categorical Logic. Cambridge University Press.Google Scholar
Mac Lane, S. (1971) Categories for the Working Mathematician. Springer-Verlag.CrossRefGoogle Scholar
Mason, I. and Talcott, C. (1989) Axiomatising operational equivalence in the presence of side effects. In: IEEE Symposium on Logic in Computer Science, Asilomar, California.Google Scholar
Milner, R. (1984) A proposal for Standard ML. In: ACM Symposium on Lisp and Functional Programming, Austin, Texas.Google Scholar
Moggi, E. (1989a) Computational lambda-calculus and monads. In: IEEE Symposium on Logic in Computer Science, Asilomar, California. (A longer version is available as a technical report from the University of Edinburgh.)Google Scholar
Moggi, E. (1989b) An abstract view of programming languages. Course notes, University of Edinburgh.Google Scholar
Plotkin, G. (1975) Call-by-name, call-by-value, and the λ-calculus. Theoretical Computer Science, 1 125–159.CrossRefGoogle Scholar
Rees, J. and Clinger, W., editors, (1986) The revised3 report on the algorithmic language Scheme. ACM SIGPLAn Notices, 21(12) 37–79.CrossRefGoogle Scholar
Reynolds, J. C. (1974) On the relation between direct and continuation semantics. In: Colloquium on Automata, Languages and Programming, Saarbrücken, LNCS 14, Springer-Verlag.Google Scholar
Reynolds, J. C. (1983) Types, abstraction, and parametric polymorphism. In: Mason, R. E. A., editor, Information Processing 83, North-Holland, Amsterdam, 513–523.Google Scholar
Schmidt, D. A. (1985) Detecting global variables in denotational specifications. ACM Transactions on Programming Languages and Systems, 7 299–310.CrossRefGoogle Scholar
Spivey, M. (1990) A functional theory of exceptions. Science of Computer Programming. 14(1) 25–42.CrossRefGoogle Scholar
Turner, D. A. (1982) Recursion equations as a programming language. In: Darlington, J., Henderson, P., and Turner, D. A., editors, Functional Programming and its Applications, Cambridge, University Press.Google Scholar
Turner, D. A. (1985) Miranda: A non-strict functional language with polymorphic types. In: Proceedings of the 2nd International Conference on Functional Programming Languages and Computer Architecture, Nancy, France, LNCS 201, Springer Verlag.Google Scholar
Wadler, P. (1985) How to replace failure by a list of successes. In: 2nd Symposium on Functional Programming Languages and Computer Architecture, Nancy, LNCS 273, Springer-Verlag.Google Scholar
Wadler, P. (1987) List comprehensions. In: Jones, S. L. Peyton, The Implementation of Functional Programming Languages, Prentice Hall.Google Scholar
Wadler, P. (1989) Theorems for free! In: 4th Symposium of Functional Programming Languages and Computer Architecture, ACM, London.Google Scholar
Wadler, P. (1990a) Linear types can change the world! In: Broy, M. and Jones, C., editors, Programming Concepts and Methods (IFIP Working Conference, Sea of Gallilee, Israel, April), North Halland.Google Scholar
Wadler, P. (1990b) Comprehending monads. In: ACM Conference on Lisp and Functional Programming, Nice.CrossRefGoogle Scholar
Wadler, P. (1991) Is there a use for linear logic? In: Conference on Partial Evaluation and Semantics-Baed Program Manipulation (PEPM), ACM, New Haven, Connecticut.Google Scholar
Wadler, P. (1992) The essence of functional programming. In: Proceedings of the 19th Annual Symposium on Principles of Programming Languages, Albuquerque, N.M.Google Scholar