## Assignment 1

*Corrected Sat 4 Feb 2006 8:20pm*

Due Monday 6 February *by email* to LAS and Sean (except for the programming project for 6 credit students, which is due Thursday 9 February).

If you do it on paper, use the handy dandy scanner/copiers in the AC and OC to email ... if you haven't tried them yet, you are in for a treat!

This assignment has been offically released and is ready to roll.

- 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)}}}

- Is your procedure linear, quadratic, exponential, or something else? Explain your answer.

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?`(apply-to-five 1+)``(apply-to-five (lambda (n) (* n 3)))``(apply-to-five apply-to-five)`

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.

- A procedure that takes one argument, a list of numbers, and returns the largest number in the list.
- A procedure that takes one argument, a list of numbers, and returns the arithmetic mean (what we lay folks call the average) of the numbers in the list.
a procedure

`collect-stats`that takes as an argument a list of numbers and returns a list of three numbers: the maximum value in the original list, the minimum value in the original list, and the arithmetic mean of the numbers in the original list.

- 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.
**Project students only: Also do 2006ProjectAssignment1**Turn in a code listing (.scm file, properly commented, in ascii so we can run it) and some examples of your code working.*EXTRA CREDIT/CHALLENGE*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) 9}}}- What are the values of the following expressions?
`((repeatedly (lambda (x) (* x x)) 3) 2)``((repeatedly (repeatedly 1+ 4) 5) 200)`

*EXTRA CREDIT/CHALLENGE*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)))- 346)

350}}}