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)}}}
a. A simple implementation of merge should look something like this: {{{(define merge (lambda (l1 l2))
- (if (null? l1)
- l2 (if (null? l2)
- l1
(if (< (car l1) (car l2))
- (cons (car l1) (merge (cdr l1) l2)) (cons (car l2) (merge l1 (cdr l2)))))))
- l1
- l2 (if (null? l2)
- (cond ((null? l1) l2)
- ((null? l2) l1)
((< (car l1) (car l2)) (cons (car l1) (merge (cdr l1) l2))) (else (cons (car l2) (merge l1 (cdr l2)))))))
- ((null? l2) l1)
b. Is your procedure linear, quadratic, exponential, or something else? Explain your answer. Merge is linear. It isn't a sort, it runs once for each element in both lists and collates them together. The number of operations doubles when the total size of the 2 input lists (the number of inputs) doubles.
- (if (null? l1)
Problem 2: Apply-To-Five
Suppose that we and also What will the results of evaluating the following expressions be?(define apply-to-five
(lambda (f)
(f 5)))
(define 1+
(lambda (x)
(+ 1 x)))
a. (apply-to-five 1+)
(apply-to-five 1+) -> (+1 5) -> 6
b. (apply-to-five (lambda (n) (* n 3)))
(apply-to-five (lambda (n) (* n 3))) -> (* 5 3) -> 15
c. (apply-to-five apply-to-five)
(apply-to-five apply-to-five) -> (apply-to-five 5) -> (5 5) -> ERROR
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.
a. A procedure that takes one argument, a list of numbers, and returns the largest number in the list. The thing that you don't really want to do in this problem is to call maximum twice in one recursive iteration. That will be very inefficient. You can accomplish this in a number of ways.
Here's what you DON'T want to do:
(define max (lambda (l) (if (null? l) l (if (null? (cdr l)) (car l) (if (> (car l) (max (cdr l))) (car l) (max (cdr l))))))
To get around this, you could use a helper function:(define bigger (lambda (x y) (if (> x y) x y))) (define max (lambda (l) (if (null? l) l (if (null? (cdr l)) (car l) (bigger (car l) (max (cdr l)))))))
You could also use a let:(define max (lambda (l) (if (null? l) l (if (null? (cdr l)) (car l) (let ((m (max (cdr l)))) (if (> (car l) m) (car l) m)))))
Finally, you could do something clever with the lists that you pass to the recursive call in order to make it truly tail-recursive:(define max (lambda (l) (if (null? l) l (if (null? (cdr l)) (car l) (if (> (car l) (cadr l)) (max (cons (car l) (cddr l))) (max (cdr l)))))))
b. 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. You'll need to define some helper functions to help you out with this one: sum and len.
(define sum (lambda (l) (if (null? l) 0 (if (null? (cdr l)) (car l) (+ (car l) (sum (cdr l))))))) (define len (lambda (l) (if (null? l) 0 (+ 1 (len (cdr l)))))) (define mean (lambda (l) (/ (sum l) (len l))))
You could also wrap these helper functions right into the mean function by replacing "sum" and "len" in mean with their actual lambdas.c. 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. Minimum can be accomplished in any of the same ways as maxumim, but just replacing a single test symbol. Any of the above listed designs will work. Then, collect-stats should just build a list directly from the results of the other functions. This could be done with list or my consing.
(define min (lambda (l) (if (null? l) l (if (null? (cdr l)) (car l) (if (< (car l) (cadr l)) (min (cons (car l) (cddr l))) (min (cdr l))))))) (define collect-stats (lambda (l) (list (max l) (min l) (mean l))))
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)
- 9}}}
a. Your solution should end up looking something like this. The important thing to realize is that it should always return a function.
(define repeatedly (lambda (f n) (if (> n 1) (lambda (x) (f ((repeatedly f (- n 1)) x))) (lambda (x) (f x)))))
You could also define repeatedly to evaluate the functions in a different order:(define repeatedly (lambda (f n) (if (> n 1) (lambda (x) ((repeatedly f (- n 1)) (f x))) (lambda (x) (f x)))))
b. What are the values of the following expressions?
i. ((repeatedly (lambda (x) (* x x)) 3) 2) 256
ii. ((repeatedly (repeatedly 1+ 4) 5) 200) 220
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)))
- 346)
350}}}
Your answer for repeatedly-until should look something like the following:
(define repeatedly-until (lambda (f u) (lambda (x) (let ((fx (f x))) (if (u fx) fx ((repeatedly-until f u) fx))))))