; sethi418.s *)
; see ML Exercises, p. 380 *)
                             
; 10.4 = 9.2 

;;;;;;;;;;;;;;;;;;;;; a
;fun n2a [] = []
; |  n2a [x] = [x]
; |  n2a (a::y) = if a = (hd y) then n2a(y)
;                 else a::n2a(y);
(define (n4a L)
        (cond ((null? L) nil)
              ((null? (cdr L)) L)
              (else
                     (if (eq? (car L) (car (cdr L)))
                         (n4a (cdr L))
                         (cons (car L) (n4a (cdr L))) ))))

;;;;;;;;;;;;;;;;;;;;;; b
;fun remrep(k,x) = if x = nil then []
;                  else if k = (hd x) then remrep(k,tl x)
;                  else x;
;fun n2b [] = []
; |  n2b [x] = [x]
; |  n2b (a::y) = if a = (hd y) then n2b(remrep(a,y))
;                 else a::n2b(y);
(define (remrep k x)
        (cond ((null? x) nil)
              ((eq? k (car x)) (remrep k (cdr x)))
              (else x)))
(define (n4b L)
        (cond ((null? L) nil)
              ((null? (cdr L)) L)
              (else (if (eq? (car L) (car (cdr L)))
                    (n4b (remrep (car L) (cdr L)))
                    (cons (car L) (n4b (cdr L)))))))

;;;;;;;;;;;;;;;;;;;;;;; c
;fun n2c [] = []
; |  n2c [x] = []
; |  n2c (a::y) = if a <> (hd y) then n2c(y)
;                 else a::n2c(remrep(a,y));
(define (n4c L)
        (cond ((null? L) nil)
              ((null? (cdr L)) nil)
              (else (if (eq? (car L) (car (cdr L)))
                    (cons (car L) (n4c (remrep (car L) (cdr L))))
                    (n4c (cdr L))))))

;;;;;;;;;;;;;;;;;;;;;;; d
;fun count [] = 0
; |  count [x] = 1
; |  count (a::y) = if a <> (hd y) then 1
;                   else 1 + count(y);
;fun n2d [] = []
; |  n2d (a::y) = (count(a::y),a) :: (n2d (remrep(a,a::y)));
(define (count L)
        (cond ((null? L) 0)
              ((null? (cdr L)) 1)
              (else (if (not (eq? (car L) (car (cdr L))))
                    1
                    (+ 1 (count (cdr L)))))))
(define (n4d L)
        (cond ((null? L) nil)
              (else (cons (list (count L) (car L))
                          (n4d (remrep (car L) L))))))


; 10.5 = 9.3 

;;;;;;;;;;;;;;;;;;;;; a
;fun addallaux(x,a) = if x = nil then a
;                     else addallaux(tl x, a + hd x);
;fun addall(x) = addallaux(x,0);
(define (addallaux L A)
        (if (null? L) A (addallaux (cdr L) (+ A (car L)))))
(define (addall L) (addallaux L 0))

;;;;;;;;;;;;;;;;;;;;; b
;fun mulallaux(x,a) = if x = nil then a
;                     else mulallaux(tl x, a * hd x);
;fun mulall(x) = mulallaux(x,1);
(define (mulallaux L A)
        (if (null? L) A (mulallaux (cdr L) (* A (car L)))))
(define (mulall L) (mulallaux L 1))

;;;;;;;;;;;;;;;;;;;;; c
;fun facaux(x,a) = if x = 0 then a else facaux(x-1, a*x);
;fun fac(x) = facaux(x,1);
(define (facaux x A)
        (if (eq? x 0) A (facaux (- x 1) (* A x))))
(define (fac x) (facaux x 1))



;(* Fibonacci Numbers *) ;;; Only up to 45 for xscheme

;fun fib n = if n <= 1 then 1
;            else fib(n-1) + fib(n-2);

;fun fibaux(n,a,b) = if n <= 1 then a
;                    else fibaux(n-1,a+b,a);

;fun fibonacci n = fibaux(n,1,1);

(define (fib n)
        (if (<= n 1) 1 (+ (fib (- n 1)) (fib (- n 2)))))

(define (fibaux N A B)
        (if (<= n 1) A (fibaux (- N 1) (+ A B) A)))
(define (fibonacci N) (fibaux N 1 1))