#lang racket (provide (all-defined-out)) ;; This assignment should be completed individually. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; I pledge on my honor that I have not given or received any ;; unauthorized assistance on this assignment. ;; ;; Name: TODO ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; These are a series of finger-exercise programs to help you: ;; - learn a bit of Racket ;; - practice with structural recursion and type-based program design ;; This style of programming will be used throughout the course, ;; now is the time to master the style! ;; If you've mastered the style, you can write these programs on auto-pilot. ;; If you haven't, you will struggle. (module+ test (require rackunit)) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; Numeric functions ;; Natural -> Natural ;; Compute n! (define (fact n) (fact-iter 1 n)) (define (fact-iter acc n) (if (= n 0) acc (fact-iter (* n acc) (- n 1)))) (module+ test (check-equal? (fact 0) 1) (check-equal? (fact 1) 1) (check-equal? (fact 2) 2) (check-equal? (fact 5) 120)) ;; Natural -> Natural ;; Compute nth Fibonnaci number (define (fib n) (fib-iter 1 0 n)) (define (fib-iter a b n) (if (= n 0) b (fib-iter (+ a b) a (- n 1)))) (module+ test (check-equal? (fib 0) 0) (check-equal? (fib 1) 1) (check-equal? (fib 2) 1) (check-equal? (fib 3) 2) (check-equal? (fib 4) 3) (check-equal? (fib 5) 5) (check-equal? (fib 6) 8) (check-equal? (fib 20) 6765)) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; String functions ;; Read up on string functions in Racket to implement these. ;; String String -> String ;; Select the longer of the two strings (or first if same length) (define (longer s1 s2) (if (> (string-length s2) (string-length s1)) s2 s1)) (module+ test (check-equal? (longer "" "") "") (check-equal? (longer "abc" "d") "abc") (check-equal? (longer "a" "bcd") "bcd") (check-equal? (longer "ab" "cd") "ab")) ;; String -> [Listof String] ;; Explode a string into a list of length-1 strings (define (explode s) (map string (string->list s))) (module+ test (check-equal? (explode "") '()) (check-equal? (explode "a") '("a")) (check-equal? (explode "abc") '("a" "b" "c"))) ;; String -> [Listof [List String String]] ;; Compute list of bigrams (pairs of adjacent letters) in a string (define (bigrams s) (match (explode s) ['() '()] [(list a) '()] [(cons x xs) (append (list (list x (car xs))) (bigrams (string-join xs "")))])) (module+ test (check-equal? (bigrams "") '()) (check-equal? (bigrams "a") '()) (check-equal? (bigrams "ab") '(("a" "b"))) (check-equal? (bigrams "abc") '(("a" "b") ("b" "c")))) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; Simple list functions ;; Follow this template for functions on lists of numbers where appropriate. ;; [Listof Number] ... -> ... #; (define (lon-template ls ...) (match ls ['() ...] [(cons n ls) (... n (lon-template ls ...) ...)])) ;; [Listof Number] -> Natural ;; Compute the length of given list of numbers (define (length-lon ls) (match ls ['() 0] [(cons n ls) (+ 1 (length-lon ls))])) (module+ test (check-equal? (length-lon '()) 0) (check-equal? (length-lon '(1)) 1) (check-equal? (length-lon '(2)) 1) (check-equal? (length-lon '(1 2)) 2)) ;; [Listof Number] -> Number ;; Compute the sum of given list of numbers (define (sum ls) (match ls ['() 0] [(cons n ls) (+ n (sum ls))])) (module+ test (check-equal? (sum '()) 0) (check-equal? (sum '(1)) 1) (check-equal? (sum '(2)) 2) (check-equal? (sum '(1 2)) 3)) ;; [Listof Number] [Listof Number] -> [Listof Number] ;; Compute the pairwise sum of given list of numbers ;; ASSUME: lists have equal length (define (zip-add ls1 ls2) (match ls1 ['() '()] [(cons n1 ls1) (append (list (+ n1 (car ls2))) (zip-add ls1 (cdr ls2)))])) (module+ test (check-equal? (zip-add '() '()) '()) (check-equal? (zip-add '(1) '(2)) '(3)) (check-equal? (zip-add '(1 3) '(2 4)) '(3 7))) ;; [Listof Number] [Listof Number] -> [Listof [List Number Number]] ;; Compute the pairwise list of given list of numbers ;; ASSUME: lists have equal length (define (zip-lon ls1 ls2) (match ls1 ['() '()] [(cons n1 ls1) (append (list (list n1 (car ls2))) (zip-lon ls1 (cdr ls2)))])) (module+ test (check-equal? (zip-lon '() '()) '()) (check-equal? (zip-lon '(1) '(2)) '((1 2))) (check-equal? (zip-lon '(1 3) '(2 4)) '((1 2) (3 4)))) ;; [Pairof Real [Listof Real]] -> Real ;; Compute max element of non-empty list of numbers (define (max-lon xs) (match xs [(cons x '()) x] [(cons x xs) #:when (> x (max-lon xs)) x] [(cons x xs) (max-lon xs)])) (module+ test (check-equal? (max-lon '(1)) 1) (check-equal? (max-lon '(1 2)) 2) (check-equal? (max-lon '(2 1)) 2) (check-equal? (max-lon '(2 3 1)) 3)) ;; [Listof Real] -> [Listof Real] ;; Sort list into ascending order ;; HINT: do insertion sort by writing and using the helper below (define (sort-asc xs) (match xs ['() '()] [(cons x xs) (insert-asc x (sort-asc xs))])) (module+ test (check-equal? (sort-asc '()) '()) (check-equal? (sort-asc '(1)) '(1)) (check-equal? (sort-asc '(1 2)) '(1 2)) (check-equal? (sort-asc '(2 1)) '(1 2)) (check-equal? (sort-asc '(2 3 1)) '(1 2 3))) ;; Real [Listof Real] -> [Listof Real] ;; Insert number into sorted list ;; ASSUME: given list is sorted in ascending order (define (insert-asc n xs) (match xs ['() (list n)] [(list x) (if (> n x) (append (list x) (list n)) (cons n (list x)))] [(cons x xs) #:when (> n x) (cons x (insert-asc n xs))] [(cons x xs) (cons n (cons x xs))])) (module+ test (check-equal? (insert-asc 5 '()) '(5)) (check-equal? (insert-asc 5 '(7)) '(5 7)) (check-equal? (insert-asc 5 '(3)) '(3 5))) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; Polymorphic list functions ;; ∀ (α) (α -> Real) [Pairof α [Listof α]] -> α ;; Find element that minimizes the given measure (take first if more than one) (define (minimize f xs) (min-iter (f (car xs)) (car xs) f (cdr xs))) ;; Helper function (define (min-iter fx x f xs) (cond [(= (length-lon xs) 0) x] [(<= fx (f (car xs))) (min-iter fx x f (cdr xs))] [else (min-iter (f (car xs)) (car xs) f (cdr xs))])) (module+ test (check-equal? (minimize abs '(1 -2 3)) 1) (check-equal? (minimize string-length '("abc" "d" "efg")) "d") (check-equal? (minimize string-length '("abc" "d" "ef" "g")) "d")) ;; ∀ (α) (α α -> Boolean) [Listof α] -> [Listof α] ;; Sort list in ascending order according to given comparison ;; ENSURE: result is stable (define (sort < xs) (match xs ['() '()] [(cons n ls) (append (sort < (for/list ([i ls] #:when (< i n)) i)) (list n) (sort < (for/list ([i ls] #:when (not (< i n))) i)))])) (module+ test (check-equal? (sort < '(1 -2 3)) '(-2 1 3)) (check-equal? (sort string<? '("d" "abc" "efg")) '("abc" "d" "efg")) (check-equal? (sort (λ (s1 s2) (< (string-length s1) (string-length s2))) '("efg" "d" "abc")) '("d" "efg" "abc"))) ;; ∀ (α β) [Listof α] [Listof β] -> [Listof [List α β]] ;; Zip together lists into a list of lists ;; ASSUME: lists are the same length (define (zip as bs) (match as ['() '()] [(cons a as) (append (list (list a (car bs))) (zip as (cdr bs)))])) (module+ test (check-equal? (zip '() '()) '()) (check-equal? (zip '(1) '(2)) '((1 2))) (check-equal? (zip '(1 3) '(2 4)) '((1 2) (3 4))) (check-equal? (zip '(1 3) '("a" "b")) '((1 "a") (3 "b")))) ;; ∀ (α) (Listof (α -> α)) -> (α -> α) ;; Compose a list of functions into a single function ;; ((pipe (list f1 f2 f3)) x) ≡ (f1 (f2 (f3 x))) (define (pipe fs) (apply compose fs)) (module+ test (check-equal? ((pipe (list number->string sqr add1)) 5) "36") (check-equal? ((pipe (list number->string add1 sqr)) 5) "26") (check-equal? ((pipe (list string-length number->string add1 sqr)) 5) 2)) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; Peano numbers ;; Unary encoding of the natural numbers ;; type N = (Z) | (S N) ;; We will represent Peano numbers in racket with structures. (struct Z () #:transparent) (struct S (N) #:transparent) ;; this structure 'S' should be recursive - ;; it's parameter should be another Peano Number ;; Natural -> N ;; Convert natural to Peano (define (nat->peano n) (if (= n 0) (Z) (S (nat->peano (- n 1))))) (module+ test (check-equal? (nat->peano 0) (Z)) (check-equal? (nat->peano 1) (S (Z))) (check-equal? (nat->peano 2) (S (S (Z)))) (check-equal? (nat->peano 3) (S (S (S (Z)))))) ;; N -> Natural ;; Convert Peano to natural (define (peano->nat n) (match n [(Z) 0] [(S N) (+ 1 (peano->nat N))])) (module+ test (check-equal? (peano->nat (Z)) 0) (check-equal? (peano->nat (S (Z))) 1) (check-equal? (peano->nat (S (S (Z)))) 2) (check-equal? (peano->nat (S (S (S (Z))))) 3)) ;; Do not use conversions to implement the following functions ;; N N -> N ;; Add two Peano numbers together (define (plus n1 n2) (match n1 [(Z) n2] [(S N) (S (plus N n2))])) (module+ test (check-equal? (plus (Z) (Z)) (Z)) (check-equal? (plus (Z) (S (Z))) (S (Z))) (check-equal? (plus (S (Z)) (Z)) (S (Z))) (check-equal? (plus (S (Z)) (S (Z))) (S (S (Z))))) ;; N N -> N ;; Multiply two Peano numbers together (define (mult n1 n2) (match n2 [(Z) (Z)] [(S N) (plus n1 (mult n1 N))])) (module+ test (check-equal? (mult (Z) (Z)) (Z)) (check-equal? (mult (Z) (S (Z))) (Z)) (check-equal? (mult (S (Z)) (Z)) (Z)) (check-equal? (mult (S (Z)) (S (Z))) (S (Z)))) ;; ∀ (α) N (α -> α) -> (α -> α) (define (iter n f) (match n [(Z) (lambda (a) a)] [(S N) (compose (lambda (a) (f a)) (iter N f))])) (module+ test ;; Natural -> Natural (define (succ n) (+ n 1)) (check-equal? ((iter (Z) succ) 0) 0) (check-equal? ((iter (S (Z)) succ) 0) 1) (check-equal? ((iter (S (S (Z))) succ) 0) 2) ;; Boolean -> Boolean (define (neg b) (not b)) (check-equal? ((iter (Z) neg) #t) #t) (check-equal? ((iter (S (Z)) neg) #t) #f) (check-equal? ((iter (S (S (Z))) neg) #t) #t)) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; Binary trees of numbers ;; Write test cases for each function (before writing code!). ;; type BTNumber = ;; | (leaf) ;; | (node Number BTNumber BTNumber) ;; We will represent Binary trees in racket with structures. (struct leaf () #:transparent) (struct node (n left right) #:transparent) ;; this structure 'node' should be recursive - ;; it's last two parameters should be binary trees ;; Follow this template for functions on binary trees. ;; bt ... -> ... #; (define (btn-template n) (match n [(leaf) ...] [(node n left right) (... n (btn-template left ...) (btn-template right ...) ...)])) ;; BTNumber -> Natural ;; Compute the height of a binary tree (leaf has height 0) (define (btn-height bt) (match bt [(leaf) 0] [(node n left right) (+ 1 (max (btn-height left) (btn-height right)))])) (module+ test (check-equal? (btn-height (leaf)) 0) (check-equal? (btn-height (node 5 (leaf) (leaf))) 1) (check-equal? (btn-height (node 5 (node 1 (leaf) (leaf)) (leaf))) 2)) ;; BTNumber -> Natural ;; Count the nodes of a binary tree (define (btn-count bt) (match bt [(leaf) 0] [(node n left right) (+ 1 (btn-count left) (btn-count right))])) (module+ test (check-equal? (btn-count (leaf)) 0) (check-equal? (btn-count (node 5 (leaf) (leaf))) 1) (check-equal? (btn-count (node 5 (node 1 (leaf) (leaf)) (leaf))) 2)) ;; BTNumber -> BTNumber ;; Compute the mirror image of binary tree (define (btn-mirror bt) (match bt [(leaf) (leaf)] [(node n left right) (node n right left)])) (module+ test (check-equal? (btn-mirror (leaf)) (leaf)) (check-equal? (btn-mirror (node 5 (leaf) (leaf))) (node 5 (leaf) (leaf))) (check-equal? (btn-mirror (node 5 (node 1 (leaf) (leaf)) (leaf))) (node 5 (leaf) (node 1 (leaf) (leaf))))) ;; BTNumber -> Number ;; Sum the numbers of a binary tree (define (btn-sum bt) (match bt [(leaf) 0] [(node n left right) (+ n (btn-sum left) (btn-sum right))])) (module+ test (check-equal? (btn-sum (leaf)) 0) (check-equal? (btn-sum (node 5 (leaf) (leaf))) 5) (check-equal? (btn-sum (node 5 (node 1 (leaf) (leaf)) (leaf))) 6)) ;; Natural Number -> BTNumber ;; Generate a full bt of height h containing given number n at each node (define (btn-gen-full h n) (match h [0 (leaf)] [h (node n (btn-gen-full (- h 1) n) (btn-gen-full (- h 1) n))])) (module+ test (check-equal? (btn-gen-full 0 8) (leaf)) (check-equal? (btn-gen-full 1 8) (node 8 (leaf) (leaf))) (check-equal? (btn-gen-full 2 8) (node 8 (node 8 (leaf) (leaf)) (node 8 (leaf) (leaf))))) ;; BTNumber Number -> Boolean ;; Does the bt contain number n? (define (btn-contains? bt n) (match bt [(leaf) #f] [(node num left right) (if (= n num) #t (or (btn-contains? left n) (btn-contains? right n)))])) (module+ test (check-equal? (btn-contains? (leaf) 8) #f) (check-equal? (btn-contains? (node 8 (leaf) (leaf)) 8) #t) (check-equal? (btn-contains? (node 5 (leaf) (leaf)) 8) #f) (check-equal? (btn-contains? (node 5 (leaf) (node 8 (leaf) (leaf))) 8) #t)) ;; BTNumber -> [Listof Number] ;; Generate the list of numbers in bt in preorder ;; HINT: append is a function that might be helpful (define (btn-preorder btn) (match btn [(leaf) '()] [(node n left right) (append (list n) (btn-preorder left) (btn-preorder right))])) (module+ test (check-equal? (btn-preorder (leaf)) '()) (check-equal? (btn-preorder (node 5 (leaf) (leaf))) '(5)) (check-equal? (btn-preorder (node 5 (node 8 (leaf) (leaf)) (node 9 (leaf) (leaf)))) '(5 8 9))) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; Representing expressions ;; Here is a datatype definition for representing expressions in a small ;; functional programming language: ;; type SExpr = ;; | Integer ;; | Boolean ;; | Variable ;; | (list e1 e2) ;; | (list 'lambda (list (? symbol? x)) e) ;; type Variable = Symbol ;; Some examples of valid programs: ;; 34 ;; #t ;; 'x ;; '((lambda (x) x) 17) ;; The above definition is easy to read, but can be troublesome to work with. ;; Instead of using the SExpr representation, we will transform it into a ;; more structured representation (this will be our AST). ;; type Expr = ;; | (Int Integer) ;; | (Bool Boolean) ;; | (Var Variable) ;; | (App Expr Expr) ;; | (Lam Variable Expr) ;; type Variable = Symbol ;; We will be using these structures: (struct Int (i) #:transparent) (struct Bool (b) #:transparent) (struct Var (v) #:transparent) (struct App (e1 e2) #:transparent) (struct Lam (x e) #:transparent) ;; After converting the above SExpr programs into Expr representation: ;; (Int 34) ;; (Bool #t) ;; (Var 'x) ;; (App (Lam 'x (Var 'x)) (Int 17)) ;; We already wrote a helper function to put SExpr programs into this ;; new representation. Feel free to play around with this in your REPL. ;; SExpr -> Expr (define (sexpr->expr s) (match s [(? integer? s) (Int s)] [(? boolean? b) (Bool b)] [(? symbol? v) (Var v)] [(list e1 e2) (App (sexpr->expr e1) (sexpr->expr e2))] [(list 'lambda (list (? symbol? x)) e) (Lam x (sexpr->expr e))])) ;; Below is a template of how to traverse this AST: #; (define (expr-template e) (match e [(Int i) ...] [(Bool b) ...] [(Var v) ...] [(App e1 e2) (... (expr-template e1) (expr-template e2) ...)] [(Lam x e) (... x (expr-template e) ...)])) ;; Note: for each of the following functions, the order of elements ;; and whether repetitions occur is left unspecified and up to you. ;; The tests are written using this function to take this in to ;; account. (module+ test ;; [Listof a] [Listof a] -> Boolean ;; Are the two lists equal up to re-ordering and repetition? (define (list-set-equal? xs ys) (equal? (list->set xs) (list->set ys))) (check-equal? (list-set-equal? '() '()) #t) (check-equal? (list-set-equal? (list 1 2) (list 2 1)) #t) (check-equal? (list-set-equal? (list 1 1 2) (list 2 2 1)) #t) (check-equal? (list-set-equal? (list 1 1 2) (list 2 3 2 1)) #f)) ;; Expr -> [Listof Integer] ;; Computes a list of all integer literals that appear in the expression (define (expr-integers e) (match e [(Int i) (list i)] [(Bool b) '()] [(Var v) '()] [(App e1 e2) (append (expr-integers e1) (expr-integers e2))] [(Lam x e) (append (expr-integers e) '())])) (module+ test (check list-set-equal? (expr-integers (sexpr->expr 123)) '(123)) (check list-set-equal? (expr-integers (sexpr->expr 'x)) '()) (check list-set-equal? (expr-integers (sexpr->expr '((lambda (x) x) 123))) '(123)) (check list-set-equal? (expr-integers (sexpr->expr '((lambda (x) 42) 123))) '(123 42))) ;; Expr -> [Listof Variable] ;; Compute a list of all lambda-bound variables in the expression (define (expr-lambda-vars e) (match e [(Int i) '()] [(Bool b) '()] [(Var v) '()] [(App e1 e2) (append (expr-lambda-vars e1) (expr-lambda-vars e2))] [(Lam x e) (append (list x) (expr-lambda-vars e))])) (module+ test (check list-set-equal? (expr-lambda-vars (sexpr->expr 123)) '()) (check list-set-equal? (expr-lambda-vars (sexpr->expr 'x)) '()) (check list-set-equal? (expr-lambda-vars (sexpr->expr '((lambda (x) x) 123))) '(x)) (check list-set-equal? (expr-lambda-vars (sexpr->expr '((lambda (x) 42) 123))) '(x))) ;; Expr -> [Listof Variable] ;; Compute a list of all free variables, i.e. variables which occur outside ;; of any lambda that binds them. (define (expr-free-vars e) (match e [(Int i) '()] [(Bool b) '()] [(Var v) (list v)] [(App e1 e2) (append (expr-free-vars e1) (expr-free-vars e2))] [(Lam x e) (remove* (list x) (expr-free-vars e))])) (module+ test (check list-set-equal? (expr-free-vars (sexpr->expr 123)) '()) (check list-set-equal? (expr-free-vars (sexpr->expr 'x)) '(x)) (check list-set-equal? (expr-free-vars (sexpr->expr '((lambda (x) x) 123))) '()) (check list-set-equal? (expr-free-vars (sexpr->expr '((lambda (x) 42) 123))) '()))