Article

Free access

Comprehending monads

Author:

Philip WadlerAuthors Info & Claims

LFP '90: Proceedings of the 1990 ACM conference on LISP and functional programming

Pages 61 - 78

https://doi.org/10.1145/91556.91592

Published: 01 May 1990 Publication History

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

[1]

A. Bloss, Update analysis and the efficient implementation of functional aggregates. In ~'~h Symposium on Functional Programming Languages and Computer Architecture, ACM, London, September 1989.

Digital Library

[2]

M. Barr and C. Wells, Toposes, Triples, and Theories. Springer Verlag, 1985.

[3]

R. Bird and P. Wadler, Introduction to Functional Programming. Prentice Hall, 1988.

Digital Library

[4]

J. Fairbairn, Form follows function. Software - Practice and Ezperience, 17(6):379-386, June 1987.

Digital Library

[5]

R. Frost and J. Launchbury, Constructing natural language interpreters in a lazy functional language. The Computer Journal, 32(2):108-121, April 1989.

Digital Library

[6]

J.A. Goguen, Higher order functions considered unnecessary for higher order programming. Technical report SRI-CSL-88-1, SRI International, January 1988.

[7]

D.K. Gifford and J. M. Lucassen, integrating functional and imperative programming. in A CM Conference on Lisp and Functional Programming, pp. 28-39, Cambridge, Massachusetts, August 1986.

Digital Library

[8]

