Comprehending monads

Comprehending monads

1992 | Philip Wadler
This paper presents a new method for structuring pure programs that mimic impure features. The method generalizes list comprehensions to an arbitrary monad, allowing programs that manipulate state, handle exceptions, parse text, or invoke continuations to be expressed concisely in a pure functional language. It also presents a new solution to the problem of destructive array update, using two abstract data types with ten operations between them. The solution ensures that array updates can be implemented safely by overwriting, without requiring additional checks or restrictions. The paper introduces the concept of monad comprehensions, which provide a pleasant syntax for expressing programs structured in this way. It also discusses the use of monads to model various features in functional languages, including exceptions, parsers, and non-determinism. The paper shows how monads can be used to translate lambda-calculus into an arbitrary monad, and how this can be used to transform languages with state, exceptions, or continuations into a pure functional language. The paper also discusses the use of monads in the Glasgow Haskell compiler, and the relationship between monads and continuation-passing style. It presents two applications of the monad approach: one is to derive call-by-value and call-by-name interpretations for a simple non-deterministic language, and the other is to apply the call-by-value scheme in the monad of continuations, resulting in the familiar continuation-passing style transformation. The paper concludes by discussing the broader implications of the monad approach, including its ability to clarify and unify previous proposals for incorporating various features into functional languages. It also highlights the importance of types in indicating what parts of a program may have what sorts of effects, and the role of monads in providing a framework for structuring programs that manipulate state, handle exceptions, and perform other impure operations.This paper presents a new method for structuring pure programs that mimic impure features. The method generalizes list comprehensions to an arbitrary monad, allowing programs that manipulate state, handle exceptions, parse text, or invoke continuations to be expressed concisely in a pure functional language. It also presents a new solution to the problem of destructive array update, using two abstract data types with ten operations between them. The solution ensures that array updates can be implemented safely by overwriting, without requiring additional checks or restrictions. The paper introduces the concept of monad comprehensions, which provide a pleasant syntax for expressing programs structured in this way. It also discusses the use of monads to model various features in functional languages, including exceptions, parsers, and non-determinism. The paper shows how monads can be used to translate lambda-calculus into an arbitrary monad, and how this can be used to transform languages with state, exceptions, or continuations into a pure functional language. The paper also discusses the use of monads in the Glasgow Haskell compiler, and the relationship between monads and continuation-passing style. It presents two applications of the monad approach: one is to derive call-by-value and call-by-name interpretations for a simple non-deterministic language, and the other is to apply the call-by-value scheme in the monad of continuations, resulting in the familiar continuation-passing style transformation. The paper concludes by discussing the broader implications of the monad approach, including its ability to clarify and unify previous proposals for incorporating various features into functional languages. It also highlights the importance of types in indicating what parts of a program may have what sorts of effects, and the role of monads in providing a framework for structuring programs that manipulate state, handle exceptions, and perform other impure operations.
Reach us at info@study.space