From: Jim Pryor Date: Tue, 5 Oct 2010 03:21:17 +0000 (-0400) Subject: week4 tweaks X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=commitdiff_plain;h=5c53b47bfede98d2274154b7a33039334cfcc4cc week4 tweaks Signed-off-by: Jim Pryor --- diff --git a/week4.mdwn b/week4.mdwn index daa18981..fca995e3 100644 --- a/week4.mdwn +++ b/week4.mdwn @@ -589,14 +589,29 @@ detail](http://okmij.org/ftp/Streams.html#enumerator-stream). > that `5` is the outer/leftmost head of the list. That's not an efficient way > to get the leftmost head. > -> We could improve this by building lists as left folds when implementing them -> as continuation-passing style folds. We'd just replace above: +> We could improve this by building lists as **left folds**. What's that? +> +> Well, the right fold of `f` over a list `[a;b;c;d;e]`, using starting value z, is: +> +> f a (f b (f c (f d (f e z)))) +> +> The left fold on the other hand starts combining `z` with elements from the left. `f z z` is then combined with `b`, and so on: +> +> f (f (f (f (f z a) b) c) d) e +> +> or, if we preferred the arguments to each `f` flipped: +> +> f e (f d (f c (f b (f a z)))) +> +> Recall we implemented v3 lists as their own right-fold functions. We could +> instead implement lists as their own left-fold functions. To do that with our +> v5 lists, we'd replace above: > > let make_list = \h t. \f2 z continue_handler abort_handler. > f2 h z (\z. t f2 z continue_handler abort_handler) abort_handler > -> now `extract_head` should return the leftmost head directly, using its -> `abort_handler`: +> Having done that, now `extract_head` can return the leftmost head +> directly, using its `abort_handler`: > > let extract_head = \lst larger_computation. lst > (\hd sofar continue_handler abort_handler. abort_handler hd)