From c4a2655a636328b4e3fe183717402a02f1d97a90 Mon Sep 17 00:00:00 2001 From: Jim Pryor Date: Wed, 1 Dec 2010 03:40:41 -0500 Subject: [PATCH] consistently use k for continuations Signed-off-by: Jim Pryor --- from_list_zippers_to_continuations.mdwn | 18 +++++++++--------- manipulating_trees_with_monads.mdwn | 8 ++++---- 2 files changed, 13 insertions(+), 13 deletions(-) diff --git a/from_list_zippers_to_continuations.mdwn b/from_list_zippers_to_continuations.mdwn index 07c34863..da184c51 100644 --- a/from_list_zippers_to_continuations.mdwn +++ b/from_list_zippers_to_continuations.mdwn @@ -144,7 +144,7 @@ This means that we can now represent the unzipped part of our 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: @@ -155,11 +155,11 @@ some small but interesting differences. We've included the orginal | (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)) = match l with - | [] -> 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'] @@ -178,19 +178,19 @@ not be instantiated). 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`. -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 -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: diff --git a/manipulating_trees_with_monads.mdwn b/manipulating_trees_with_monads.mdwn index 379ead54..a05fa259 100644 --- a/manipulating_trees_with_monads.mdwn +++ b/manipulating_trees_with_monads.mdwn @@ -262,25 +262,25 @@ That is, nothing happens. But we can begin to substitute more 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 *) - # 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 *) - # 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 - type ('a -> 'b -> 'c) continuation = ('a -> 'b) -> 'c;; + type ('a -> 'b -> 'k) continuation = ('a -> 'b) -> 'k;; The binary tree monad --------------------- -- 2.11.0