;; File:    sampler.rkt
;; Author:  Robert Keller
;; Purpose: A basic sampler for how to compute with Racket

#lang racket

(require htdp/testing)

;; We use check-expect and check-within from library htdp/testing
;; to exemplify the expected value of evaluating various expressions.
;; This serves as both documentation as well as for unit tests.
;; At the end, the call to generate-report tells us whether we
;; made any errors.


;; Simple arithmetic expressions with functions + * - /

;;            Expression              Expected result
(check-expect (+ 2 3)                               5)  ;; Addition
(check-expect (+ 2 3 4 5)                          14)  ;; Arbitrary arity addition
(check-expect (+)                                   0)  ;; Even 0-ary addition makes sense.
(check-expect (- 10 6)                              4)  ;; Subtraction
(check-expect (- 8)                                -8)  ;; Unary minus
(check-expect (* 2 3)                               6)  ;; Multiplication
(check-expect (* 2 3 4)                            24)  ;; Arbitrary arity multiplication
(check-expect (*)                                   1)  ;; Note identity element.
(check-expect (/ 6 3)                               2)  ;; Non-truncating division
(check-expect (/ 3 6)                             1/2)  ;; Rational numbers
(check-expect (/ 8 6)                             4/3)
(check-expect (/ 8)                               1/8)  ;; reciprocal
(check-expect (+ 2 (* 3 4) (/ 5 (- 6 7)) (- 8))     1)  ;; Nested expressions

(check-expect (/ 21 4)                      (+ 5 1/4))  ;; exact for rationals
(check-expect (quotient 21 4)                       5)  ;; integer remainder
(check-expect (modulo 21 4)                         1)  ;; modulus (integer remainder) 
(check-expect (floor (/ 8 6))                       1)  ;; floor is greatest integer <=
(check-expect (ceiling (/ 8 6))                     2)  ;; ceiling is least integer >=
(check-expect (round (/ 8 6))                       1)  ;; Round to nearest integer
(check-expect (round (/ 9 6))                       2)
(check-expect (sqrt 1/4)                          1/2)  ;; Rational square root
(check-expect (sqrt -1)                          0+1i)  ;; Complex numbers
(check-expect (min 5 2 4 -1 3)                     -1)
(check-expect (max 5 2 7 -1)                        7)
(check-expect (max 1)                               1)  ;; max requires at least one argument

(check-within (+ 1 1.5) 2.5 0) ;; Use check-within rather than check-expect for inexact numbers.
(check-within (/ 2. 5)                     0.4      0)  ;; Third argument is tolerance
(check-within (sqrt 2)                     1.414 3e-4)  ;; The second argument is a tolerance
(check-within (real-part (exp (* 0+i pi))) -1.0 1e-16)  ;; e^(-i*pi) is -1
(check-within (cos 0)                      1        0)
(check-within (cos (/ pi 2))               0    1e-16)
(check-within (atan 1)               (/ pi 4)   1e-16)  ;; arc tangent

