snapshot -> outer_snapshot
[lambda.git] / topics / cps_hint_2.mdwn
1 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.
2
3
4         #lang racket
5         
6         (define (atom? x)
7           (and (not (pair? x)) (not (null? x))))
8         
9         (define beta
10           (lambda (lst)
11             (let/cc k ; calling k with val will immediately return val from the call to beta
12               (letrec ([aux (lambda (l)
13                               (cond
14                                 [(null? l) '()]
15                                 [(atom? (car l)) (k (car l))]
16                                 [else (begin
17                                         ; each of the following lines will evaluate to '() iff no atom was found in the specified part of l
18                                         (aux (car l))
19                                         (aux (cdr l)))]))])
20                 (aux lst)))))
21         
22         (beta '(((a b) ()) (c (d ()))))       ; ~~> 'a
23         (beta '((() (a b) ()) (c (d ()))))    ; ~~> 'a
24         (beta '(() (() (a b) ()) (c (d ())))) ; ~~> 'a
25         (beta '(() (() ())))                  ; no leftmost atom, returns '()
26
27 This function could also be written like this:
28
29         (define leftmost
30           (lambda (l)
31             (cond
32               [(null? l) '()]
33               [(atom? (car l)) (car l)]
34               [else (let ([found (leftmost (car l))])
35                       (cond
36                         ; here we check whether the recursive call found an atom in (car l)
37                         [(atom? found) found]
38                         ; if not, we search for an atom in (cdr l)
39                         [else (leftmost (cdr l))]))])))
40
41 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.
42
43