Quantifier Functions

; Directly programmed functions. These functions terminate ; if the predicate fails on an element (for-all) or if ; if the predicate holds on an element (there-exists) ; Notice that both functions are tail-recursive. (define (for-all lst p) (cond ((null? lst) #t) ((p (car lst)) (for-all (cdr lst) p)) (else #f))) (define (there-exists lst p) (cond ((null? lst) #f) ((p (car lst)) #t) (else (there-exists (cdr lst) p)))) ; It is easy to program there-exists-1 by use of ; filter - see below. Here is another attempt which makes used of for-all: (define (there-exists-1 lst p) (cond ((null? lst) #f) ((p (car lst)) (for-all (cdr lst) (negate p))) (else (there-exists-1 (cdr lst) p)))) ; Versions of for-all and there-exists programmed with ; mapping and accumulation. These function will traverse the ; whole list twice. This should be avoided, if possible. (define (for-all lst p) (accumulate-right and-fn #t (map p lst))) (define (there-exist lst p) (accumulate-right or-fn #f (map p lst))) (define (there-exists-1 lst p) (= (length (filter p lst)) 1)) ; Here is the stuff necessary for theses functions to work: (define (accumulate-right f init lst) (if (null? lst) init (f (car lst) (accumulate-right f init (cdr lst))))) (define (and-fn x y) (and x y)) ; and is special form - short circuited (define (or-fn x y) (or x y)) ; or is special form - short circuited (define (filter pred lst) (reverse (filter-help pred lst '()))) (define (filter-help pred lst res) (cond ((null? lst) res) ((pred (car lst)) (filter-help pred (cdr lst) (cons (car lst) res))) (else (filter-help pred (cdr lst) res)))) (define (negate p) (lambda (x) (if (p x) #f #t)))