CIS352 notes: 01/20

01-20.rkt

#lang racket

(define x 22)

;; □ -- List introduction: literals, basic operations
'()
'foo
'(x y z) ;; homoiconicity -- the language uses the same
         ;; representation for syntax / expressions as it does
         ;; for data.

;; □ -- The inherently structure of Racket's lists

;; There's a very basic and common recipe for writing any recursive
;; function over lists. This is the "direct-style recursion," and
;; first kind of iteration we'll learn about.

;; direct-style recursion is akin to this sort of iteration
;; for (x : lst) {
;;                ...
;; }               

(define (length lst)
  (if (empty? lst)
      0
      (+ 1 (length (rest lst)))))

;; To define the recursion, we...
;;  - Define the base case: how do we handle a fixed amount of data
;;    (in this case, that's the empty list...)
;;  - Define the recursive case in the following manner:
;;    - First, make a recursive call to process (rest l)
;;    - Next, combine that intermediate result with (first l)

(define (recursive-template lst)
  (if (empty? lst) ;; checking: is it the base case?
      'base-case
      (let ([x (recursive-template (rest lst))])
        ;; now x is in scope within the let
        'combine-first-lst-with-x)))

;; If you use this template, every function over lists terminates


;; according to the template...
#;(define (length lst)
  (if (empty? lst)
      0
      (let ([x (length lst)] [y 0])
        (+ 1 x))))

;; □ -- Direct style recursion over lists
;;  -> length
;;  -> sum
(define (sum l)
  (if (empty? l)
      'todo
      'todo)) ;; need to use (first l) and (sum (rest l))

;; quickanswer.harp-lab.com

;;  -> sum

#;(define (sum l)
  (if (empty? l)
      0
      (+ (first l) (sum (rest l)))))

;;  -> exists?

;; returns #t if the element is in the list l
;; returns #f otherwise. Compare elements using
;; equal?

(define (exists? l x)
  (if (empty? l)
      #f
      (if (equal? (first l) x) 
         #t 
         (exists? (rest l) x))))
;;  -> lists-equal? (two lists equal?)

;; two lists are equal when they contain the same number
;; of elements where each has a corresponding match
(define (lists-equal? l0 l1)
  'todo)

(define (lists-equal? l0 l1)
  (if (empty? l0)
      (empty? l1)
      (if (empty? l1)
          ;; (empty? l0) is #f, but (empty? l1) is #t
          #f
          ;; neither is empty
          (and (equal? (first l0) (first l1))
               (lists-equal? (rest l0) (rest l1))))))

;; are the two lists, l0, and l1 equal?
;; Assume: lengths are equal
(define (l-equal? l0 l1)
  (if (empty? l0)
      ;; assume l1 is also empty
      #t
      ;; we know if we got here, l0 and l1 are both not empty
      (and ;; the first elements of l0 / 1l are both equal
       (equal? (first l0) (first l1))
       ;; how do I know if the rests of l0 / l1 are equal?
       (l-equal? (rest l0) (rest l1)))))

(define (lists-equal? l0 l1)
  (and (equal? (length l0) (length l1))
       (l-equal? l0 l1)))

       
      
;; returns #t if the element is in the list l

;; returns #f otherwise. Compare elements using

;; equal?

;; two lists are equal when they contain the same number

;; of elements where each has a corresponding match

#;(define (lists-equal? l0 l1)
  (cond [(empty? l0) (empty? l1)] ;; if l0 is empty, l1 had better also be empty
        ;; we know l0 isn't empty
        [(empty? l1) #f]
        ;; we know neither l0 / l1 is empty 
        [else (lists-equal? (rest l0) (rest l1))]))
  
;;  -> zip / unzip
;;  -> forall


;; □ -- Representing game boards as flattened lists

;; How do represent a board like this:
;;   |   | X
;; ---------
;; O |   | O
;; ---------
;;   | X |  
'(E E X O E O E X E)

;; I will represent game boards as lists of size n*n for some n

;; write a function, (board-ref b i j) i is the row, j is the column
;; you return the element {'E, 'X, 'O}. First, calculate the index
;; in the list, and then use (list-ref l i)
(define (board-ref b i j)
  (define N (sqrt (length b))) ;; assume N is a whole number
  (list-ref b (+ (* N i) j)))

  
;;  -> Game boards are n*n 
;;  -> Mapping x,y coordinates to list elements
;;  -> Update a cell of the game board
;;  -> When does a player win?