hints/cps_hint_3

   1 This function is developed in *The Seasoned Schemer* pp. 84-89. It accepts an atom `a` and a list `lst` and returns `lst` with the leftmost occurrence of `a`, if any, removed. Occurrences of `a` will be found no matter how deeply embedded.
   2
   3         #lang racket
   4
   5         (define (atom? x)
   6           (and (not (pair? x)) (not (null? x))))
   7
   8         (define gamma
   9           (lambda (a lst)
  10             (letrec ([aux (lambda (l k)
  11                             (cond
  12                               [(null? l) (k 'notfound)]
  13                               [(eq? (car l) a) (cdr l)]
  14                               [(atom? (car l)) (cons (car l) (aux (cdr l) k))]
  15                               ; when (car l) exists but isn't an atom, we try to remove a from (car l)
  16                               ; if we succeed we prepend the result to (cdr l) and stop
  17                               [else (let ([car2 (let/cc k2
  18                                                   ; calling k2 with val will bind car2 to val and continue with the (cond ...) block below
  19                                                   (aux (car l) k2))])
  20                                       (cond
  21                                         ; if a wasn't found in (car l) then prepend (car l) to the result of removing a from (cdr l)
  22                                         [(eq? car2 'notfound) (cons (car l) (aux (cdr l) k))]
  23                                         ; else a was found in (car l)
  24                                         [else (cons car2 (cdr l))]))]))]
  25                      [lst2 (let/cc k1
  26                              ; calling k1 with val will bind lst2 to val and continue with the (cond ...) block below
  27                              (aux lst k1))])
  28               (cond
  29                 ; was no atom found in lst?
  30                 [(eq? lst2 'notfound) lst]
  31                 [else lst2]))))
  32
  33         (gamma 'a '(((a b) ()) (c (d ())))) ; ~~> '(((b) ()) (c (d ())))
  34         (gamma 'a '((() (a b) ()) (c (d ())))) ; ~~> '((() (b) ()) (c (d ())))
  35         (gamma 'a '(() (() (a b) ()) (c (d ())))) ; ~~> '(() (() (b) ()) (c (d ())))
  36         (gamma 'c '((() (a b) ()) (c (d ())))) ; ~~> '((() (a b) ()) ((d ())))
  37         (gamma 'c '(() (() (a b) ()) (c (d ())))) ; ~~> '(() (() (a b) ()) ((d ())))
  38         (gamma 'x '((() (a b) ()) (c (d ())))) ; ~~> '((() (a b) ()) (c (d ())))
  39         (gamma 'x '(() (() (a b) ()) (c (d ())))) ; ~~> '(() (() (a b) ()) (c (d ())))
  40