author jim Thu, 19 Mar 2015 23:01:25 +0000 (19:01 -0400) committer Linux User Thu, 19 Mar 2015 23:01:25 +0000 (19:01 -0400)

index 8f32014..3b92b61 100644 (file)
@@ -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:

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]

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:

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:

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
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.

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.