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