lists-monad tweaks

[lambda.git] / list_monad_as_continuation_monad.mdwn

diff --git a/list_monad_as_continuation_monad.mdwn b/list_monad_as_continuation_monad.mdwn
index d2136db..970a587 100644 (file)
--- a/list_monad_as_continuation_monad.mdwn
+++ b/list_monad_as_continuation_monad.mdwn
@@ -218,15 +218,15 @@ paragraph much easier to follow.]
 As usual, we need to unpack the `u` box.  Examine the type of `u`.
 This time, `u` will only deliver up its contents if we give `u` an
 argument that is a function expecting an `'a` and a `'b`. `u` will
 As usual, we need to unpack the `u` box.  Examine the type of `u`.
 This time, `u` will only deliver up its contents if we give `u` an
 argument that is a function expecting an `'a` and a `'b`. `u` will

-fold that function over its type `'a` members, and that's how we'll get the `'a`s we need. Thus:
+fold that function over its type `'a` members, and that's where we can get at the `'a`s we need. Thus:

 
        ... u (fun (a : 'a) (b : 'b) -> ... f a ... ) ...
 
 
        ... u (fun (a : 'a) (b : 'b) -> ... f a ... ) ...
 

-In order for `u` to have the kind of argument it needs, the `... (f a) ...` has to evaluate to a result of type `'b`. The easiest way to do this is to collapse (or "unify") the types `'b` and `'d`, with the result that `f a` will have type `('c -> 'b -> 'b) -> 'b -> 'b`. Let's postulate an argument `k` of type `('c -> 'b -> 'b)` and supply it to `(f a)`:
+In order for `u` to have the kind of argument it needs, the `... f a ...` has to evaluate to a result of type `'b`. The easiest way to do this is to collapse (or "unify") the types `'b` and `'d`, with the result that `f a` will have type `('c -> 'b -> 'b) -> 'b -> 'b`. Let's postulate an argument `k` of type `('c -> 'b -> 'b)` and supply it to `(f a)`:

 
        ... u (fun (a : 'a) (b : 'b) -> ... f a k ... ) ...
 
 
        ... u (fun (a : 'a) (b : 'b) -> ... f a k ... ) ...
 

-Now we have an argument `b` of type `'b`, so we can supply that to `(f a) k`, getting a result of type `'b`, as we need:
+Now the function we're supplying to `u` also receives an argument `b` of type `'b`, so we can supply that to `f a k`, getting a result of type `'b`, as we need:

 
        ... u (fun (a : 'a) (b : 'b) -> f a k b) ...
 
 
        ... u (fun (a : 'a) (b : 'b) -> f a k b) ...
 


@@ -251,8 +251,8 @@ Now let's think about what this does. It's a wrapper around `u`. In order to beh
 
 Suppose we have a list' whose contents are `[1; 2; 4; 8]`---that is, our list' will be `fun f z -> f 1 (f 2 (f 4 (f 8 z)))`. We call that list' `u`. Suppose we also have a function `f` that for each `int` we give it, gives back a list of the divisors of that `int` that are greater than 1. Intuitively, then, binding `u` to `f` should give us:
 
 
 Suppose we have a list' whose contents are `[1; 2; 4; 8]`---that is, our list' will be `fun f z -> f 1 (f 2 (f 4 (f 8 z)))`. We call that list' `u`. Suppose we also have a function `f` that for each `int` we give it, gives back a list of the divisors of that `int` that are greater than 1. Intuitively, then, binding `u` to `f` should give us:
 

-       concat (map f u) =
-       concat [[]; [2]; [2; 4]; [2; 4; 8]] =
+       List.concat (List.map f u) =
+       List.concat [[]; [2]; [2; 4]; [2; 4; 8]] =

        [2; 2; 4; 2; 4; 8]
 
 Or rather, it should give us a list' version of that, which takes a function `k` and value `z` as arguments, and returns the right fold of `k` and `z` over those elements. What does our formula
        [2; 2; 4; 2; 4; 8]
 
 Or rather, it should give us a list' version of that, which takes a function `k` and value `z` as arguments, and returns the right fold of `k` and `z` over those elements. What does our formula


@@ -271,18 +271,18 @@ do? Well, for each element `a` in `u`, it applies `f` to that `a`, getting one o
 So if, for example, we let `k` be `+` and `z` be `0`, then the computation would proceed:
 
        0 ==>
 So if, for example, we let `k` be `+` and `z` be `0`, then the computation would proceed:
 
        0 ==>

-       right-fold + and 0 over [2; 4; 8] = ((2+4+8+0) ==>
-       right-fold + and 2+4+8+0 over [2; 4] = 2+4+(2+4+8+0) ==>
-       right-fold + and 2+4+2+4+8+0 over [2] = 2+(2+4+(2+4+8+0)) ==>
-       right-fold + and 2+2+4+2+4+8+0 over [] = 2+(2+4+(2+4+8+0))
+       right-fold + and 0 over [2; 4; 8] = 2+4+8+(0) ==>
+       right-fold + and 2+4+8+0 over [2; 4] = 2+4+(2+4+8+(0)) ==>
+       right-fold + and 2+4+2+4+8+0 over [2] = 2+(2+4+(2+4+8+(0))) ==>
+       right-fold + and 2+2+4+2+4+8+0 over [] = 2+(2+4+(2+4+8+(0)))

 
 which indeed is the result of right-folding + and 0 over `[2; 2; 4; 2; 4; 8]`. If you trace through how this works, you should be able to persuade yourself that our formula:
 
        fun k z -> u (fun a b -> f a k b) z
 
 
 which indeed is the result of right-folding + and 0 over `[2; 2; 4; 2; 4; 8]`. If you trace through how this works, you should be able to persuade yourself that our formula:
 
        fun k z -> u (fun a b -> f a k b) z
 

-will deliver just the same folds, for arbitrary choices of `k` and `z` (with the right types), and arbitrary list's `u` and appropriately-typed `f`s, as
+will deliver just the same folds, for arbitrary choices of `k` and `z` (with the right types), and arbitrary `list'`s `u` and appropriately-typed `f`s, as

 
 

-       fun k z -> List.fold_right k (concat (map f u)) z
+       fun k z -> List.fold_right k (List.concat (List.map f u)) z

 
 would.
 
 
 would.