×

Comprehending monads. (English) Zbl 0798.68040

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

MSC:

68P05 Data structures
68N15 Theory of programming languages
18C15 Monads (= standard construction, triple or triad), algebras for monads, homology and derived functors for monads
18C10 Theories (e.g., algebraic theories), structure, and semantics
68Q65 Abstract data types; algebraic specification
08A70 Applications of universal algebra in computer science
03B40 Combinatory logic and lambda calculus

Software:

Haskell
Full Text: DOI

References:

[1] Appel, 16th ACM Symposium on Principles of Programming Languages (1989)
[2] Harper, The definition of Standard ML, version 2 (1988)
[3] Wadler, The Implementation of Functional Programming Languages (1987)
[4] Wadler, 2nd Symposium on Functional Programming Languages and Computer Architecture (1985)
[5] Turner, Proceedings of the 2nd International Conference on Functional Programming Languages and Computer Architecture (1985)
[6] Turner, Functional Programming and its Applications (1982)
[7] DOI: 10.1016/0167-6423(90)90056-J · Zbl 0699.68022 · doi:10.1016/0167-6423(90)90056-J
[8] DOI: 10.1145/3318.3323 · Zbl 0562.68008 · doi:10.1145/3318.3323
[9] Reynolds, Information Processing 83 pp 513– (1983)
[10] Reynolds, Colloquium on Automata, Languages and Programming (1974)
[11] DOI: 10.1145/15042.15043 · doi:10.1145/15042.15043
[12] DOI: 10.1016/0304-3975(75)90017-1 · Zbl 0325.68006 · doi:10.1016/0304-3975(75)90017-1
[13] Moggi, An abstract view of programming languages (1989)
[14] Moggi, IEEE Symposium on Logic in Computer Science (1989)
[15] Milner, ACM Symposium on Lisp and Functional Programming (1984)
[16] Mason, IEEE Symposium on Logic in Computer Science (1989)
[17] Mac Lane, Categories for the Working Mathematician (1971) · doi:10.1007/978-1-4612-9839-7
[18] Lambek, Introduction to Higher Order Categorical Logic (1986) · Zbl 0596.03002
[19] Hughes, Functional Programming, Glasgow 1989 (1989)
[20] DOI: 10.1093/comjnl/32.2.98 · doi:10.1093/comjnl/32.2.98
[21] Hudak, Report on the Programming Language Haskell: Version 1.1 (1991)
[22] Hudak, Workshop o Graph Reduction (1986)
[23] Hudak, ACM Conference on Lisp and Functional Programming pp 351– (1986)
[24] Holmström, Proceedings SERC/Chalmers Workshop on Declarative Programming (1983)
[25] Guzmán, IEEE Symposium on Logic in Computer Science (1990)
[26] Gordon, Ediburgh LCF (1979) · doi:10.1007/3-540-09724-4
[27] Goguen, Higher order functions considered unnecessary for higher order programming (1988)
[28] Gifford, ACM Conference on Lisp and Functional Programming pp 28– (1986)
[29] Wadler, Proceedings of the 19th Annual Symposium on Principles of Programming Languages (1992)
[30] DOI: 10.1002/spe.4380170603 · doi:10.1002/spe.4380170603
[31] Bloss, 4th Symposium on Functional Programming Languages and Computer Architecture (1989)
[32] Wadler, Conference on Partial Evaluation and Semantics-Baed Program Manipulation (PEPM) (1991)
[33] Bird, Introduction to Functional Programming (1988)
[34] Barr, Toposes, Triples, and Theories (1985) · doi:10.1007/978-1-4899-0021-0
[35] Wadler, Programming Concepts and Methods (1990)
[36] Wadler, 4th Symposium of Functional Programming Languages and Computer Architecture (1989)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.