The categorical structure of monads is used to structure programs with behaviour that looks and feels like side-effects in purely functional programming languages.
The use of monads appears monolithic. However, it solves two very distinct problems:
IO
monad). In this case, monads are built into the language.Both problems were seen as important in
lazy functional programming by the mid-1980s, but it is likely that problem no 1 preceded problem no 2.
Interestingly, the solution came by solving problem no 2 first. Perhaps one of the first papers that noticed that lists may offer a solution to problem number 2 is [Wadler 1985]. This paper essentially contains the seeds of the "data-flow" of the >>=
(bind) operation of monads.
The hint was taken by [Spivey 1990], which seems to have introduced the Maybe
to write purely functional programs that may throw exceptions. Spivey's work was the first one to notice that both Maybe
and the list functor [-]
are monads.
This approach to lazy, pure functional programming "with simulated effects" was then developed at length by [Wadler 1992]. That paper also contains a lot of early references for the precursors to the monadic style.
Around the same time, [Wadler 1992b] showed how to use monads to write modular definitional interpreters for programming languages with effects, whenever the implementation language is lazy and functional. This 'ties the knot' with Moggi's work, which concentrated on structuring the denotational semantics of languages with effects. A definitional interpreter is a form of "denotational semantics," but implemented in another language instead of mathematics. Thus, structuring an interpreter with monads is exactly the same as Moggi's approach to the semantics of effects.
Please expand.
Wadler, Philip. 1985. ‘How to Replace Failure by a List of Successes a Method for Exception Handling, Backtracking, and Pattern Matching in Lazy Functional Languages’. In Functional Programming Languages and Computer Architecture, edited by Jean-Pierre Jouannaud, 201:113–28. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer Berlin Heidelberg. https://doi.org/10.1007/3-540-15975-4_33.
@inproceedings{wadler_1985,
address = {Berlin, Heidelberg},
series = {Lecture {Notes} in {Computer} {Science}},
title = {How to replace failure by a list of successes a method for exception handling, backtracking, and pattern matching in lazy functional languages},
volume = {201},
doi = {10.1007/3-540-15975-4_33},
booktitle = {Functional {Programming} {Languages} and {Computer} {Architecture}},
publisher = {Springer Berlin Heidelberg},
author = {Wadler, Philip},
editor = {Jouannaud, Jean-Pierre},
year = {1985},
pages = {113--128}
}
Spivey, Mike. 1990. ‘A Functional Theory of Exceptions’. Science of Computer Programming 14 (1): 25–42. https://doi.org/10.1016/0167-6423(90)90056-J.
@article{spivey_1990,
title = {A functional theory of exceptions},
volume = {14},
doi = {10.1016/0167-6423(90)90056-J},
number = {1},
journal = {Science of Computer Programming},
author = {Spivey, Mike},
year = {1990},
pages = {25--42}
}
Wadler, Philip. 1992. ‘Comprehending Monads’. Mathematical Structures in Computer Science 2 (4): 461–93. https://doi.org/10.1017/S0960129500001560. [pdf]
@article{wadler_1992,
title = {Comprehending monads},
volume = {2},
doi = {10.1017/S0960129500001560},
number = {4},
journal = {Mathematical Structures in Computer Science},
author = {Wadler, Philip},
year = {1992},
pages = {461--493}
}
Wadler, Philip. 1992b. ‘The Essence of Functional Programming’. In Proceedings of the 19th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages - POPL ’92. ACM Press. https://doi.org/10.1145/143165.143169. [pdf]
@inproceedings{wadler_1992b,
title = {The essence of functional programming},
doi = {10.1145/143165.143169},
booktitle = {Proceedings of the 19th {ACM} {SIGPLAN}-{SIGACT} symposium on {Principles} of programming languages - {POPL} '92},
publisher = {ACM Press},
author = {Wadler, Philip},
year = {1992}
}