X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=week7.mdwn;h=c81ff1253ceca9ee8cb724163cee5e139bcfe234;hp=351a6d953fac41901c96823c8bf31829b51e6733;hb=1713e01a3a0982e0f8fc68ed93035cea6ca8f46e;hpb=f5b5782cffbfacfdedcd59af0780eb981a564b0c;ds=sidebyside diff --git a/week7.mdwn b/week7.mdwn index 351a6d95..c81ff125 100644 --- a/week7.mdwn +++ b/week7.mdwn @@ -105,7 +105,7 @@ that provides at least the following three elements: 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`. @@ -125,14 +125,8 @@ that provides at least the following three elements: 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 = - -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 @@ -160,7 +154,7 @@ Similarly: 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 @@ -219,16 +213,23 @@ them from hurting the people that use them or themselves. 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 = # let unit x = Some x;; val unit : 'a -> 'a option = + # let ( * ) u f = match u with None -> None | Some x -> f x;; + val ( * ) : 'a option -> ('a -> 'b option) -> 'b option = + + 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 = # divide 6 2;; - : int option = Some 3 # unit 2 * divide 6;; @@ -239,10 +240,6 @@ them from hurting the people that use them or themselves. # 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: @@ -268,7 +265,7 @@ is `*`, pronounced "bind") is an infix operator, so we write # 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` @@ -305,24 +302,26 @@ See also . 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. + * [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. + + +* [Daniel Friedman. A Schemer's View of Monads](/schemersviewofmonads.ps): from 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: @@ -354,7 +353,7 @@ also define a lift operation for binary functions: # 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 = -`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`! @@ -379,7 +378,7 @@ Another general monad operation is called `ap` in Haskell---short for "apply." ( 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 @@ -396,11 +395,12 @@ That is the `join` operation. 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)