In this first machine problem you will be implementing a number of different Racket functions that make use of recursion (tail and non-tail), manipulate lists, and perform pattern matching.
All the code you write for this machine problem will go into the "mp1.rkt" file, found in the private source repository created when you accepted my GitHub invitation. In that file you will find stubs for each of the programming exercises described below.
Note that you may also refer to the assignment writeup found in your repository.
Each exercise below requires you to implement a single function. Unless explicitly mentioned, you should not use any built-in functions or special forms not covered in the first three lectures (01-intro, 02-functions, 03-recursion). If you wish, however, you may implement additional helper functions on top of the required ones.
Note that some exercises specify whether your solution should be tail-recursive (or not). If unspecified, you may do either.
Each exercise is worth 5 points, for a total of 40 possible points.
iexpt: Performs integer exponentiation (assuming positive, integer
arguments). Given arguments n and e, computes ne. E.g.,
> (iexpt 2 10)
1024
> (iexpt 5 3)
125
poly-eval: Given coeffs and x, where coeffs is a list of integer
coefficients (a, b, c, ...) and x is an integer, computes the value
of the polynomial ax0 + bx1 + cx2 + ...
E.g.,
> (poly-eval '(2 3 4) 2)
24
> (poly-eval '() 10)
0
> (poly-eval '(8 4 2 1) 4)
120
Your implementation should be tail-recursive. You may use iexpt from the
previous exercise.
concatenate: Given zero or more list arguments, concatenates all the
elements of the argument lists into a single list. E.g.,
> (concatenate '(1 2 3) '(hi bye) '(4 5 6))
'(1 2 3 hi bye 4 5 6)
> (concatenate '(a (b) c) '() '((d) (42 43)))
'(a (b) c (d) (42 43))
Your implementation should be tail-recursive. Additionally, when building
your result list, you should only use cons, and your implementation should
have linear runtime w.r.t. the total number of elements. Hint: it might be
helpful to use reverse at some point in your implementation!
merge: Takes two argument lists, both of which contain only integers and
are in ascending order. Returns a single list containing all the integers,
sorted in ascending order. E.g.,
> (merge '(1 4 8 10) '(2 3 7 13))
'(1 2 3 4 7 8 10 13)
Your implementation should not be tail-recursive (we'll do that next).
merge-tail: re-implement the previous function, but this time your
implementation should be tail-recursive. As with your implementation of
concatenate, you may only use the cons function to build your result
list, and it should have linear runtime w.r.t. the total number of integers.
run-length-encode: returns a run-length encoding of the argument list.
Run-length encoding stores each value together with the number of times it
appears (contiguously) — in this way, a value that is repeated multiple
times can be more efficiently represented. E.g.,
> (run-length-encode '(a a a a a b b b))
'((a 5) (b 3))
> (run-length-encode '(a a a b a a c c c b b))
'((a 3) (b 1) (a 2) (c 3) (b 2))
Your implementation should be tail recursive. You may assume that adjacent
elements can be compared for equality using equal?.
run-length-decode: given a run-length encoded list argument, returns the
original list. E.g.,
> (run-length-decode '((a 5) (b 3)))
'(a a a a a b b b)
> (run-length-decode '((5 3) (12 2)))
'(5 5 5 12 12)
label-sexp: returns a "labeled" version of the argument sexp. The labeling
is based on a simplified understanding of the Racket language, where a sexp
is one of:
42x, num+, *, /, or
-, and followed by two argument sexps; e.g., (+ 4 5), (* x (+ 1 2))(foo 42), (bar (+ 5 (foo 10)))The labeled version of a sexp will enclose each of the original components
within a list with a label, which is one of int, var, arith, op,
funcall, or name. E.g., (indentation added for clarity)
> (label-sexp 42)
'(int 42)
> (label-sexp 'x)
'(var x)
> (label-sexp '(+ 1 2))
'(arith (op +) (int 1) (int 2))
> (label-sexp '(+ 1 (* x 2)))
'(arith (op +)
(int 1)
(arith (op *)
(var x)
(int 2)))
> (label-sexp '(foo 42))
'(funcall (name foo) (int 42))
> (label-sexp '(foo (+ 5 (foo 10))))
'(funcall (name foo)
(arith (op +)
(int 5)
(funcall (name foo) (int 10))))
You may find it quite helpful to use match and quasiquoting (to construct
your labeled expressions). We've provided you with a bit of starter code.
We've provided you with tests for every exercise in the "mp1-tests.rkt" source file. If you open the file you'll find that there are a bunch of definitions that looks like this:
(test-case "Integer exponentiation"
(check-equal? (iexpt 100 0) 1)
(check-equal? (iexpt 100 1) 100)
(check-equal? (iexpt 5 2) 25)
(check-equal? (iexpt 5 3) 125)
(check-equal? (iexpt 2 10) 1024))
This defines a test case (here, for the iexpt function). The check-equal?
calls are assertions. If they fail, they will produce errors that looks like
this:
--------------------
Integer exponentiation
. FAILURE
name: check-equal?
location: mp1-test.rkt:8:11
actual: 2
expected: 1
--------------------
You can run the tests by loading the file in DrRacket and evaluating it. Note that while passing all the tests is a good indication that your solutions are on the right track, we don't guarantee exhaustive test coverage, nor that passing all tests will results in 100% on the assignment! (E.g., we will be checking for tail-recursive implementations manually).
When you are done with your work, simply commit your changes and push them to our shared private GitHub repository. Please note that your submission date will be based on your most recent push (unless you let us know to grade an earlier version).