;; tabulate 
(define tabulate (i j)
  (if (> i j)
      '()
      (cons i (tabulate (+ i 1) j))))


;; prime numbers based on sieve of eratosthenes
;; test if first argument divides second
(define divides (m n) 
  (= (mod n m) 0))

(divides 5 10)


;; removes the list l with all multiples of n removed 
(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))))))

(remove-multiples 2 '(2 3 4 5 6 7))

;; sieve 
(define sieve (l) 
  (if (null? l) 
      '()
      (cons (car l) (sieve (remove-multiples (car l) (cdr l))))))

;; prime numbers 
(define primes<= (n)
  (sieve (tabulate 2 n)))


;; insertion sort 

(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)))))

(insertion-sort '(4 3 2 6 8 5))



;; let-binding 
(define foo (a b) 
  (let ((two-a (* 2 a))
	(two-b (* 2 b)))
    (list2 (+ two-a two-b) (- two-a two-b))))
	

(foo 2 3)


;; read about let* and letrec 


;; recursive functions on trees 
;; unlike ML where trees would 
;; be represented as a datatype 
;; in Scheme S-expressions are used for 
;; everything

(val mytree '(A (B C D) (E (F G H) I)))

;; some functions 

(define leaf? (node) (atom? node))
(define left  (node) (cadr node))
(define right (node) (caddr node))
(define label (node) (if (leaf? node) node (car node)))


(define pre-ord (t) 
  (cons 
   (label t) 
   (if (leaf? t) 
       '()
       (append 
	(pre-ord (left t))
	(pre-ord (right t))))))


(pre-ord mytree)

;; lambda: in Impcore (and C) functions are special things
;; that are different from values. They can only be defined 
;; at the top-level 
;; New construct for making functions values 
;; (lambda (x y .. z) e)

((lambda (x y) (+ (* x x) (* y y))) 707 707)

;; define is just sugar for a val binding  
(val det (lambda (x y) (+ (* x x) (* y y))))
(det 5 5)

;; apply n-times 
;; passing functions as arguments
(define apply-n-times (n f x)
  (if (= 0 n) 
      x 
      (apply-n-times (- n 1) f (f x))))


(define twice (n)(* 2 n))
(define square (n) (* n n))

(apply-n-times 2 twice 10)
(apply-n-times 2 square 10)


;; currying - creating functions on the fly 
;; It is critical that you understand how this works 
;; given argument x, add returns a function which 
;; given argument y, returns x+y

(val add (lambda (x) (lambda (y) (+ x y))))
(val add1 (add 1))
(add1 4) 



;; closures 
;; the key to the power of lambda is that 
;; an expression such as (lambda (y) (+ x y)) 
;; can stand for more than one function depending 
;; on what x stands for 

;; to represent a function as a value we need 
;; <lambda expression, environment>  = CLOSURE 



;; !! DIFFERENCE between values and mutable locations 


(val resetable-counter-from 
     (lambda (n)
       (list2 
	(lambda () (set n (+ n 1)))
	(lambda () (set n 0)))))

;; the two lambda's refer to the same n 
;; two different applications of resettable-counter-from 
;; refer to different n

(val step (lambda (ctr) ((car ctr))))
(val reset (lambda (ctr) ((cadr ctr))))

(val hundred (resetable-counter-from 100))
(val twenty  (resetable-counter-from 20))

(step hundred) 
(step twenty) 
(reset hundred) 
(step hundred) 
(step hundred) 
(step twenty) 



;; Higher-order functions 
(define o (f g) (lambda (x) (f (g x))))