6.001 Recitation #6 – Sept
21, 2003
RI: Konrad Tollmar
Higher-order procedures
Define a procedure swap that takes a single argument whose type is a function that takes two arguments, and returns a function that acts as the input function but with its argument positions swapped.
A/ Write a procedure composef that takes two arguments (eg. f and g), whose type is a function, and returns a function that first apply g to the input, then f to the result – i.e. ((composef f g) x) should be the same as (f (g x)).
B/ Use the substitution model to evaluate ((composef double cube) 3).
C/ What is the type if composef?
Rather than:
(define fourth-power (compose square square))
(define eight-power
(compose
square (compose square square)))
Let’s us define a procedure repeated that can compose a function N times, like in:
(define fourth-power (repeated square 2))
(define eight-power (repeated square 3))
Write a new version of repeated that is iterative, i.e. Q(1) in term of space.
Write a function
comp that takes two arguments a and b and returns a function, that when called with #t returns a and when called with #f returns b.
Finding the length of a list structures can be slow!. Define a new sequence abstraction, similar to lists, but that can return the length in constant time. Here's the contract:
(head (attach x seq)) == x
(tail (attach x seq)) == seq
(seq-empty? empty-seq) == #t
(seq-empty? (attach x seq)) == #f
(seq-length seq) == length in Q(1) time.
Define the procedures head, tail and seq-length.
The smarter sequence perform better than List, but we need to functions that could convert a Sequence to a List. And vise versa. Define the two helper-functions, seq->list and
list->seq that do this.