(check-expect (< 2 3)                              #t)  ;; relational operators
(check-expect (<= 2 2.5)                           #t)
(check-expect (> 2 3)                              #f)
(check-expect (>= 3 3)                             #t)
(check-expect (= 5/2 2.5)                          #t)
(check-expect (= 1/3 .333333333333333)             #f)
(check-expect (> 1/3 .333333333333333)             #t)

(check-expect (char<? '#\a '#\b)                   #t)
(check-expect (char=? '#\a '#\b)                   #f)
(check-expect (equal? '#t '#\t)                    #f)   ;; #t is a truth value, #\t a char


;; Function definition examples 
;; 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 Racket is case-sensitive.

;; A function to onvert farenheit to Celsius

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

(check-expect (Farenheit->Celsius 32)    0)
(check-expect (Farenheit->Celsius 212) 100)

(check-expect (Farenheit->Celsius 45)   (+ 7 2/9))


;; A function to onvert Celsius to farenheit

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

(check-expect (Celsius->Farenheit 0)    32)
(check-expect (Celsius->Farenheit 100) 212)
(check-expect (Farenheit->Celsius (Celsius->Farenheit 100)) 100)

(check-expect (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.

(check-expect (list 1 2 3 4) '(1 2 3 4))
(check-expect (list 1)             '(1))
(check-expect (list)                '())  ;; Note '() and not ().


;; first returns the first element of a list.

(check-expect (first (list 1 2 3 4)) 1)
(check-expect (first (list 1))       1)


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

(check-expect (rest (list 1 2 3 4))          '(2 3 4))
(check-expect (rest (list 1))                     '())
(check-expect (first (rest (list 1 2 3 4)))         2)
(check-expect (rest (rest (list 1 2 3 4)))     '(3 4))


;; list-ref finds the position of the index, the second argument, 
;;     in the first argument list.
;; Caution: This function should be used sparingly, 
;;     as the time cost is proportional to the index.

(check-expect (list-ref (list 1 2 3 4) 0) 1)  ;; index 0 is first element
(check-expect (list-ref (list 1 2 3 4) 2) 3)  ;; index 2 is 3rd element


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

(check-expect (cons 0 (list 1 2 3 4)) '(0 1 2 3 4))

;; Lists of lists are possible.

(check-expect (list (list 1 2) (list 3 4) (list 5 6 7)) '((1 2) (3 4) (5 6 7)))

;; first and rest deal with the outer list.

(check-expect (first (list (list 1 2) (list 3 4) (list 5 6 7))) '(1 2))
(check-expect (rest  (list (list 1 2) (list 3 4) (list 5 6 7))) '((3 4) (5 6 7)))

;; Note that cons and list are quite different.

(check-expect (cons 0 (list 1 2 3 4))  '(0 1 2 3 4))
(check-expect (list 0 (list 1 2 3 4)) '(0 (1 2 3 4)))


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

(check-expect (append (list 0) (list 1 2 3 4))                '(0 1 2 3 4))
(check-expect (append (list 1 2) (list 3 4) (list 5 6 7)) '(1 2 3 4 5 6 7))

;; append has arbitrary arity

(check-expect (append (list 0) (list 1 2 3 4) (list 5 6)) '(0 1 2 3 4 5 6))
(check-expect (append)                                    '())

;; append, cons, list are similar, yet different.

(check-expect (append (list 0 1) (list 2 3 4))  '(0 1 2 3 4))
(check-expect (cons (list 0 1) (list 2 3 4))  '((0 1) 2 3 4))
(check-expect (list (list 0 1) (list 2 3 4))  '((0 1) (2 3 4)))


;; reverse reverses a list.

(check-expect (reverse (list 1 2 3 4)) '(4 3 2 1))
(check-expect (reverse '())            '())
(check-expect (reverse (list (list 1 2) (list 3 4) (list 5 6 7))) '((5 6 7) (3 4) (1 2)))


;; use null? to test emptiness.

(check-expect (null? '())  #t)
(check-expect (null? '(1)) #f)


;; use member to determine whether an element occurs in a list.
;; The value returned is the list beginning with that element if so,
;; or #f if not

(check-expect (member 5 '(1 2 5 7 6 5 9)) '(5 7 6 5 9))
(check-expect (member 8 '(1 2 5 7 6 5 9)) #f)


;; assoc finds an element in an association list based on equality of the first
;; of the element, a list, with the first argument.
;; If no such element is found, #f is returned, which is kind of weird.
;; Recall that anything other than #f is interpreted at #t if a Boolean argument
;; is expected.

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

(check-expect (assoc 'apr months-days) '(apr 30))

(check-expect (assoc 'july months-days) #f)


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

;; higher-order list functions

;; map
(check-expect (map square '(1 2 3 4 5)) '(1 4 9 16 25))
(check-expect (map cube '(1 2 3 4 5)) '(1 8 27 64 125))

;; mapping 2-ary functions
(check-expect (map + '(1 2 3) '(4 5 6)) '(5 7 9))
(check-expect (map list '(1 2 3) '(4 5 6)) '((1 4) (2 5) (3 6)))

;; use filter to select items satisfying predicate

(check-expect (filter odd? '(1 2 3 4 5 6 7)) '(1 3 5 7))
(check-expect (filter even? '(1 2 3 4 5 6 7)) '(2 4 6))


;; for foldl and foldr, note the requirement for a unit as the second argument

(check-expect (foldl + 0 '(1 2 3 4 5)) 15)
(check-expect (foldl + 0 '()) 0)
(check-expect (foldl * 1 '(1 2 3 4 5)) 120)
(check-expect (foldl * 1 '()) 1)

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

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


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

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

(check-expect (average '(8 9 10 11 12)) 10)


;; foldl vs. foldr

(check-expect (foldl cons '() '(1 2 3 4 5)) '(5 4 3 2 1))
(check-expect (foldr cons '() '(1 2 3 4 5)) '(1 2 3 4 5))


;; representing matrices as lists

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

;; compute the lengths of each row

(check-expect (map length amatrix) '(4 4 4))


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

(check-expect (matrixRef amatrix 2 1) 8)

;; summing the squares of each row of a matrix

(check-expect (map sum-squares amatrix) '(30 354 4890))



;; let expressions
;; The form is: (let <list of equations> result)
;; where an equation is a list (<variable> <value>).

(check-expect (let ((x 9999)) (* x x)) 99980001)
(check-expect (let ((x 9999) (y 9998)) (* x y)) 99970002)

(check-expect 
 (let (
       (found (member 'apr (map first months-days)))
       )
   (if found
       (first found)
       -1)) 
 'apr)
                   
(check-expect 
 (let (
       (found (assoc 'apr months-days))
       )
   (if found
       (second found)
       -1)) 
 30)
                   
(check-expect 
 (let (
       (found (assoc 'jul months-days))
       )
   (if found
       (second found)
       -1)) 
 -1)


;; let* expressions evaluate the equations sequentially,
;; with the bindings of previous equations in force for the following one.

(check-expect 
 (let* (
        (x 9999)
        (y (* x x))
        )
   y)
 99980001)


;; Conditional expressions

(check-expect (if '#t 4 5) 4)
(check-expect (if '#f 4 5) 5)
(check-expect (if (> 3 2) 4 5) 4)
(check-expect (if (< 3 2) 4 5) 5)

; Note that anything other than #f is interpreted as if #t.

(check-expect (if (assoc 'apr months-days) 'valid 'invalid) 'valid)
(check-expect (if (assoc 'jul months-days) 'valid 'invalid) 'invalid)


;; cond expressions

(check-expect 
 (cond ((< 3 1) 'a)
       ((< 3 2) 'b)
       ((< 3 3) 'c)
       ((< 3 4) 'd)
       ((< 3 5) 'e)
       (else    'f))
 'd)


;; case expressions

(check-expect 
 (let (
       (x 'c)
       )
   (case x
     ('a   1)
     ('b   2)
     ('c   3)
     ('d   4)
     ('c   5)
     (else 6)))
 3)


;; (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 Racket. We use a conditional here
;; to avoid the inexact result that would be produced if we simply used
;; foldl.

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

(check-expect (maximum '(3 -5 17 8 6 -2 0 1)) 17)
(check-within (maximum '()) -inf.0 0) ;; can't use check-expect here


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

(check-expect (factorial 10) 3628800)


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

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

(check-expect (choose 6 2) 15)(check-expect (choose 8 3) 56)


;; (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 should have 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)))

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


;; creating lists 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))
      '()))

(check-expect (range 5 15) '(5 6 7 8 9 10 11 12 13 14 15))

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


;; transposing a matrix
;; Note: It is assumed that all rows have the same length.
;; The function does not check for this, and will fail if it is not the case.

(define (transpose m)
  (if (null? m)                ;; matrix with no rows
      '()
      (if (null? (first m))    ;; matrix with rows that are empty
          '()
          (cons (map first m) (transpose (map rest m))))))

(check-expect (transpose '((1 2 3) (4 5 6))) '((1 4) (2 5) (3 6)))
(check-expect (transpose '((1 4) (2 5) (3 6))) '((1 2 3) (4 5 6)))

;; lambda expressions

(check-expect ((lambda (x) (+ x 1)) 5) 6)
(check-expect (map (lambda(x) (* x x)) '(1 2 3 4 5)) '(1 4 9 16 25))
(check-expect (filter (lambda(x) (zero? (modulo x 5))) '(1 2 3 4 5 6 7 8 9 10 11)) '(5 10))
(check-expect (((lambda (x) (lambda (y) (list y x))) 5) 6) '(6 5))
(check-expect (((lambda (f) (lambda (x) (f (f x)))) square) 3) 81)


(generate-report)