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.