;; File: sampler.scm
;; Author: Robert Keller
;; This is intended to provide a basic sampler for how to do things in Scheme.

;; First load the tester, which defines tester and test.
;; You must have tester.scm in your local directory, or provide a path to it.

(load "tester.scm")


;; Simple arithmetic expressions with functions + * - /
;; Note that (- 8) represents unary minus, i.e. negation

(test (+ 2 (* 3 4) (/ 5 (- 6 7)) (- 8)) 1)


;; More functions: min, max, and modulo

(test (min 3 (max 4 5 6) 7) 3)

(test (modulo 15 4) 3)


;; Defining simple arithmetic functions

;; A function to convert Farenheit temperature to Celsius
;; Note that 5/9 is not an application of division, but
;; rather is a rational numeral.

;; Note that Scheme is case-sensitive.

(define (Farenheit->Celsius temp) (* 5/9 (- temp 32)))

(test (Farenheit->Celsius 212) 100)


;; A function to convert Celsius to farenheit

(define (Celsius->Farenheit temp) (+ 32 (* 9/5 temp)))

(test (Farenheit->Celsius 32) 0)

(test (Farenheit->Celsius (Celsius->Farenheit 100)) 100)

(test (Celsius->Farenheit (Farenheit->Celsius 212)) 212)


;; Simple list processing functions

;; list is a function of an arbitrary number of arguments
;; It creates a list from those arguments in the order given

(test (list 1 2 3 4) '(1 2 3 4))


;; first returns the first element of a list.

(test (first (list 1 2 3 4)) 1)


;; rest returns a list of everything but the first element of a list.

(test (rest (list 1 2 3 4)) '(2 3 4))

(test (first (rest (list 1 2 3 4))) 2)

(test (rest (rest (list 1 2 3 4))) '(3 4))


;; list-ref finds the position of the second argument in the first argument list
;; using equal? as a comparison function.

(test (list-ref (list 1 2 3 4) 2) 3)


;; cons creates a new list from an existing list and a first element.

(test (cons 0 (list 1 2 3 4)) '(0 1 2 3 4))


;; Note that cons and list are quite different

(test (list 0 (list 1 2 3 4)) '(0 (1 2 3 4)))

(test (cons (list 0) (list 1 2 3 4)) '((0) 1 2 3 4))


;; append creates a new list from elements of two or more lists.

(test (append (list 0) (list 1 2 3 4)) '(0 1 2 3 4))

(test (append (list 1 2) (list 3 4) (list 5 6 7)) '(1 2 3 4 5 6 7))

(test (list (list 1 2) (list 3 4) (list 5 6 7)) '((1 2) (3 4) (5 6 7)))

(test (first (list (list 1 2) (list 3 4) (list 5 6 7))) '(1 2))


;; reverse reverses a list

(test (reverse (list 1 2 3 4)) '(4 3 2 1))


;; Lists are not simply flat structures.

(test (rest (list (list 1 2) (list 3 4) (list 5 6 7))) '((3 4) (5 6 7)))


;; assoc finds an element in an association list based on its first element.
;; If no such element is found, #f is returned.

(define months-days '((jan 31) (feb 28) (mar 31) (apr 30) (may 31) (june 30)))

(test (assoc 'apr months-days) '(apr 30))

(test (assoc 'july months-days) #f)


;; representing matrices

(define amatrix
  '((1 2 3 4)
   (1 4 9 16)
   (1 8 27 64)))

(define (matrixRef matrix row col)
  (list-ref (list-ref matrix row) col))

(test (matrixRef amatrix 2 1) 8)


;; Conditional expressions

(test (if '#t 4 5) 4)
(test (if '#f 4 5) 5)
(test (if (> 3 2) 4 5) 4)
(test (if (< 3 2) 4 5) 5)
(test (if (assoc 'apr months-days) 'valid 'invalid) 'valid)
(test (if (assoc 'jul months-days) 'valid 'invalid) 'invalid)


;; let expressions

(test (let ((x 9999)) (* x x)) 99980001)
(test (let ((x 9999) (y 9998)) (* x y)) 99970002)

(test (let (
            (found (assoc 'apr months-days))
            )
        (if found
            (second found)
            -1)) 
      30)
                   
(test (let (
            (found (assoc 'jul months-days))
            )
        (if found
            (second found)
            -1)) 
      -1)


;; let* expressions

(test (let* (
             (x 9999)
             (y (* x x))
             )
        y)
       99980001)


;; We can use higher-order functions on lists, such as foldr and map
;; The first argument of foldr is a binary function. The second is
;; the unit for that function, which is returned when the third argument
;; is the empty list.

;; (average L) returns the aveage of a non-empty list of numbers

(define (average L) (/ (foldr + 0 L) (length L)))

(test (average '(8 9 10 11 12)) 10)

(define (square x) (* x x))

(define (sum-squares L) (foldr + 0 (map square L)))

(test (sum-squares '(1 2 3 4 5 6 7 8 9 10)) 385)


;; (maximum L) returns the maximum of a non-empty list of numbers
;; The maximum of an empty list is defined as negative infinity, 
;; which is represented as -inf.0 in Scheme.

(define (maximum L) (if (null? L) -inf.0 (foldr max (first L) L)))

(test (maximum '(3 -5 17 8 6 -2 0 1)) 17)


;; Simple recursive definition

;; (factorial n) is n factorial,
;; where n is a non-negative integer

(define (factorial n)
  (if (< n 2)
      1
      (* n (factorial (- n 1)))))

(test (factorial 10) 3628800)


;; (inverse-factorial m) is the least integer n such that 
;; (factorial n) is m or more. This uses an auxiliary function.
;; Note that more complex functions require more test coverage.

(define (inverse-factorial-aux acc n m)
  (if (>= acc m)
      n
      (inverse-factorial-aux (* (+ n 1) acc) (+ n 1) m)))

(define (inverse-factorial m)
  (if (< m 2)
      0
     (inverse-factorial-aux 2 2 m)))

(test (inverse-factorial 1) 0)
(test (inverse-factorial 2) 2)
(test (inverse-factorial 3) 3)
(test (inverse-factorial 6) 3)
(test (inverse-factorial 23) 4)
(test (inverse-factorial 24) 4)
(test (inverse-factorial 25) 5)
(test (inverse-factorial 119) 5)
(test (inverse-factorial 120) 5)
(test (inverse-factorial 121) 6)


;; (choose m n) is number of combinations of m things chosen n at a time
;; without regard to order. 
;; Note that this is not an efficient way to compute. Can you do better?

(define (choose m n) (/ (factorial m) (* (factorial n) (factorial (- m n)))))

(test (choose 6 2) 15)(test (choose 8 3) 56)


;; Lists can be created by recursion.

;; (range m n) is a list of numbers from m through n, provided that m < n
;; otherwise it is the empty list.

(define (range m n)
  (if (<= m n)
      (cons m (range (+ 1 m) n))
      '()))

(test (range 5 15) '(5 6 7 8 9 10 11 12 13 14 15))

(test (reverse (range 5 15)) '(15 14 13 12 11 10 9 8 7 6 5))


;; This special call to tester shows how well we did overall:

(tester 'show)