From: jim Date: Thu, 19 Mar 2015 23:01:25 +0000 (-0400) Subject: Clean up examples, stick more consistently to typing conventions X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=commitdiff_plain;h=a00ce3568850c86966ecf4e8ca5d9dd989b6d69a Clean up examples, stick more consistently to typing conventions --- diff --git a/topics/week7_introducing_monads.mdwn b/topics/week7_introducing_monads.mdwn index 8f320140..3b92b61b 100644 --- a/topics/week7_introducing_monads.mdwn +++ b/topics/week7_introducing_monads.mdwn @@ -197,33 +197,33 @@ The Identity monad is favored by mimes. To take a slightly less trivial (and even more useful) example, consider the box type `Î± list`, with the following operations: - mid: Î± -> [Î±] + mid : Î± -> [Î±] mid a = [a] - mcomp: (Î² -> [Î³]) -> (Î± -> [Î²]) -> (Î± -> [Î³]) - mcomp f g a = concat (map f (g a)) - = foldr (\b -> \gs -> (f b) ++ gs) [] (g a) - = [c | b <- g a, c <- f b] + mcomp : (Î² -> [Î³]) -> (Î± -> [Î²]) -> (Î± -> [Î³]) + mcomp k j a = concat (map k (j a)) = List.flatten (List.map k (j a)) + = foldr (\b ks -> (k b) ++ ks) [] (j a) = List.fold_right (fun b ks -> List.append (k b) ks) [] (j a) + = [c | b <- j a, c <- k b] -The last three definitions of `mcomp` are all equivalent, and it is easy to see that they obey the monad laws (see exercises TODO). +In the first two definitions of `mcomp`, we give the definition first in Haskell and then in the equivalent OCaml. The three different definitions of `mcomp` (one for each line) are all equivalent, and it is easy to show that they obey the Monad Laws. (You will do this in the homework.) -In words, `mcomp f g a` feeds the `a` (which has type `Î±`) to `g`, which returns a list of `Î²`s; -each `Î²` in that list is fed to `f`, which returns a list of `Î³`s. The +In words, `mcomp k j a` feeds the `a` (which has type `Î±`) to `j`, which returns a list of `Î²`s; +each `Î²` in that list is fed to `k`, which returns a list of `Î³`s. The final result is the concatenation of those lists of `Î³`s. For example: - let f b = [b, b+1] in - let g a = [a*a, a+a] in - mcomp f g 7 ==> [49, 50, 14, 15] + let j a = [a*a, a+a] in + let k b = [b, b+1] in + mcomp k j 7 ==> [49, 50, 14, 15] -`g 7` produced `[49, 14]`, which after being fed through `f` gave us `[49, 50, 14, 15]`. +`j 7` produced `[49, 14]`, which after being fed through `k` gave us `[49, 50, 14, 15]`. Contrast that to `m\$` (`mapply`, which operates not on two *box-producing functions*, but instead on two *values of a boxed type*, one containing functions to be applied to the values in the other box, via some predefined scheme. Thus: - let gs = [(\a->a*a),(\a->a+a)] in + let js = [(\a->a*a),(\a->a+a)] in let xs = [7, 5] in - mapply gs xs ==> [49, 25, 14, 10] + mapply js xs ==> [49, 25, 14, 10] As we illustrated in class, there are clear patterns shared between lists and option types and trees, so perhaps you can see why people want to identify the general structures. But it probably isn't obvious yet why it would be useful to do so. To a large extent, this will only emerge over the next few classes. But we'll begin to demonstrate the usefulness of these patterns by talking through a simple example, that uses the monadic functions of the Option/Maybe box type.