; Lisp list functions from Kamin pp. 29-31 translated to Scheme

(set length (lambda (l) (if (null? l) 0 (+ 1 (length (cdr l))))))

(set caar (lambda (l) (car (car l))))

(set cadr (lambda (l) (car (cdr l))))

(set list1 (lambda (x) (cons x '())))

(set list2 (lambda (x y) (cons x (cons y '()))))

(set list3 (lambda (x y z) (cons x (cons y (cons z '())))))

(set or (lambda (x y) (if x x y)))

(set atom? (lambda (x) (or (null? x) (or (number? x) (symbol? x)))))

(set equal (lambda (l1 l2)
    (if (atom? l1) (= l1 l2)
        (if (atom? l2) '()
            (if (equal (car l1) (car l2))
                (equal (cdr l1) (cdr l2))
                '() )))) )


; Lisp insertion sort from Kamin p. 32 translated to Scheme

(set insert (lambda (x l)
    (if (null? l) (list1 x) 
        (if (< x (car l)) (cons x l)
            (cons (car l) (insert x (cdr l)))))) )

(set insertion-sort (lambda (l) 
    (if (null? l) '() 
        (insert (car l) (insertion-sort (cdr l))) )) )

; Prime numbers using the Sieve of Eratosthenes algorithm. 
; (divides m n) tests whether m divides n. (interval-list m n) returns
; the list (m, m+l ... ) and (remove-multiples n l) removes all
; multiples of n from l.

; need to redefine this in a purely functional style!
(set mod (lambda (n m) 
    (begin (set $$ (- n (* (/ n m) m))) 
        (if (< $$ 0) (- 0 $$) $$))))

(set divides (lambda (m n) (= (mod n m) 0)))

(set interval-list (lambda (m n)
  (if (> m n) '() (cons m (interval-list (+ 1 m) n)))))

(set remove-multiples (lambda (n l) 
  (if (null? l) '() 
    (if (divides n (car l))
      (remove-multiples n (cdr l))
      (cons (car l) (remove-multiples n (cdr l)))))))



(set sieve (lambda (l) 
  (if (null? l) '()
    (cons (car l)
      (sieve (remove-multiples (car l) (cdr l)))))))
    
(set primes<= (lambda (n) (sieve (interval-list 2 n))))