recitation 7: some practice problems
--------------------------------------------
* write down the rules for evaluating expressions in scheme
1. if self-evaluating, ?
2. if name, ?
3. if _____, ?
4. if _____, ?
--------------------------------------------
* write down the rules for application of a procedure
1. if primitive procedure, ?
2. if compound procedure, ?
* what's the difference between a primitive procedure & a compound
procedure?
--------------------------------------------
* fill in the blanks:
To find the value of a COMBINATION:
a. first, find the value of ____________
b. then, APPLY the value of the ___________ to the _______________
--------------------------------------------
* list the special forms we've learned so far. For each special form,
write down the syntax (and/or an example of its use), the special
rules for evaluation, and describe why it must be special form (why
can't we use the regular rules for application?)
--------------------------------------------
(define (map proc lst)
(if (null? lst) nil
(cons (proc (car lst))
(map proc (cdr lst)))))
map: (a->b,list(a)) -> list(b)
(map square (list 1 2 3 4)) -> (1 4 9 16)
(define (filter pred lst)
(cond ((null? lst) nil)
((pred (car lst))
(cons (car lst) (filter pred (cdr lst))))
(else (filter pred (cdr lst)))))
filter: (a->boolean,list(a)) -> list(a)
(filter even? (list 1 2 3 4 5 6)) -> (2 4 6)
(define (fold-right op init lst)
(if (null? lst)
init
(op (car lst)
(fold-right op init (cdr lst)))))
fold-right: ((a,b->b),b,list(a)) -> b
(fold-right + 0 (list 1 2 3)) -> 6
--------------------------------------------
(intersection (list 1 2 3 4) (list 3 5 1 6)) -> (1 3)
* type:
* implement intersection using map, filter, and/or fold-right
--------------------------------------------
(apply-all (list abs square cube inc) -4) -> (4 16 -64 -3)
* type:
* implement apply-all recursively
* implement apply-all using map, filter and/or fold-right
--------------------------------------------
(append (list 1 2 3) (list 4 5 6)) -> (1 2 3 4 5 6)
* type:
* implement append recursively
* implement append using map, filter and/or fold-right
--------------------------------------------
(reverse (list 1 2 3 4)) -> (4 3 2 1)
* type:
* implement reverse recursively using append
* implement reverse iteratively
--------------------------------------------
(define my-tree (list 1 (list 2 3 (list 4 5)) (list (list 6))))
* draw the box & pointer diagram for my-tree
* draw a "stylized tree diagram" for my-tree
* how are they related?
--------------------------------------------
(define (leaf? tree) (not (pair? tree)))
(define (tree-manip leaf-op init merge tree)
(if (null? tree)
init
(if (leaf? tree)
(leaf-op tree)
(merge (tree-manip leaf-op init merge (car tree))
(tree-manip leaf-op init merge (cdr tree))))))
* what's the type of tree-manip?
--------------------------------------------
* use tree manip to square every element of a tree
* use tree-manip to compute the product of all the even-valued
leaves of the tree (assume a tree of integers)
* use tree-manip flatten a tree
* use tree-manip to "deep-reverse" a tree (reverse the order of
children at each node)
* use tree-manip to sum up the values of the leaves of the tree
(assume a tree of numbers)
* use tree-manip to create a new tree, which keeps the odd-valued
leaves of the original tree within the same tree structure, but
removes even valued leaves. (assume a tree of integers)
* for each of the above exercises, write down the types of arguments &
return value for the calls to tree-manip. Make sure it "type checks".
--------------------------------------------
For each expression below, indicate the value & type. If it's value
is undefined, or it produces an error or infinite loop, indicate so.
(let ((* /)
(/ *))
(/ 12 (* 6 3)))
* value:
* type:
((lambda (x + y) (+ x y))
3 * 4)
* value:
* type:
(define (inc x) (+ 1 x))
* value:
* type:
inc
* value:
* type:
(define (foo f)
(lambda (x) (f (f (f x)))))
* value:
* type:
foo
* value:
* type:
((foo inc) 0)
* value:
* type:
((foo (foo inc)) 0)
* value:
* type:
(((foo foo) inc) 0)
* value:
* type:
--------------------------------------------
fibonacci:
f(0) = 1
f(1) = 1
f(n) = f(n-1) + f(n-2), for n >= 2
* write a recursive procedure to implement fibonacci
* write an iterative procedure to implement fibonacci
Note: this version should do something smarter... and
not duplicate work
* use the substitution model (in gory detail, take small steps) to
evaluate a small example of each of your procedures. Come up with
the formula for the number of steps ("height") and memory
requirements ("width") as a function of the input. Generalize this
to an order of growth for each.
Note: the math here is actually a topic for 6.042, but we just want
you to get a flavor for it...
--------------------------------------------
* what's the difference between applicative order & normal order evaluation?
* which does scheme use?
--------------------------------------------
write an expression for ?, so that the expressions below evaluate as indicated.
(define foo ?)
(foo -5 3) => 5
(foo 2 7) => 2
(foo 7 4) => -4
(foo 10 -4) => 4
(define bar ?)
(bar 4) => 6
(bar 5) => 7
(bar 6) => error, divide by zero
(bar 7) => procedure
--------------------------------------------
(define mystery
(lambda (a b)
(mystery-meat 0 a b)))
(define mystery-meat
(lambda (c a b)
(if (> a b)
c
(mystery-meat (+ c a) (+ a 1) b))))
* write an equivalent procedure that generates a recursive process:
(define clarity (lambda (a b)
)
--------------------------------------------
* Design a data structure to store information about students in
6.001. For each student, we want to store: their first name (string),
intended major (number), and their height (number). Explain in words
the contract between your constructor & accessor functions. Sketch
out the box & pointer diagram for a simple example.
* Design an alternate data structure to store the same information.
Try to come up with something really different, and explain in what
cases your first design might be more useful, and in what cases your
second design might be more useful.
Write the following functions. Use your accessors & constructors.
Don't violate the abstraction barrier. (What's an abstraction
barrier?) Use map, filter & fold-right, when appropriate. Also,
write helper functions to make your code concise and easy to read.
* Write a function that takes in a list of student names, and a list of
their corresponding heights and returns a student list, with
everyone's major set as undeclared. Modify your data structure design
as necessary so that you can store and detect undeclared majors. In
your documentation spell out any assumptions you have made about the
input.
* Write a function that takes in a student-list, a student's first
name, and a new major, and returns a new student list with the major
declared appropriately.
* Write a function that takes in a student-list and returns a student
list where the undeclared majors have been set by the length of each
students first name. ("Ben" will be course 3, and "Alyssa" will be
course 6).
* Write a function that takes in a student-list and returns the
average height of students in the class with a particular major. Make
sure you handle undeclared majors and majors with no students.
* Write a function that takes in a student-list and returns a list
of the student names sorted by student height.
--------------------------------------------