J. Guzm~n and P. Hudak, Single-threaded polymorphic lambda calculus. In {EEE Symposium on Logic in Computer Science, Philadelphia, June 1990.

[9]

M. Gordon, R. Milner, and C. Wadsworth, Edinburgh LCF. LNCS 78, Springer-Verlag, 1979.

[10]

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.

[11]

P. Hudak, A semantic model of reference counting and its abstraction (detailed summary). In A CM Conference on Lisp and Functional Programming, pp. 351-363, Cambridge, Massachusetts, August 1986.

Digital Library

[12]

R. Harper, R. Milner, and M. Torte, The definition of Standard ML, version 2. Report ECS-LFCS-88-62, Edinburgh University, Computer Science Dept., 1988.

Digital Library

[13]

P. Hudak, Arrays, non-determinism, sideeffects, and parallelism: a functional perspective. In J. H. Fasel and R. M. Keller, editors, Workshop on Graph Reduction, Santa Fe, New Mexico, September-October 1986. LNCS 279, Springer-Verlag, 1986.

Digital Library

[14]

J. Hughes, Why functional programming matters. The Computer Journal, 32(2):98- 107, April 1989.

Digital Library

[15]

J. Hughes and J. O'Donnell, Expressing and reasoning about non-deterministic functional programs. Glasgow Workshop on Functional Programming, Fraserburgh, August 1989.

Digital Library

[16]

P. Hudak and P. Wadler, editors, Report on ~he Programming Language Haskell. Technical report, Yale University and Glasgow University, April 1990.

[17]

J. Lambek and P. Scott, Introduction to Higher Order Categorical Logic, Cambridge University Press, 1986.

Digital Library

[18]

S. Mac Lane, Categories for the Working Mathematician, Springer-Verlag, 1971.

[19]

R. Milner, A proposal for Standard ML. In A CM Symposium on Lisp and Functional Programming, Austin, Texas, August 1984.

Digital Library

[20]

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.

[21]

E. Moggi, Computational lambda-calculus and monads. In IEEE Symposium on Logic in Computer Science, Asilomar, California, June 1989. (A longer version is available as a technical report from the University of Edinburgh.)

Digital Library

[22]

E. Moggi, An abstract view of programming languges. Course notes, University of Edinburgh.

[23]

J. Rees and W. Clinger (eds.), The reviseda report on the algorithmic language Scheme. A CM SIGPLAN Notices, 21(12):37- 70 (~986).

Digital Library

[24]

J.C. Reynolds, On the relation between direct and continuation semantics. In Colloquium on Automata, Languages and Programming, Saarbriicken, July-August 1974, LNCS 14, Springer-Verlag, 1974.

Digital Library

[25]

J.C. Reynolds, Types, abstraction, and parametric polymorphism. In R. E. A. Mason, editor, Information Processing 83, 513-523, North-Holland, Amsterdam.

[26]

D.A. Schmidt, Detecting global variables in denotational specifications. A CM Transactions on Programming Languages and Systems, 7:299-310, 1985.

Digital Library

[27]

M. Spivey, Term rewriting without exceptions, Science of Computer Programming, 1989.

[28]

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.

[29]

D.A. Turner, Miranda: A non-strict functional language with polymorphic types. In Proceedings of the 2'nd International Conference on Functional Programming Languages and Computer Architecture, Nancy, France, September 1985. LNCS 201, Springer Verlag, 1985.

Digital Library

[30]

P. Wadler, How to replace failure by a list of successes. In 2'nd Symposium on Functional Programming Languages and Computer Architecture, Nancy, September 1985. LNCS 273, Springer-Verlag, 1985.

Digital Library

[31]

P. Wadler, List comprehensions. In S. L. Peyton Jones, The lmplementalion of Functional Programming Languages, Prentice Hall, 1987.

[32]

P. Wadler, Theorems for free! In d'th Symposium on Functional Programming Languages and Computer Architecture, ACM, London, September 1989.

Digital Library

[33]

P. Wadler, Linear types can change the world! In IFIP Working Conference on Programming Concepts and Methods, Sea of Gallilee, Israel, April 1990.

Cited By

Song YFoo DChin W(2024)Specification and Verification for Unrestricted Algebraic Effects and HandlingProceedings of the ACM on Programming Languages10.1145/36746568:ICFP(909-937)Online publication date: 15-Aug-2024
https://dl.acm.org/doi/10.1145/3674656
Koopman PLubbers M(2023)Strongly-Typed Multi-View Stack-Based ComputationsProceedings of the 25th International Symposium on Principles and Practice of Declarative Programming10.1145/3610612.3610623(1-12)Online publication date: 22-Oct-2023
https://dl.acm.org/doi/10.1145/3610612.3610623
Haselwarter PRivas EVan Muylder AWinterhalter TAbate CSidorenco NHriţcu CMaillard KSpitters B(2023)SSProve: A Foundational Framework for Modular Cryptographic Proofs in CoqACM Transactions on Programming Languages and Systems10.1145/359473545:3(1-61)Online publication date: 20-Jul-2023
https://dl.acm.org/doi/10.1145/3594735
Show More Cited By

Recommendations

Observationally-induced Effect Monads: Upper and Lower Powerspace Constructions

Alex Simpson has suggested to use an observationally-induced approach towards modelling computational effects in denotational semantics. The principal idea is that a single observation algebra is used for defining the computational type structure. He ...
From corecursive algebras to corecursive monads
CALCO'11: Proceedings of the 4th international conference on Algebra and coalgebra in computer science

An algebra is called corecursive if from every coalgebra a unique coalgebra-to-algebra homomorphism exists into it. We prove that free corecursive algebras are obtained as a coproduct of the final coalgebra (considered as an algebra) and with free ...
Arrows, like Monads, are Monoids

Monads are by now well-established as programming construct in functional languages. Recently, the notion of ''Arrow'' was introduced by Hughes as an extension, not with one, but with two type parameters. At first, these Arrows may look somewhat ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

LFP '90: Proceedings of the 1990 ACM conference on LISP and functional programming

May 1990

348 pages

ISBN:089791368X

DOI:10.1145/91556

Chairman:
Gilles Kahn

Copyright © 1990 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGAI: ACM Special Interest Group on Artificial Intelligence
SIGPLAN: ACM Special Interest Group on Programming Languages
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation
INRIA: Institut Natl de Recherche en Info et en Automatique

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 May 1990

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

LFP90

Sponsor:

LFP90: ACM Conference on Lisp and Functional Programming

June 27 - 29, 1990

Nice, France

Acceptance Rates

Overall Acceptance Rate 30 of 109 submissions, 28%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

334
Total Citations
View Citations
2,998
Total Downloads

Downloads (Last 12 months)450
Downloads (Last 6 weeks)49

Reflects downloads up to 26 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Song YFoo DChin W(2024)Specification and Verification for Unrestricted Algebraic Effects and HandlingProceedings of the ACM on Programming Languages10.1145/36746568:ICFP(909-937)Online publication date: 15-Aug-2024
https://dl.acm.org/doi/10.1145/3674656
Koopman PLubbers M(2023)Strongly-Typed Multi-View Stack-Based ComputationsProceedings of the 25th International Symposium on Principles and Practice of Declarative Programming10.1145/3610612.3610623(1-12)Online publication date: 22-Oct-2023
https://dl.acm.org/doi/10.1145/3610612.3610623
Haselwarter PRivas EVan Muylder AWinterhalter TAbate CSidorenco NHriţcu CMaillard KSpitters B(2023)SSProve: A Foundational Framework for Modular Cryptographic Proofs in CoqACM Transactions on Programming Languages and Systems10.1145/359473545:3(1-61)Online publication date: 20-Jul-2023
https://dl.acm.org/doi/10.1145/3594735
Shaikhha AKelepeshis MGhorbani MDubach CBruening DHardekopf B(2023)Fine-Tuning Data Structures for Query ProcessingProceedings of the 21st ACM/IEEE International Symposium on Code Generation and Optimization10.1145/3579990.3580016(149-161)Online publication date: 17-Feb-2023
https://dl.acm.org/doi/10.1145/3579990.3580016
Dietrich JGalster MLuczak-Roesch M(2023)On Retrofitting Provenance for Transparent and Fair Software - Drivers and Challenges2023 IEEE/ACM International Workshop on Equitable Data & Technology (FairWare)10.1109/FairWare59297.2023.00007(14-21)Online publication date: May-2023
https://doi.org/10.1109/FairWare59297.2023.00007
VANDENBROUCKE ASCHRIJVERS T(2023)Disjunctive Delimited ControlTheory and Practice of Logic Programming10.1017/S1471068423000029(1-22)Online publication date: 11-Apr-2023
https://doi.org/10.1017/S1471068423000029
Oliveira J(2023)Why Adjunctions Matter—A Functional Programmer PerspectiveRecent Trends in Algebraic Development Techniques10.1007/978-3-031-43345-0_2(25-59)Online publication date: 22-Oct-2023
https://doi.org/10.1007/978-3-031-43345-0_2
Dudzik AVeličković PKoyejo SMohamed SAgarwal ABelgrave DCho KOh A(2022)Graph neural networks are dynamic programmersProceedings of the 36th International Conference on Neural Information Processing Systems10.5555/3600270.3601770(20635-20647)Online publication date: 28-Nov-2022
https://dl.acm.org/doi/10.5555/3600270.3601770
Shaikhha AScholz BKameyama Y(2022)Deep Fusion for Efficient Nested Recursive ComputationsProceedings of the 21st ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences10.1145/3564719.3568698(33-44)Online publication date: 29-Nov-2022
https://dl.acm.org/doi/10.1145/3564719.3568698
Hanus MPrott KTeegen F(2022)A Monadic Implementation of Functional Logic ProgramsProceedings of the 24th International Symposium on Principles and Practice of Declarative Programming10.1145/3551357.3551370(1-15)Online publication date: 20-Sep-2022
https://dl.acm.org/doi/10.1145/3551357.3551370
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents