Homework 6

Out: 11/16, due by 11:59pm 11/27 (Mon after Thanksgiving)

Erratum:

The command-line switch for invoking mzscheme to run the hw6test.ss test script has changed, from "-f" to "-t".

Also, the default version of mzscheme on GL seems to be missing some libraries. You can instead run a more complete (and incidentally, much more up-to-date) version from my home directory:
/afs/umbc.edu/users/p/a/park/pub/racket/bin/mzscheme. You can use a command like:

ln -s /afs/umbc.edu/users/p/a/park/pub/racket/bin/mzscheme mzscheme6

to then run it by just typing "./mzscheme6"

Scheme II

This assignment gives you a chance actually write some challenging Scheme functions. Unless otherwise specified (or suggested by the examples) you can assume that reasonable arguments are given to your functions. In other words, you need not add code to check the arguments provided. Obsessive compulsives are free to do so, of course.

Getting ready

This assignment assumes that you successfully used the mzscheme system on the GL machines, or that alternatively, you downloaded Racket Scheme from the web and have tested it on your own machine.

Your assignment

(1) chop and unchop

You will write a pair of complementary Scheme functions named chop and unchop. Chop takes a proper list L with at least one element and returns a list like L but without it's last element. (recall that a proper list is one that ends in a null.) Unchop takes two arguments, a proper list L (possibly empty) and an arbitrary s-expression X and returns a list like L but with X added as it's last element. Here is an example of their use.

gl3% mzscheme
Welcome to Racket v5.1.3.
> (load "hw6.ss")
> (chop '(1 2 3))
(1 2)
> (chop '(1))
()
> (chop '())
cdr: expects argument of type <pair>; given ()

=== context ===
/Users/Park/Sites/331s13/hw/hw6/hw6.ss:7:0: chop
/opt/racket/collects/racket/private/misc.rkt:85:7

> (unchop '() 100)
(100)
> (unchop '(1 2 3) 'infinity)
(1 2 3 infinity)
> (unchop '(1 2 3) '(47))
(1 2 3 (47))

(Note: there is an error message shown in the example above. Your own code might produce a completely different error message, depending on your implementation.)

Hints: There are several ways to define these functions, some being more efficient than others. For this assignment you need not produce the most efficient solution. Note that lists in Lisp and Scheme are traditional linked lists. One way to access the last element of a list is to traverse the list until you reach an element where the next (cdr) element is the empty list (null). Another way is to use the built in function reverse and take the first element of that. To "remove" an element from the end of a list, you can reverse it, take the cdr, and return the reverse of that. To add an element to the end of the list, you can reverse it, cons the new element onto the result, and then return the reverse of that.

To keep things from being too trivial, you are not allowed to do:

    (append originalList (list lastElement))

I would hope most of you would want to show off a bit, and that solution, while technically correct, is too simple to allow.

(2) shift-left and shift-right

Write functions shift-left and shift-right that take a single argument that is assumed to be a list, possibly empty. Shift-left and returns a new list like its argument but with first element moved to the end of the list. Shift right returns a new list with the last element moved to the front. Here are some examples:

> (shift-left '(1 2 3))
(2 3 1)
> (shift-left '(1))
(1)
> (shift-left '())
()
> (shift-left (shift-left '(1 2 3)))
(3 1 2)
> (shift-right '(1 2 3))
(3 1 2)
> (shift-right '(1))
(1)
> (shift-right '())
()
> (shift-right (shift-right '(a b c)))
(b c a)

(3) zipper?, zip and unzip

a) Let's define a zipper as a proper list where each element is itself a list with exactly two elements which can be any expressions. Write a function zipper? that returns #t if its single argument is a zipper and #f if it is not, like so:

> (zipper? '((a 1)(b 2)))
#t
> (zipper? '((foo 100)(bar 2 3)))
#f
> (zipper? '((a 1) b (c 3)))
#f
> (zipper? '((a 1) . 2))
#f
> (zipper? '((a (1)) ((b) 2)))
#t

b) Next, write a function zip that takes any two proper lists and creates a zipper out of them, pairing up elements from the first and second arguments. If the either of the two lists is shorter than the other, use null for the missing elements. Here are some examples:

> (zip '(a b c) '(1 2 3))
((a 1) (b 2) (c 3))
> (zip '(a b c) '(1))
((a 1) (b ()) (c ()))
> (zip '(a b) '(1 2 3))
((a 1) (b 2) (() 3))
> (zip '() '())
()

c) Lastly, write a function unzip that reverses the process, taking a zipper and returning a list of two lists. Again, some examples:

> (unzip '((a 1)(b 2)(c 3)))
((a b c) (1 2 3))
> (unzip '())
(() ())

Testing your Scheme code

You should create a single file named hw6.ss that contains the definitions of your functions for this problem set. To help you get started, here is a file with stubs for the functions you have to write. Feel free to add additional functions if you think you need them (you should not, though).

You can test your scheme code using the unit test file hw6test.ss. You can run this from the command line on gl like this

mzscheme -t hw6test.ss

This will run various unit tests and print a report like the following.

linux1[1]% mzscheme -t hw6test.ss
Running chop tests
5 success(es) 0 failure(s) 0 error(s) 5 test(s) run
Running shift tests
12 success(es) 0 failure(s) 0 error(s) 12 test(s) run
Running zip tests
17 success(es) 0 failure(s) 0 error(s) 17 test(s) run
linux1[2]%

What to hand in

Submit to project hw6 a Scheme file named hw6.ss with the definitions of all of your Scheme functions.

CMSC 331 — Fall 2017