; Lisp list functions from Kamin pp. 29-31

(define length (l) (if (null? l) 0 (+ 1 (length (cdr l)))))

(define caar (l) (car (car l)))

(define cadr (l) (car (cdr l)))

(define list1 (x) (cons x '()))

(define list2 (x y) (cons x (cons y '())))

(define list3 (x y z) (cons x (cons y (cons z '()))))

(define or (x y) (if x x y))

(define atom? (x) (or (null? x) (or (number? x) (symbol? x))))

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


; Insertion sort from Kamin p. 32

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

(define insertion-sort(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!
(define mod (n m) 
    (begin (set $$ (- n (* (/ n m) m))) 
        (if (< $$ 0) (- 0 $$) $$)))

(define divides (m n) (= (mod n m) 0))

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

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

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