[FrontPage] [TitleIndex] [WordIndex

Assignment 1 Solutions - 2006

Here is the solution guide to the first problem set.

Problem 1: Merge Lists

Write a procedure that takes two lists of numbers in ascending order and produces a single, merged list also in ascending order. For example, {{{(merge (list 1 4 6 8 10) (list 2 3 5 8 18)) ==> (1 2 3 4 5 6 8 8 10 18)}}}

Problem 2: Apply-To-Five

Suppose that we

(define apply-to-five
  (lambda (f)
    (f 5))) 

and also

 (define 1+
   (lambda (x)
     (+ 1 x))) 

What will the results of evaluating the following expressions be?

Problem 3: Max, Min, Mean, Stats

Define the following procedures using only the basic numeric operations + - * / < > <= >= = and list manipulations (cons/car/cdr -- or first/rest if you prefer -- and empty?, which is sometimes spelled null?). You may also use the special forms (including define, lambda, and if) that we discussed in class.

For all of these solutions, your procedures do not have to implement error checking (they do not have to accept the empty list or other invalid inputs.) The solutions written out in this section mostly do accept the empty list due to the if (null? l) case. However, this was not stated in the assignment, so it isn't required.

Problem 4: Stacks vs. Queues

Functional programming languages are quite good for some things, but less good for others. Read about (stacks and) queues in Cormen (pp. 200 - 203). Explain why a queue is a more natural fit for a procedural programming language (i.e., one that uses assignment as a common primitive) than for a purely functional programming language that does not use assignment. You may find it easier to answer this question if you think about implementing a queue in your favorite assignment-based programming language and in scheme. Your answer should be a few well reasoned sentences (no more than a paragraph), possibly with an accompanying illustration if it helps your explanation.

The important thing to realize for this question is the difference between FIFO/FILO and the good match between only accessing one end of a stack and the functional list built out of cons cells. A stack pushes and pops items from one end (the “top”). A queue, on the other hand, pushes onto one end and pops from the other. Stacks are more suited to functional programming languages because they are easily built out of lists (cons cells). Push is cons and pop is car, while saving the cdr. To implement a queue, a functional language would have to cdr all the way down the list and then rebuild it again every time it needed to either push or pop.

Extra Credit / Challenge

1. Define a procedure, {\tt repeatedly}, that takes two arguments -- f, a procedure of one argument, and n, a number of times to apply f -- and returns the function f composed with itself n times. For example, assuming the definition of 1+ from above,

{{{((repeatedly 1+ 3) 6)

2. Now write a procedure repeatedly-until which takes a procedure f of one argument and a procedure until of one argument, and repeats f}{{{until {\tt until} evaluates to true (on the same argument as f). Make sure that you return the final value of repeatedly applying f to x. For example,

{{{((repeatedly-until 1+ (lambda (x) (= (remainder x 10) 0)))


Your answer for repeatedly-until should look something like the following:

2013-07-17 10:42