The guts of the definition of the `bind` operation amount to
specifying how to unbox the monadic value `u`. In the `bind`
- opertor for the option monad, we unboxed the monadic value by
+ operator for the option monad, we unboxed the monadic value by
matching it with the pattern `Some x`---whenever `u`
happened to be a box containing an integer `x`, this allowed us to
get our hands on that `x` and feed it to `f`.
useful way.
So the "option/maybe monad" consists of the polymorphic `option` type, the
-`unit`/return function, and the `bind` function. With the option monad, we can
-think of the "safe division" operation:
+`unit`/return function, and the `bind` function.
- # let safe_divide num den = if 0 = den then None else Some (num/den);;
- val safe_divide : int -> int -> int option = <fun>
-
-as basically a function from two integers to an integer, except with
-this little bit of option plumbing on the side.
A note on notation: Haskell uses the infix operator `>>=` to stand
for `bind`. Chris really hates that symbol. Following Wadler, he prefers to
is shorthand for `u >>= (\x -> v >>= (\y -> f x y))`, that is, `bind u (fun x
-> bind v (fun y -> f x y))`. Those who did last week's homework may recognize
-this.
+this last expression.
(Note that the above "do" notation comes from Haskell. We're mentioning it here
because you're likely to see it when reading about monads. It won't work in
type, we have `(unit x) * f == f x`. For instance, `unit` is itself
a function of type `'a -> 'a m`, so we can use it for `f`:
- # let ( * ) u f = match u with None -> None | Some x -> f x;;
- val ( * ) : 'a option -> ('a -> 'b option) -> 'b option = <fun>
# let unit x = Some x;;
val unit : 'a -> 'a option = <fun>
+ # let ( * ) u f = match u with None -> None | Some x -> f x;;
+ val ( * ) : 'a option -> ('a -> 'b option) -> 'b option = <fun>
+
+ The parentheses is the magic for telling OCaml that the
+ function to be defined (in this case, the name of the function
+ is `*`, pronounced "bind") is an infix operator, so we write
+ `u * f` or `( * ) u f` instead of `* u f`. Now:
# unit 2;;
- : int option = Some 2
# unit 2 * unit;;
- : int option = Some 2
+ # let divide x y = if 0 = y then None else Some (x/y);;
+ val divide : int -> int -> int option = <fun>
# divide 6 2;;
- : int option = Some 3
# unit 2 * divide 6;;
# unit 0 * divide 6;;
- : int option = None
-The parentheses is the magic for telling OCaml that the
-function to be defined (in this case, the name of the function
-is `*`, pronounced "bind") is an infix operator, so we write
-`u * f` or `( * ) u f` instead of `* u f`.
* **Associativity: bind obeys a kind of associativity**. Like this:
# Some 3 * (fun x -> divide 2 x * divide 6);;
- : int option = None
-Of course, associativity must hold for arbitrary functions of
+Of course, associativity must hold for *arbitrary* functions of
type `'a -> 'a m`, where `m` is the monad type. It's easy to
convince yourself that the `bind` operation for the option monad
obeys associativity by dividing the inputs into cases: if `u`
Here are some papers that introduced monads into functional programming:
-* [Eugenio Moggi, Notions of Computation and Monads](http://www.disi.unige.it/person/MoggiE/ftp/ic91.pdf): Information and Computation 93 (1).
+* [Eugenio Moggi, Notions of Computation and Monads](http://www.disi.unige.it/person/MoggiE/ftp/ic91.pdf): Information and Computation 93 (1) 1991.
* [Philip Wadler. Monads for Functional Programming](http://homepages.inf.ed.ac.uk/wadler/papers/marktoberdorf/baastad.pdf):
in M. Broy, editor, *Marktoberdorf Summer School on Program Design Calculi*, Springer Verlag, NATO ASI Series F: Computer and systems sciences, Volume 118, August 1992. Also in J. Jeuring and E. Meijer, editors, *Advanced Functional Programming*, Springer Verlag, LNCS 925, 1995. Some errata fixed August 2001.
- The use of monads to structure functional programs is described. Monads provide a convenient framework for simulating effects found in other languages, such as global state, exception handling, output, or non-determinism. Three case studies are looked at in detail: how monads ease the modification of a simple evaluator; how monads act as the basis of a datatype of arrays subject to in-place update; and how monads can be used to build parsers.
+<!-- The use of monads to structure functional programs is described. Monads provide a convenient framework for simulating effects found in other languages, such as global state, exception handling, output, or non-determinism. Three case studies are looked at in detail: how monads ease the modification of a simple evaluator; how monads act as the basis of a datatype of arrays subject to in-place update; and how monads can be used to build parsers.-->
* [Philip Wadler. The essence of functional programming](http://homepages.inf.ed.ac.uk/wadler/papers/essence/essence.ps):
invited talk, *19'th Symposium on Principles of Programming Languages*, ACM Press, Albuquerque, January 1992.
- This paper explores the use monads to structure functional programs. No prior knowledge of monads or category theory is required.
+<!-- This paper explores the use monads to structure functional programs. No prior knowledge of monads or category theory is required.
Monads increase the ease with which programs may be modified. They can mimic the effect of impure features such as exceptions, state, and continuations; and also provide effects not easily achieved with such features. The types of a program reflect which effects occur.
- The first section is an extended example of the use of monads. A simple interpreter is modified to support various extra features: error messages, state, output, and non-deterministic choice. The second section describes the relation between monads and continuation-passing style. The third section sketches how monads are used in a compiler for Haskell that is written in Haskell.
+ The first section is an extended example of the use of monads. A simple interpreter is modified to support various extra features: error messages, state, output, and non-deterministic choice. The second section describes the relation between monads and continuation-passing style. The third section sketches how monads are used in a compiler for Haskell that is written in Haskell.-->
+
+* [Daniel Friedman. A Schemer's View of Monads](/schemersviewofmonads.ps): from <https://www.cs.indiana.edu/cgi-pub/c311/doku.php?id=home> but hosted the link above is to a local copy.
There's a long list of monad tutorials on the [[Offsite Reading]] page. Skimming the titles makes me laugh.
In the presentation we gave above---which follows the functional programming conventions---we took `unit`/return and `bind` as the primitive operations. From these a number of other general monad operations can be derived. It's also possible to take some of the others as primitive. The [Monads in Category
Theory](/advanced_notes/monads_in_category_theory) notes do so, for example.
-Here are some of the specifics. You don't have to master these; they're collected here for your reference.
+Here are some of the other general monad operations. You don't have to master these; they're collected here for your reference.
You may sometimes see:
# let lift2 g = fun u v -> bind u (fun x -> bind v (fun y -> Some (g x y)));;
val lift2 : ('a -> 'b -> 'c) -> 'a option -> 'b option -> 'c option = <fun>
-`lift (+)` will now be a function from `int option`s and `int option`s to `int option`s. This should look familiar to those who did the homework.
+`lift2 (+)` will now be a function from `int option`s and `int option`s to `int option`s. This should look familiar to those who did the homework.
The `lift` operation (just `lift`, not `lift2`) is sometimes also called the `map` operation. (In Haskell, they say `fmap` or `<$>`.) And indeed when we're working with the list monad, `lift f` is exactly `List.map f`!
and so on. Here are the laws that any `ap` operation can be relied on to satisfy:
ap (unit id) u = u
- ap (ap (ap (return compose) u) v) w = ap u (ap v w)
+ ap (ap (ap (unit compose) u) v) w = ap u (ap v w)
ap (unit f) (unit x) = unit (f x)
ap u (unit x) = ap (unit (fun f -> f x)) u
All of these operations can be defined in terms of `bind` and `unit`; or alternatively, some of them can be taken as primitive and `bind` can be defined in terms of them. Here are various interdefinitions:
+ lift f u = u >>= compose unit f
lift f u = ap (unit f) u
+ lift2 f u v = u >>= (fun x -> v >>= (fun y -> unit (f x y)))
lift2 f u v = ap (lift f u) v = ap (ap (unit f) u) v
+ ap u v = u >>= (fun f -> lift f v)
ap u v = lift2 id u v
- lift f u = u >>= compose unit f
- lift f u = ap (unit f) u
join m2 = m2 >>= id
u >>= f = join (lift f u)
u >> v = u >>= (fun _ -> v)