Created
February 22, 2024 17:14
-
-
Save kmicinski/5ea61c34923be14453b95c3a80c71e45 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
;; Exercise 2 | |
;; CIS 352 -- Spring 2024 | |
#lang racket | |
(provide (all-defined-out)) | |
;; | |
;; Maps | |
;; | |
;; map the function f over each element of lst | |
(define (map f lst) | |
(if (empty? lst) | |
'() | |
(cons (f (first lst)) (map f (rest lst))))) | |
;; Racket | |
(map - '(1 2 3)) ;; ‘(-1 -2 -3) | |
;; equivalent to (via “η-extenstionality”) | |
(map (lambda (x) (- x)) '(1 2 3)) | |
;; (add-n n lst) adds n to each element of the list lst. | |
;; write the function using *direct* style recursion | |
;; (i.e., follow the template). | |
(define (add-n lst n) | |
(if (empty? lst) | |
'() | |
(cons (+ n (first lst)) (add-n (rest lst) n)))) | |
;; define add-n again, but this time using map. Your function should | |
;; not use recursion (directly, although it will indirectly be using | |
;; recursion in that `map` is recursive), but should instead simply | |
;; use `map`. | |
(define (add-n-using-map lst n) | |
(map (lambda (x) (+ n x)) lst)) | |
(define (foo x) | |
(match x | |
[(? number?) (* 2 x)] | |
[`(,e0 ,e1 ,_) `(,e0 ,e1)] | |
[_ "error"])) | |
;; | |
;; practice with matches and quasiquotes | |
;; | |
;; return only elements of lst that satisfy f | |
(define (filter f lst) | |
(cond [(empty? lst) '()] | |
[(f (first lst)) (cons (first lst) (filter f (rest lst)))] | |
[else (filter f (rest lst))])) | |
(define (fac n) | |
(if (= n 0) | |
(begin (displayln "here") 1) | |
(* n (fac (- n 1))))) | |
;; I want to write this function to use tail recursion | |
;; what that means is that every recursive call must be | |
;; "the last thing to happen" | |
(define (fac-again n) | |
;; n is going to get smaller (by 1) | |
;; acc is going get bigger | |
(define (h n acc) | |
(displayln n) | |
(displayln acc) | |
(if (equal? n 0) | |
acc | |
(h (- n 1) (* acc n)))) | |
(h n 1)) | |
(define (fib n) | |
(match n | |
[0 1] | |
[1 1] | |
[_ (+ (fib (- n 1)) (fib (- n 2)))])) | |
;; Exam problem candidate | |
;; | |
;; Circle all of the callsites that are tail calls | |
;; and underline all of the callsites that are | |
;; direct-style calls | |
#;(define (length-dir l) | |
(pretty-print l) | |
;;________________ | |
(pretty-print n) | |
;;________________ | |
(if (null? l) | |
;;_________ | |
0 | |
(+ 1 (length-dir (rest l))))) ;; (+ 1 ....) circled | |
;; ________ | |
;;_____________________ | |
;; claim: we can rewrite length-dir like this | |
#;(define (length-dir l) | |
(pretty-print l) | |
;;________________ | |
(pretty-print n) | |
;;________________ | |
(if (null? l) | |
;;_________ | |
0 | |
(let ([x (rest l)]) | |
(let ([r (length-dir x)]) | |
(+ 1 r))))) | |
(define (length-tail l) | |
(define (h l n) | |
(pretty-print l) | |
(pretty-print n) | |
(if (null? l) | |
n | |
(h (cdr l) (+ n 1)))) ;; the call to h is in tail position, it is a tail call | |
(h l 0)) ;; this call to h is a tail call, too | |
#;(define (filter f lst) | |
(cond [(empty? lst) '()] | |
[(f (first lst)) | |
(cons (first lst) | |
(filter f (rest lst)))] | |
[else (filter f (rest lst))])) | |
(define (filter-tl f lst) | |
(define (reverse l) | |
(define (rev lst0 lst1) | |
(match lst0 | |
['() lst1] | |
[`(,hd . ,tl) (rev tl (cons hd lst))])) | |
(rev l '())) | |
(define (h0 lst acc) | |
(match lst | |
['() acc] | |
[`(,hd . ,tl) | |
(if (f hd) | |
(h0 tl (cons hd acc)) | |
(h0 tl acc))])) | |
(define (h1 lst acc) | |
(match lst | |
['() acc] | |
[`(,hd . ,tl) | |
(if (f hd) | |
(h1 tl (append acc (list hd))) | |
(h1 tl acc))])) | |
;; fix 1 | |
(reverse (h0 lst '())) | |
;; fix 2 | |
#;(h1 lst '())) | |
;; acc = 1 | |
;; for(i in range(n)): | |
;; acc = acc * n | |
;; Define using match patterns: (filter f l) selects the elements in | |
;; the list l which satisfy the predicate f, omitting those elements x | |
;; for which (f x) is false | |
(define (filter-again f lst) | |
(match lst | |
['() '()] | |
[`(,hd . ,tl) #:when (f hd) (cons hd (filter-again f tl))] | |
[`(,hd . ,tl) (filter-again f tl)])) | |
;; select the maximum element from the list lst, assume lst is a list | |
;; of numbers. | |
(define (maxof lst) | |
(match lst | |
['() (error "can't take the max of an empty list")] | |
[`(,only) only] | |
[`(,fst . ,rest) | |
(max fst (maxof rest))])) | |
;; andmap test cases | |
;; > (andmap list? ‘((1 2) () (3))) | |
;; #t | |
;; > (andmap list? ‘((1 . 2) ())) | |
;; #f | |
;; > (andmap list? ‘(1 2 3)) | |
;; #f | |
(define (andmap f lst) | |
(match lst | |
['() #t] | |
[`(,hd . ,tl) (if (f hd) (andmap f tl) #f)])) | |
;; | |
;; practice with hashes and sets | |
;; | |
;; hashes in racket are key / value dictionaries | |
;; add / lookup / etc... are amortized O(1) | |
(define hsh (hash 'x 1 'y 2 'z 4)) | |
;; important functions on hashes | |
(hash-keys (hash 'x 1 'y 2 'z 3)) | |
;; returns a list of the keys of the hash | |
;; in *no specific order* | |
;; pass in a list of elements | |
(define (my-set lst) | |
;; make a hash of key/value associations from | |
;; each element of lst (which will be keys in our hash) | |
;; to the dummy value "dummy" | |
(define (h lst) | |
(match lst | |
['() (hash)] | |
[`(,hd . ,tl) (hash-set (h tl) hd "dummy")])) | |
(h lst)) | |
;; hashes are generalized *sets* | |
;; a hash-set (degenerate hash) can be constructed using | |
(define st (set 1 2 3)) | |
;; print out a hash in a canonical order | |
(define (render-hash h) | |
(for ([key (sort (hash-keys h) symbol<?)]) | |
(displayln (format "~a,~a" key (hash-ref h key))))) | |
;; produce a map from each element in lst to the number zero | |
;; (zeroes '(x y)) = (hash-set (hash-set 'y 0) 'x 0) | |
;; note that hashes are *unordered* | |
;; aka (hash 'x 0 'y 0) | |
(define (zeroes lst) | |
(match lst | |
['() (hash)] | |
;; hint: use hash-set and recursion | |
[`(,hd . ,tl) | |
(hash-set (zeroes tl) hd 0)])) | |
(define (zeroes-tl lst) | |
(define (h lst hsh) | |
(match lst | |
['() hsh] | |
[`(,hd . ,tl) | |
(h tl (hash-set hsh hd 0))])) | |
(h lst (hash))) | |
(define (foldr reducer init lst) | |
(match lst | |
['() init] | |
[`(,hd . ,tl) | |
(reducer hd (foldr reducer init tl))])) | |
(define (sum-list lst) | |
(foldr (λ (next-element-in-list current-accumulator) | |
(+ next-element-in-list current-accumulator)) | |
0 | |
lst)) | |
(define (filter-using-foldr f lst) | |
;; e is next element in the list | |
;; acc is an accumulated list of elements | |
;; principle: return type from the reducer function is | |
;; the return type of the foldr as a whole | |
(foldr (λ (e acc) | |
(if (f e) | |
(cons e acc) | |
acc)) | |
'() | |
lst)) | |
(define (filter-using-foldl f lst) | |
;; e is next element in the list | |
;; acc is an accumulated list of elements | |
;; principle: return type from the reducer function is | |
;; the return type of the foldr as a whole | |
(reverse | |
(foldl (λ (e acc) | |
(if (f e) | |
(cons e acc) | |
acc)) | |
'() | |
lst))) | |
;; Project 2 | |
;; We need to accumulate a graph: | |
;; - For all n0 ∈ Node(graph): | |
;; - For all n1 s.t. there's an edge n0 ↦ n1 ∈ Edges(graph): | |
;; - For all n2 s.t. there's an edge n1 ↦ n2 ∈ Edges(graph): | |
;; Add n0 ↦ n2 to Edges(graph) | |
;; | |
;; Insight is that each "for all in" translates into a fold | |
;; Fact: if the reducer commutes then you can use either foldr or foldl | |
;; Because we're walking over the keys of a hash--which are unordered-- | |
;; we can use either foldl or foldr to process a hash key by key | |
#;(define (one-step-transitive graph) | |
;; For all n0 ∈ Node(graph) | |
(foldl (λ (n0 graph) | |
(foldl (λ (n1 graph) | |
;; For all n2 s.t. there's an edge n1 ↦ n2 ∈ Edges(graph): | |
;; Add n0 ↦ n2 to Edges(graph) | |
...) | |
graph | |
;; all of the n1s, gives us a set, which we can transform to a list... | |
(set->list (hash-ref graph n0)))) | |
graph | |
;; this will get me the set of nodes as a list | |
(hash-keys graph))) | |
(define (map-using-foldr f l) | |
;; acc is a list | |
(foldr (λ (x acc) (cons (f x) acc)) '() l)) | |
;; no matter what l is ... | |
;; (foldl + 0 l) = (foldr + 0 l) | |
;; same thing for ... | |
;; (foldr * 1 l) = (foldr * 1 l) | |
(foldr cons '() '(1 2 3)) | |
(foldl cons '() '(1 2 3)) | |
;; acc = '() | |
;; for e in lst: | |
;; acc = (if (f e) (cons e acc) acc) | |
#;(define (sum-list l) | |
(match l | |
['() 0] | |
[`(,hd . ,tl) (+ hd (sum-list tl))])) | |
(define (sum-set st) | |
(sum-list (set->list st))) | |
;; Set data structure in Racket | |
;; Use `set` as a constructor | |
;; - (set) or (set 'x 'y ...) or (set e0 e1 ...) | |
;; | |
;; (set-add st element) O(1) -- returns a new set | |
;; that includes everything in st and also element | |
;; | |
;; (set-union st0 st1) O(n) or faster -- return | |
;; a new set that includes everything in st0 and st1 | |
;; | |
;; (set-remove st element) O(1) -- return a set | |
;; containing everything in st minus element | |
;; add n to each value of the hash, for each of its keys. Hint: write | |
;; a recursive function (or foldl, if you know / would like to use it) | |
;; to walk over each of the keys in `hash-keys`. | |
(define (add-to-each h n) | |
(define (f keys) | |
(match keys | |
['() (hash)] | |
[`(,first-key . ,rest-keys) (hash-set (f rest-keys) | |
first-key | |
(+ (hash-ref h first-key) n))])) | |
(f (hash-keys h))) | |
(define (add-to-each-using-foldr h n) | |
;; use foldr to walk over the hash keys, and accumulate a hash | |
;; for each key, retrieve its value, add n, and then set the | |
;; key to that value in the accumulator | |
(foldr (λ (next-element acc) (hash-set acc next-element (+ n (hash-ref h next-element)))) | |
(hash) | |
(hash-keys h))) | |
(define (hash-map hsh f) | |
(define (h keys) | |
(match keys | |
['() (hash)] | |
[`(,hd . ,tl) (hash-set (h tl) hd (f (hash-ref hsh hd)))])) | |
(h (hash-keys hsh))) | |
;; IfArith | |
(define (expr? e) | |
(match e | |
[(? integer? n) #t] | |
[`(plus ,(? expr? e0) ,(? expr? e1)) #t] | |
[`(div ,(? expr? e0) ,(? expr? e1)) #t] | |
[`(not ,(? expr? e-guard)) #t] | |
[`(if ,(? expr? e0) ,(? expr? e1) ,(? expr? e2)) #t] | |
[_ #f])) | |
(define (evaluate e) | |
;; e satisfies expr?, return a number? | |
(match e | |
[(? integer? n) n] | |
[`(plus ,(? expr? e0) ,(? expr? e1)) (+ (evaluate e0) (evaluate e1))] | |
[`(div ,(? expr? e0) ,(? expr? e1)) (/ (evaluate e0) (evaluate e1))] | |
;; remember: 0 is "false", anything nonzero is "true" | |
[`(not ,(? expr? e-guard)) | |
(if (equal? 0 (evaluate e-guard)) | |
;; it is 0, return something nonzero | |
1 | |
;; it is nonzero, return 0 | |
0)] | |
[`(if ,(? expr? e0) ,(? expr? e1) ,(? expr? e2)) | |
(if (equal? 0 (evaluate e0)) | |
;; it is false, evaluate the false branch | |
(evaluate e2) | |
;; it is true, evaluate the true branch | |
(evaluate e1))] | |
[_ #f])) | |
(define (command? c) | |
(match c | |
;; swap x and y's value | |
[`(swap ,(? symbol? x) ,(? symbol? y)) #t] | |
;; assign x to the value of y | |
[`(assign ,(? symbol? x) ,(? number? y)) #t] | |
;; assign x to the value of y+z | |
[`(add ,(? symbol? x) ,(? symbol? y) ,(? symbol? z)) #t] | |
[_ #f])) | |
;; "interpret" a single command: return the resulting hash. Swap | |
;; should swap the values in x and y. Assign should assign to the | |
;; value x. Add should assign to the value x with the value of y plus | |
;; the value of z. | |
(define (interpret-command e h) | |
(match e | |
[`(swap ,x ,y) | |
(hash-set (hash-set h x (hash-ref h y)) y (hash-ref h x))] | |
[`(assign ,x ,y) | |
(hash-set h x y)] | |
[`(add ,x ,y ,z) | |
(hash-set h x (+ (hash-ref h y) (hash-ref h z)))])) | |
;; interpret each command one at a time | |
(define (interpret-commands es) | |
(define (h hsh lst) | |
(match lst | |
['() hsh] | |
[`(,hd . ,tl) (h (interpret-command hd hsh) tl)])) | |
(h (hash) es)) | |
(define (interpret-commands-again-using-foldl es) | |
(foldl (λ (next-cmd h) (interpret-command next-cmd h)) | |
(hash) | |
es)) | |
(define (newlines n) | |
(cond | |
[(equal? n 0) ""] | |
[(not (equal? n 0)) (string-append "\n" (newlines (- n 1)))])) | |
#;(define (newlines n) | |
(match n | |
[0 ""] | |
[n (string-append "\n" (newlines (- n 1)))])) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment