X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?a=blobdiff_plain;f=topics%2Fcps_hint_2.mdwn;fp=topics%2Fcps_hint_2.mdwn;h=d948a28001349e9e40a4983bbdca61b0a0a7fe77;hb=fac1570c5e308143c929a1a0c686d4a45ccaae61;hp=0000000000000000000000000000000000000000;hpb=3a2824d682c7c6860c6487b7dfcbb3b0ce0a5c56;p=lambda.git diff --git a/topics/cps_hint_2.mdwn b/topics/cps_hint_2.mdwn new file mode 100644 index 00000000..d948a280 --- /dev/null +++ b/topics/cps_hint_2.mdwn @@ -0,0 +1,43 @@ +This function is developed in *The Seasoned Schemer* pp. 76-83. It accepts a list `lst` and returns the leftmost atom in it, even if that atom is embedded several levels deep. Any empty lists preceding the leftmost atom are ignored. + + + #lang racket + + (define (atom? x) + (and (not (pair? x)) (not (null? x)))) + + (define beta + (lambda (lst) + (let/cc k ; calling k with val will immediately return val from the call to beta + (letrec ([aux (lambda (l) + (cond + [(null? l) '()] + [(atom? (car l)) (k (car l))] + [else (begin + ; each of the following lines will evaluate to '() iff no atom was found in the specified part of l + (aux (car l)) + (aux (cdr l)))]))]) + (aux lst))))) + + (beta '(((a b) ()) (c (d ())))) ; ~~> 'a + (beta '((() (a b) ()) (c (d ())))) ; ~~> 'a + (beta '(() (() (a b) ()) (c (d ())))) ; ~~> 'a + (beta '(() (() ()))) ; no leftmost atom, returns '() + +This function could also be written like this: + + (define leftmost + (lambda (l) + (cond + [(null? l) '()] + [(atom? (car l)) (car l)] + [else (let ([found (leftmost (car l))]) + (cond + ; here we check whether the recursive call found an atom in (car l) + [(atom? found) found] + ; if not, we search for an atom in (cdr l) + [else (leftmost (cdr l))]))]))) + +But in this version, when an atom is found, it is returned back the chain of recursive calls, one by one. The previous version, on the other hand, uses a captured continuation `k` to return the atom immediately upon finding it. + +