; CSE 341 - Section 6 - May 4th
#lang racket
(provide (all-defined-out))

;========================
; OUTLINE
;========================
; *) Mutation
; *) Memoization
;  *) Background: scoping, associative lists
;  *) Idiom that makes some algorithms (sometimes much) more efficient
;  *) Demonstration: speeding up naive fibonacci
; *) Streams
;  *) Definition and use


; We'll require a few things to implement memoization:
; 1) a memory local to a function that can remember results;
; 2) a way to look up results in that memory




; 1) a memory local to a function that can remember results
;========================
;MUTATION
;========================

; Racket is like most (all?) other languages in that there are
;   * "values", data structures in memory;
;   * "variables", names which can refer to data structures.

; Racket's facilities for mutation:
;
;   (set! var value)
;     re-binds the name `var` to refer to `value`
;     (in the namespace `var` is defined in)
;
;   (mcons value value)
;     builds a "mutable pair" -- just like (cons value value),
;     but supports the next four functions...
;
;   (set-mcar! mp value)
;   (set-mcdr! mp value)
;     changes the *pair data structure* mp refers to,
;     so the car/cdr is now `value`
;
;   (mcar mp)
;   (mcdr mp)
;     exactly like `car` and `cdr`, except they operate on `mcons`s instead
;     Not interchangeable with `car` and `cdr`!
;
; Example use:
(define mp (mcons 1 2))
(define mp2 mp)
(set-mcar! mp "l") ; change first value in mutable pair mp to "l"
(set-mcdr! mp "r") ; change second value in mutable pair mp to "r"
mp  ; => (mcons "l" "r")
mp2 ; => (mcons "l" "r")
(set! mp (mcons 3 4))
mp  ; => (mcons 3 4)
mp2 ; => (mcons "l" "r")
; Note that (set! mp ...),
;    unlike (set-mcar! mp ...),
;    did *not* modify the data structure!
; It just made mp point at a new object!


; These are analogous to regular pairs and lists, but mutable!
; NOTE: they are NOT the same however
; they are completely different datatypes
; (with the exception that the empty list is also the empty mutable list)

; Use mutable types only when necessary! Prefer immutable!











;========================
; LEXICAL SCOPE
;========================
; how do these procedures differ?

(define accumulate-1
  (let ([acc 0])
    (lambda (x)
      (begin
        (set! acc (+ acc x))
        acc))))

(define accumulate-2
  (lambda (x)
    (let ([acc 0])
      (begin
        (set! acc (+ acc x))
        acc))))





; 2) a way to look up results in that memory
;========================
; ASSOCIATIVE LISTS
;========================

; Associative lists (lists of key-value pairs)
; are one simple way to achieve that!

; library function named "assoc" will do lookups by key in any associative list
;   (assoc value my-list)
;     returns the first pair in the list in which its car is equal?
;      to the given `value`. Returns the entire pair found.
;     If the key isn't found, it returns #f.

