1 Assignment 1: Recursion and Higher-Order Functional Abstractions
Recursion is the root of computation since it trades description for time.
——Alan Perlis
Guidelines for this assignment
Solutions must be naturally recursive (unless not possible), or credit will not be given.
You may not use built-in procedures that handle the bulk of the work. For example, you may not use the append function from Racket. But once you have defined your own append for problem 8, feel free to use it for other problems. If you use the builtin append from Racket, even if your code passes all the tests in our autograder, you will get 0 for this problem.
Lists are assumed to be flat lists and not nested lists unless specified otherwise.
The objective is not simply to write programs that get the correct answers; it is to write answers in the style of programs written in class.
Make sure to title your file a1.rkt when you submit your homework.
Please feel free to submit your work as many times as you wish, we will grade the last submission prior to the due date (and time).
Assignment
Write the following recursive Racket procedures. Place all of your code in a file named a1.rkt, and submit it via the autograder. Please make sure your file has exactly this filename, and that it runs, before submitting.
Please read through our Course policies before beginning the rest of the assignment.
Define and test a procedure countdown that takes a natural number and returns a list of the natural numbers less than or equal to that number, in descending order.
> (countdown 5) (5 4 3 2 1 0) Define and test a procedure insertL that takes two symbols and a list and returns a new list with the second symbol inserted before each occurrence of the first symbol. For this and later questions, these functions need only hold over eqv?-comparable structures.
> (insertL 'x 'y '(x z z x y x)) (y x z z y x y y x) Define and test a procedure remv-1st that takes a a symbol and a list and returns a new list with the first occurrence of the symbol removed.
> (remv-1st 'x '(x y z x)) (y z x) > (remv-1st 'y '(x y z y x)) (x z y x) > (remv-1st 'z '(a b c)) (a b c) Define and test a procedure remove-from that takes a predicate and a list and returns a new list containing the members that do not satisfy the predicate. A predicate is a procedure that takes a single argument and returns either #t or #f. The number? predicate, for example, returns #t if its argument is a number and #f otherwise. The argument satisfies the predicate, then, if the predicate returns #t for that argument.
> (remove-from even? '(1 2 3 4 5 6)) (1 3 5) Define and test a procedure map that takes a procedure p of one argument and a list ls and returns a new list containing the results of applying p to the members of ls. Do not use Racket’s built-in map in your definition.
> (map sub1 '(1 2 3 4)) (0 1 2 3) Define and test a procedure zip that takes two lists and forms a new list, each member of which is a pair formed by combining the corresponding members of the two input lists. If the two lists are of uneven length, then drop the tail of the longer one.
> (zip '(1 2 3) '(a b c)) ((1 . a) (2 . b) (3 . c)) > (zip '(1 2 3 4 5 6) '(a b c)) ((1 . a) (2 . b) (3 . c)) > (zip '(1 2 3) '(a b c d e f)) ((1 . a) (2 . b) (3 . c)) Define and test a procedure list-index-ofv that takes a member and a list and returns the (base 0) index of that member in the list. A list missing that member will be considered bad data.
> (list-index-ofv 'x '(x y z x x)) 0 > (list-index-ofv 'x '(y z x x)) 2 Define and test a procedure append that takes two lists, ls1 and ls2, and appends ls1 to ls2.
> (append '(42 120) '(1 2 3)) (42 120 1 2 3) > (append '(a b c) '(cat dog)) (a b c cat dog) Define and test a procedure reverse that takes a list and returns the reverse of that list.
> (reverse '(a 3 x)) (x 3 a) Define and test a procedure repeat that takes a list and a natural number and returns a new list with repeating sequence of the input list. The number of times the new list repeats is equal to the natural number, which is the second argument.
> (repeat '(4 8 11) 4) '(4 8 11 4 8 11 4 8 11 4 8 11) Define and test a procedure same-lists* that takes two lists, possibly nested and returns #t if they are equal and #f otherwise.
> (same-lists* '() '()) #t > (same-lists* '(1 2 3 4 5) '(1 2 3 4 5)) #t > (same-lists* '(1 2 3 4) '(1 2 3 4 5)) #f > (same-lists* '(a (b c) d) '(a (b) c d)) #f > (same-lists* '((a) b (c d) d) '((a) b (c d) d)) #t The expressions '(a b) and '(a . (b . ())) are equivalent. Using this knowledge, rewrite the expression '((w x) y (z)) using as many dots as possible. Be sure to test your solution using Racket’s equal? predicate. (You do not have to define a rewrite procedure; just rewrite the given expression by hand and place it in a comment.)
Define and test a procedure binary->natural that takes a flat list of 0s and 1s representing an unsigned binary number in reverse bit order and returns that number. For example:
> (binary->natural '()) 0 > (binary->natural '(0 0 1)) 4 > (binary->natural '(0 0 1 1)) 12 > (binary->natural '(1 1 1 1)) 15 > (binary->natural '(1 0 1 0 1)) 21 > (binary->natural '(1 1 1 1 1 1 1 1 1 1 1 1 1)) 8191 Define division using natural recursion. Your division function, div, need only work when the second number evenly divides the first (which is, for the divisible abelian group that’s a subgroup of Nat). Division by zero is of course bad data.
> (div 25 5) 5 > (div 36 6) 6 Define a function append-map that, similar to map, takes both a procedure p of one argument, a list of inputs ls, and applies p to each of the members of ls. Like our definition of countdown, p takes one argument and yields a list, each of which is appended together. Do not use Racket’s built-in append-map in your definition.
> (append-map countdown (countdown 5)) (5 4 3 2 1 0 4 3 2 1 0 3 2 1 0 2 1 0 1 0 0) Define a function set-difference that takes two flat sets (each of which has no duplicate members) s1 and s2 and returns a list (a set) containing all the members in s1 that are not in s2.
> (set-difference '(1 2 3 4 5) '(2 6 4 8)) (1 3 5)
Brainteasers
Here is the Ackermann function we showed in class on Thursday, Aug 29th:
(define G (λ (i) (cond ((zero? i) (λ (n m) (cond ((zero? m) n) (else (add1 ((G 0) n (sub1 m))))))) ((zero? (sub1 i)) (λ (n m) (cond ((zero? m) 0) (else ((G 0) n ((G 1) n (sub1 m))))))) (else (λ (n m) (cond ((zero? m) 1) (else ((G (sub1 i)) n ((G i) n (sub1 m)))))))))) By a few steps, we can simplify the definition above to get the definition below:
(define G (λ (i) (λ (n m) (cond ((zero? m) (cond ((zero? i) n) ((zero? (sub1 i)) 0) (else 1))) ((zero? i) (add1 ((G 0) n (sub1 m)))) (else ((G (sub1 i)) n ((G i) n (sub1 m)))))))) Show the intermediate steps for simplifying G. You can name each intermediate definition as G-1, G-2, G-3, G-4, etc. Feel free to discuss this question with your classmates, but be sure to submit your own solution.
In mathematics, the power set of any set S, denoted P(S), is the set of all subsets of S, including the empty set and S itself.
S = \{x, y, z\}\\ \mathcal{P}(S) = \{\{\}, \{x\}, \{y\}, \{z\}, \{x,y\}, \{x,z\}, \{y,z\}, \{x,y,z\}\}.The procedure powerset takes a list and returns the power set of the members in the list. The exact order of your lists may differ, which for this problem is acceptable.
> (powerset '(3 2 1)) ((3 2 1) (3 2) (3 1) (3) (2 1) (2) (1) ()) > (powerset '()) (()) The cartesian-product is defined over a list of sets (again simply lists that by our agreed upon convention don’t have duplicates). The result is a list of tuples (i.e. lists). Each tuple has in the first position a member of the first set, in the second position a member of the second set, etc. The output list should contain all such combinations. The exact order of your tuples may differ, which for this problem is acceptable.
> (cartesian-product '((5 4) (3 2 1))) ((5 3) (5 2) (5 1) (4 3) (4 2) (4 1)) Consider a function f below that takes a positive integer n
f(n) = \begin{cases} n / 2 & \text{if}~n \equiv 0~\text{(mod 2)} \\ 3n + 1 & \text{if}~n \equiv 1~\text{(mod 2)} \end{cases}Your task is to define a function C with letrec. C should be a function which, when given a positive integer as an input, should always return 1. It behaves in the way f is defined above. This function f is named the Collatz function for the mathematician Lothar Collatz who posed the conjecture in 1937. You can see its definition (without letrec) in The Little Schemer, page 155.
> (C 12) 1 > (C 120) 1 > (C 9999) 1
Just Dessert
A quine is a program whose output is the listings (i.e. source code) of the original program. In Racket, 5 and #t are both quines.
> 5 5 > #t #t We will call a quine in Racket that is neither a number nor a boolean an interesting Racket quine. Below is an interesting Racket quine.
> ((lambda (x) (list x (list 'quote x))) '(lambda (x) (list x (list 'quote x)))) ((lambda (x) (list x (list 'quote x))) '(lambda (x) (list x (list 'quote x)))) Racket’s standard printing convention will prepend a quote to a list. You can hide the first quote by putting the following two lines of code before your quine:
(print-reader-abbreviations #f) (print-as-expression #f) Define your own interesting Racket quine. The following should then be true.
> (equal? quine (eval quine)) #t > (equal? quine (eval (eval quine))) #t Not every Racket list is a quine. Make sure to use the above tests.