Signed-off-by: Jim Pryor <profjim@jimpryor.net>
zipper---the part we've already unzipped---as a continuation: a function
describing how to finish building a list. We'll write a new
function, `tc` (for task with continuations), that will take an input
zipper---the part we've already unzipped---as a continuation: a function
describing how to finish building a list. We'll write a new
function, `tc` (for task with continuations), that will take an input
-list (not a zipper!) and a continuation and return a processed list.
+list (not a zipper!) and a continuation `k` (it's conventional to use `k` for continuation variables) and return a processed list.
The structure and the behavior will follow that of `tz` above, with
some small but interesting differences. We've included the orginal
`tz` to facilitate detailed comparison:
The structure and the behavior will follow that of `tz` above, with
some small but interesting differences. We've included the orginal
`tz` to facilitate detailed comparison:
| (unzipped, 'S'::zipped) -> tz ((List.append unzipped unzipped), zipped)
| (unzipped, target::zipped) -> tz (target::unzipped, zipped);; (* Pull zipper *)
| (unzipped, 'S'::zipped) -> tz ((List.append unzipped unzipped), zipped)
| (unzipped, target::zipped) -> tz (target::unzipped, zipped);; (* Pull zipper *)
- let rec tc (l: char list) (c: (char list) -> (char list)) =
+ let rec tc (l: char list) (k: (char list) -> (char list)) =
- | [] -> List.rev (c [])
- | 'S'::zipped -> tc zipped (fun tail -> c (c tail))
- | target::zipped -> tc zipped (fun tail -> target::(c tail));;
+ | [] -> List.rev (k [])
+ | 'S'::zipped -> tc zipped (fun tail -> k (k tail))
+ | target::zipped -> tc zipped (fun tail -> target::(k tail));;
# tc ['a'; 'b'; 'S'; 'd'] (fun tail -> tail);;
- : char list = ['a'; 'b'; 'a'; 'b']
# tc ['a'; 'b'; 'S'; 'd'] (fun tail -> tail);;
- : char list = ['a'; 'b'; 'a'; 'b']
I have not called the functional argument `unzipped`, although that is
what the parallel would suggest. The reason is that `unzipped` is a
I have not called the functional argument `unzipped`, although that is
what the parallel would suggest. The reason is that `unzipped` is a
-list, but `c` is a function. That's the most crucial difference, the
+list, but `k` is a function. That's the most crucial difference, the
point of the excercise, and it should be emphasized. For instance,
you can see this difference in the fact that in `tz`, we have to glue
together the two instances of `unzipped` with an explicit (and
relatively inefficient) `List.append`.
point of the excercise, and it should be emphasized. For instance,
you can see this difference in the fact that in `tz`, we have to glue
together the two instances of `unzipped` with an explicit (and
relatively inefficient) `List.append`.
-In the `tc` version of the task, we simply compose `c` with itself:
-`c o c = fun tail -> c (c tail)`.
+In the `tc` version of the task, we simply compose `k` with itself:
+`k o k = fun tail -> k (k tail)`.
A call `tc ['a'; 'b'; 'S'; 'd']` yields a partially-applied function; it still waits for another argument, a continuation of type `char list -> char list`. We have to give it an "initial continuation" to get started. Here we supply *the identity function* as the initial continuation. Why did we choose that? Well, if
you have already constructed the initial list `"abSd"`, what's the desired continuation? What's the next step in the recipe to produce the desired result, i.e, the very same list, `"abSd"`? Clearly, the identity function.
A good way to test your understanding is to figure out what the
A call `tc ['a'; 'b'; 'S'; 'd']` yields a partially-applied function; it still waits for another argument, a continuation of type `char list -> char list`. We have to give it an "initial continuation" to get started. Here we supply *the identity function* as the initial continuation. Why did we choose that? Well, if
you have already constructed the initial list `"abSd"`, what's the desired continuation? What's the next step in the recipe to produce the desired result, i.e, the very same list, `"abSd"`? Clearly, the identity function.
A good way to test your understanding is to figure out what the
-continuation function `c` must be at the point in the computation when
+continuation function `k` must be at the point in the computation when
`tc` is called with the first argument `"Sd"`. Two choices: is it
`fun tail -> 'a'::'b'::tail`, or it is `fun tail -> 'b'::'a'::tail`? The way to see if
you're right is to execute the following command and see what happens:
`tc` is called with the first argument `"Sd"`. Two choices: is it
`fun tail -> 'a'::'b'::tail`, or it is `fun tail -> 'b'::'a'::tail`? The way to see if
you're right is to execute the following command and see what happens:
interesting functions for the first argument of `treemonadizer`:
(* Simulating the tree reader: distributing a operation over the leaves *)
interesting functions for the first argument of `treemonadizer`:
(* Simulating the tree reader: distributing a operation over the leaves *)
- # treemonadizer (fun a c -> c (square a)) t1 (fun i -> i);;
+ # treemonadizer (fun a k -> k (square a)) t1 (fun i -> i);;
- : int tree =
Node (Node (Leaf 4, Leaf 9), Node (Leaf 25, Node (Leaf 49, Leaf 121)))
(* Simulating the int list tree list *)
- : int tree =
Node (Node (Leaf 4, Leaf 9), Node (Leaf 25, Node (Leaf 49, Leaf 121)))
(* Simulating the int list tree list *)
- # treemonadizer (fun a c -> c [a; square a]) t1 (fun i -> i);;
+ # treemonadizer (fun a k -> k [a; square a]) t1 (fun i -> i);;
- : int list tree =
Node
(Node (Leaf [2; 4], Leaf [3; 9]),
Node (Leaf [5; 25], Node (Leaf [7; 49], Leaf [11; 121])))
(* Counting leaves *)
- : int list tree =
Node
(Node (Leaf [2; 4], Leaf [3; 9]),
Node (Leaf [5; 25], Node (Leaf [7; 49], Leaf [11; 121])))
(* Counting leaves *)
- # treemonadizer (fun a c -> 1 + c a) t1 (fun i -> 0);;
+ # treemonadizer (fun a k -> 1 + k a) t1 (fun i -> 0);;
- : int = 5
We could simulate the tree state example too, but it would require
generalizing the type of the continuation monad to
- : int = 5
We could simulate the tree state example too, but it would require
generalizing the type of the continuation monad to
- type ('a -> 'b -> 'c) continuation = ('a -> 'b) -> 'c;;
+ type ('a -> 'b -> 'k) continuation = ('a -> 'b) -> 'k;;
The binary tree monad
---------------------
The binary tree monad
---------------------