cps_hints to mdwn
[lambda.git] / hints / cps_hint_2.mdwn
diff --git a/hints/cps_hint_2.mdwn b/hints/cps_hint_2.mdwn
new file mode 100644 (file)
index 0000000..2cdc49a
--- /dev/null
@@ -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.
+
+