Comp210 Exam#1 Solutions

1998 Spring

1. Write the function append2, which takes two <list-of-symbol> s and returns the contents of the first followed by the contents of the second. Show the (recursive) calls to your function that occur in the hand-evaluation of (append2 (list 'cyan 'teal) (list 'ochre)); the answer should be (list 'cyan 'teal 'ochre) (If two lines denote equal values, connect them with ``=''; don't write down a series of unrelated values.)
   Hint: recur only on the first argument, never varying the second argument.

   For this problem, you don't need to write the data-definition and template for a <list-of-symbol>, though if you are stuck these might help you, and they can provide partial credit.

   You of course cannot appeal to the built-in function append.
   (solution)

2. (25pts) Recall that a <natNum> is
   • 0, or
   • (add1 m), where m is a <natNum>.
   1. Write the template for a function which handles two arguments: a <natNum> and a <list-of-symbol>. Make sure all cases are covered.
   2. Write the function nth-rest, which takes a <natNum> n and a <list-of-symbol> los, and returns los without its first n items, or the symbol 'list-too-short if los has fewer than n items.

        (nth-rest 2 (list 'four 'scores 'and 'twenty))
      = (list 'and 'twenty)
      

      You may simplify and combine cases if you like, but be careful! Indicate whether or not you can rearrange your cond's question/answer pairs and still produce the correct answer.
   (solution)

3. (30pts)
   1. Write a data description for a <list-of-door> (where <door> s will be defined below).
   2. Write a template for a <list-of-door>-handling function, assuming you will have a <door>-handling function.
   3. There are three types of <door> s, depending on what's on the other side: Either a room (which has a name, but nothing else), or a hallway (which has a name and a <list-of-door>), or the outside (which has no further information). Write a reasonable data description for a <door>, along with any accompanying define-structs.
   4. Write a template for a <door>-handling function; remember to write in any appropriate recursive calls.
   5. Write the function can-escape?, which takes a <door> and indicates whether it is possible to reach the outside. (Include the contract for each function you write.)
   (solution)

4. (20pts) Write the function max, which takes a non-empty list of numbers, and returns the largest number in the list. Use an accumulator, and do not use local. Show the (recursive) calls to your function(s) that occur in the hand-evaluation of (max (list 7 5 9 2)).

   Be sure to include a contract and description for all functions you write. (You don't need to write any data description for this problem, though you are welcome to.)
   (solution)