09-12.rkt

#lang racket

;; Recursion over lists
(cons 1 (cons 2 (cons 3 (cons 4 '()))))

;; more laboriously as ...
(let ([last-link (cons 4 '())])
  (let ([second-to-last-link (cons 3 last-link)])
    (let ([third-to-last-link (cons 2 second-to-last-link)])
      (cons 1 third-to-last-link))))

;; write '(4 3), equivalently (list 4 3), using the cons syntax only...
(cons 4 (cons 3 '()))

;; Primitive recursive functions over lists all have the following "recipe"

;; All primitive recursive functions--recursive over just a list--follow this recipe
(define (f lst)
  (if (empty? lst)
      'base-case
      ;; the inductive case will extract the cdr and will call f on the cdr to obtain
      ;; a "partial" result--that partial result will then be combined with the car
      ;; of lst (i.e., the first element of lst) to obtain the desired result
      'inductive-case))

;; some facts about primitive recursive functions:
;; - they always terminate. Why?
;;  -> Because any time the computer can hold a list, materialized in RAM, the list is finite
;;  -> So by the template above, every to f operates on a "smaller" subordinate list.
;;  -> Eventually, you "bottom out" (i.e., hit the base case)
;; - some functions--even useful functions--are *not* primitive recursive

;; some examples of primitive recursive functions

;; first--I always have to copy the template, i.e., the (design) recipe

;; extracts the maximum value from a list
(define (max-lst lst)
  (if (empty? lst)
      ;; for the base case, how do I handle it?
      ;; if someone asks me for the maximum value of a list, what is a sensible
      ;; return value?
      -inf.0
      ;; what about the inductive case?
      (let ([rest-lst (cdr lst)])
        ;; now--call max on rest-lst, and combine it with (car lst) to obtain the result
        (max (car lst) (max-lst rest-lst)))))



;; the following is an equality

;; whenever you have a piece of code
;;(let ([x expr])
;;  (... x))
;; you could always instead write
;;(... expr)

;; for example
;;(let ([x (+ 1 2)])
;;  (* x x))

;; this is the same as
;;(* (+ 1 2) (+ 1 2))

;; and in fact, this is how textual reduction works for let

;; multiply all of the elements in lst together
;; (product-lst '(1 3 4)) => 12
(define (product-lst lst)
  (if (empty? lst)
      1
      (* (car lst) (product-lst (cdr lst)))))

;; don't use racket's built-in member
;; return #t iff e in the list lst
;; 
;; use equal? for structural equality
(define (check-member? lst e)
  (if (empty? lst)
      #f
      (if (equal? (first lst) e)
          #t
          (check-member? (rest lst) e))))

;; filter takes two arguments:
;; - a list lst 
;; - a function f, which is a predicte that can be applied to each element of the list lst
;; (filter lst f) returns each element of lst--in order--which satisfies f, all other
;; elements which do not satisfy f (i.e., which return false for f) are dropped out
(define (filter lst f)
  (if (empty? lst)
      '()
      ;; the inductive case will extract the cdr and will call f on the cdr to obtain
      ;; a "partial" result--that partial result will then be combined with the car
      ;; of lst (i.e., the first element of lst) to obtain the desired result
      ;; hint: use cons, call filter on the tail of lst with f
      (if (f (car lst))
          (cons (first lst) (filter (cdr lst) f))
          ;; drop (car lst) from the list lst
          (filter (cdr lst) f))))

;; assertion: this is the identity function
;; proof: induction on lst..
(define (regurgitate-list lst)
  (if (empty? lst)
      '()
      (cons (car lst) (regurgitate-list (cdr lst)))))

;; zip is a function that takes two lists, lst0 and lst1
;; assume lst0 and lst1 are the same size
;; it will return one list of cons cells, the length of both
;; lst0/lst1 (same by assumption) where each nth element is
;; the cons of the corresponding elements of lst0 and lst1
(define (zip lst0 lst1)
  ;; assume that you can check either lst0 or lst1 for empty?
  ;; because by assumption they are the same size--and so
  ;; (empty? lst0) iff (empty? lst1)
  (if (empty? lst0)
      '()
      (cons (cons (car lst0) (car lst1))
            (zip (cdr lst0) (cdr lst1)))))

(define (argmax f l)
  ;; let's write a helper function to surmise the maximum value attained by f
  ;; from each element in l
  (define (max-of-f-in-l lst)
    (if (= (length lst) 1)
        (f (first lst))
        (max (f (first l)) (max-of-f-in-l (rest lst)))))
  ;; maximum value attained by f(e) for e ∈ l
  ;; currently wrong.. need more...
  ;; now let's write a helper function that takes this value and
  ;; finds the value e in l such that (f e) is equal to this
  ;; maximized value
  (define (find-element lst max-val)
    (if (empty? lst)
        (error "I assumed the value max-val is maximezed in the lst lst")
        (if (equal? (f (first lst)) max-val)
            ;; I found it!
            (first lst)
            ;; otherwise, keep looking--I won't hit the base case, because
            ;; by assumption, the number that maximizes max-val *exists
            ;; in the list*.
            (find-element (cdr lst) max-val))))
  (find-element l (max-of-f-in-l l)))
        

;; tests for argmax

(argmax add1 '(5 -3 1 2)) ;; 5
(define (g x) (* (- x 2) (- x 2)))

(argmax g '(-5 -3 -2 0 2 4 5 8))
(argmax-again g '(-5 -3 -2 0 2 4 5 8))

;; write a function that returns #t iff the board is full of only
;; 'X, 'O, or 'E
(define (check-valid-xoe lst)
  (cond [(empty? lst) #t]
        [(equal? (first lst) 'X) (check-valid-xoe (rest lst))]
        [(equal? (first lst) 'O) (check-valid-xoe (rest lst))]
        [(equal? (first lst) 'E) (check-valid-xoe (rest lst))]
        [else #f]))

(define (get-value-at lst row col)
  (define size (sqrt (length lst))) ;; you need to know this is integral
  ;; but you do assuming board?
  (list-ref lst (+ (* size row) col)))