; 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 use 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)))