#lang racket ; Fibonacci v1.0 (define (fib x) (if (or (= x 1) (= x 2)) 1 (+ (fib (- x 1)) (fib (- x 2))))) ; Questions: ;; 1. Is this tail recursive? If not, why not? ;; 2. Is there any repeated/redundant work? If so, what is it? ; Lexical scope again! ;; Questions: ;; 1. How are the below two examples similar? ;; 2. How are the below two examples different? ;; 3. Is one more efficient than the other? If so, which one and why? (define ex-1a (let ([v (fib 1)]) (lambda (x) (+ x v)))) (define ex-1b (lambda (x) (let ([v (fib 1)]) (+ x v)))) ; Mutation ;; Blast from the past! What do these lines do in SML? ;; val x = ref 0 ;; val _ = x := (!x) + 7 ;; Racket analog? (define x 0) (set! x (+ x 7)) ;; Mutation for Pairs/Lists ;;; Racket separates mutable lists from immutable lists explicitly... ;;;; Mutable Immutable ;; (define mp (mcons 1 2)) (define p (cons 1 2)) ;; (mpair? mp) (pair? p) ;; (mcar mp) (car p) ;; (mcdr mp) (cdr p) ;; (set-mcar! mp 5) ??? ;; (set-mcdr! mp 6) ??? ; Lexical Scope + Mutation ;; Question: What does ex-2a do? What does ex-2b do? (define ex-2a (let ([c (mcons 1 '())]) (lambda (x) (begin (set-mcdr! c (mcons x (mcdr c))) c)))) (define ex-2b (lambda (x) (let ([c (mcons 1 '())]) (begin (set-mcdr! c (mcons x (mcdr c))) c)))) ; Associative Lists? (aka Hash Maps) ;; This is an example of an "Associative List" (define my-list (list (cons 1 2) (cons 3 4) (cons 5 6) (cons "example" #t))) ;; An associative list is just a list of key-value pairs. ;; But how can we use it like a Hash Map (i.e. look-up by their key?) ;; Assoc! (assoc 3 my-list) ;; The library function "assoc" will do lookups by key in any valid associative list. ;; It returns the first pair in the list in which its car is equal? to the ;; requested key value, and returns the entire pair. (or #f if not found) ;; For example, these would return pairs (assoc 1 my-list) (assoc "example" my-list) ;; While these would return #f (assoc 100 my-list) (assoc 2 my-list) ; Fibonnaci v2.0 (define memo-fib (letrec([memo null] ; list of pairs (arg . result), initially empty [f (lambda (x) (let ([ans (assoc x memo)]) (if ans ; saved result in cache? (cdr ans) ; return memoized answer (let ([new-ans (if (or (= x 1) (= x 2)) ; otherwise, compute new answer 1 (+ (f (- x 1)) (f (- x 2))))]) (begin (set! memo (cons (cons x new-ans) memo)) ; save it new-ans)))))]) ; return new answer f)) ; ultimately, return f, which is memoized fib ;; Variation (define memo-fib2 (letrec ([memo '((0 . 0) (1 . 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 (+ (f (- x 1)) (f (- x 2)))]) (begin (set! memo (cons (cons x new-ans) memo)) new-ans)))))]) f)) ; Streams ;; What is this function doing? (define (s1) (cons 1 s1)) ; a stream is implemented as a thunk 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 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))))