(define my-list (list (cons 1 2) (cons 3 4) (cons 3 6) (cons "example" #t)))
; note:
;  > my-list
;  '((1 . 2) (3 . 4) (3 . 6) ("example" . #t))
; The apostrophe is syntactic sugar for list literals,
;   the . is syntactic sugar for pairs.
;
(assoc 1 my-list) ; => '(1 . 2)
(assoc 3 my-list) ; => '(3 . 4)     NOTE: not '(3 . 6)
(assoc 6 my-list) ; NOTE: assoc only looks at the car of each pair





;========================
; REFRESHER -> FIBONACCI
;========================
(define (fibonacci x)
  (if (or (= x 1) (= x 2))
      1
      (+ (fibonacci (- x 1))
         (fibonacci (- x 2)))))

;(println "Computing (fibonacci 38)...")
;(fibonacci 38)

; Why is this procedure slow?
; We end up recomputing many values,
;  due to the doubly-recursive structure of the function.
; Runtime grows exponentially with x! Bad! Very bad!

; One method of speeding up the naive fibonacci is to remember results
; from previous calls.

; This idiom is called *memoization*.
; Memoization will allow fibonacci to become almost exponentially faster!


;========================
; MEMOIZATION -> REIMPLEMENTING FIBONACCI
;========================
; We now know:
;   how to create a function-local cache that can remember things,
;   methods to mutate that cache,
;   and how to use an associative list!
; Now, let's combine all this to make a Fibonacci-number calculator
;   that remembers its results instead of recomputing them.

(define memo-fibonacci1
  (let ([memory null]) ; don't expose memo to outside world
    (lambda (n) ; fibonacci only takes one argument, but memoization
                ; easily generalizes to multiple arguments
      (if (assoc n memory) ; saved result in cache?
          (cdr (assoc n memory))
          (if (or (= n 1) (= n 2))
              1
              (let ([result (+ (memo-fibonacci0 (- n 1))
                               (memo-fibonacci0 (- n 2)))])
                (set! memory
                      (cons (cons n result) memory))
                result))))))

;(print "Computing (memo-fibonacci0 38)...")
;(memo-fibonacci0 38)

; this implementation avoids exponential blowup!
; instead of taking time proportional to 2^x, takes time proportional to x


; Some other approaches:

(define memo-fibonacci2
  (letrec ([memo '((1 . 1) (2 . 1))] ; you can put your base cases in results cache!
           [f (lambda (x)
                (let ([ans (assoc x memo)])
                  (if ans
                      (cdr ans)
                      (let ([new-ans (+ (memo-fibonacci2 (- x 1)) (memo-fibonacci2 (- x 2)))])
                        (begin
                          (set! memo (cons (cons x new-ans) memo))
                          new-ans)))))])
    f))

(define (memo-fibonacci3 x)
  (define ans (if (or (= x 1) (= x 2))
                 1
                 (+ (memo-fibonacci3 (- x 1))
                    (memo-fibonacci3 (- x 2)))))
  (define f memo-fibonacci3)
  (set! memo-fibonacci3 (lambda (y) (if (= x y) ans (f y))))
  ans)

;========================
; STREAMS => REFRESHER
;========================
; Streams are another powerful programming idiom:
;  they allow us to represent an infinite list,
;  without actually creating one.

;========================
; STREAMS => SIMPLE EXAMPLES
;========================

; A stream is implemented as a "thunk" (0-argument function)
;  that evaluates to a pair of an element and another stream.
; This is an infinitely recursive definition. There's no end to a stream!

(define (ones) (cons 1 ones))

(define (take n stream)
  (if (= n 0) null
      (let ((s (stream)))
      (cons (car s)
            (take (- n 1) (cdr s))))))

(define natural-numbers
  (letrec ([next-nat (lambda (x)
                (cons x (lambda () (next-nat (+ x 1)))))]) ; return next pair
    (lambda () (next-nat 0)))) ; "seed" the stream

; How does this work? Let's pull some results out of a stream to see:
; natural-numbers                   ; just a thunk
; (natural-numbers)                 ; extract pair from stream
; ((cdr (natural-numbers)))         ; get pair after next
; ((cdr ((cdr (natural-numbers))))) ; ...

(define powers-of-two
  (letrec ([next-thunk (lambda (x) (cons x (lambda () (next-thunk (* x 2)))))])
    (lambda () (next-thunk 1))))

; see a pattern?

(define (stream-maker init fn)
  (letrec ([next-thunk (lambda (x)
                (cons x (lambda () (next-thunk (fn x)))))])
    (lambda () (next-thunk init))))
(define nats2  (stream-maker 0 (lambda (x) (+ x 1))))
(define powers2 (stream-maker 1 (lambda (x) (* x 2))))

; recursive functions make elegant use of streams
; here's an example

(define (number-until stream tester)
  (letrec ([f (lambda (stream ans)
                (let ([pr (stream)])
                  (if (tester (car pr))
                      ans
                      (f (cdr pr) (+ ans 1)))))])
    (f stream 1)))

(define four (number-until powers-of-two (lambda (x) (= x 16))))

; warning ->> it's very easy to make mistakes with parens when using streams
; for example: passing a pair instead of a stream

; code safely!