HOP WPO 5 (Solutions)
Assistant: Bjarno Oeyen (firstname.lastname@example.org)
Section 1: More Environment Diagrams
Exercise 1: A Bug in A Let
Converted to lambda:
x is only bound once the body of the
let expression is being evaluated. Therefore, when the expression
(+ 1 x) is being evaluated, it cannot find a value for
x. The bug can be fixed by converting the program to a
Section 2: Vectors
Exercise 2: My name is Vector, Scheme Vector
Exercise 3: Map / Filter on vectors
Map on a Vector:
Filter on a Vector:
There are multiple approaches possible here:
- Accumulate a list of filtered values: then convert the list to a vector
- Scan over the vector to find out the size of the resulting vector before going through all elements again to copy those back to the resulting vector
- An optimized version of 3 that only calls the predicate once for every element.
However, a true solution does not make use of lists. We will first create the unoptimized version that calls the predicate multiple times.
The aid procedure
vector-count is used to check first how many elements there are. The inner loop in
vector-filter2 will then have two pointers: one in the input vector, and one in the output vector. However, the predicate procedure is now given twice for every element: once in
vector-filter, and once in
vector-count. This can be fixed in the third version.
identity procedure is used as an argument for
vector-count. It will therefore count the number of non-false elements given as argument.
Remember that in Scheme, every value is considered true except for
The algorithm in this solution is similar to that of the previous one: however, the
matched vector results in the predicate function only being called once.
There are multiple other solutions that I can think of: such as generating a list of matched indexes, and then use this list to copy (instead of iterating through the vector multiple times), however, this is for you to write!
Exercise 4: Merge Sort
Read the comments in the code to understand the algorithm better.
This is slightly modified from the given template: as the input vector given to the top-level
mergesort procedure makes that vector available in all procedures created therein. It therefore does not need to be passed around as arguments to the utility procedures.
Section 3: Streams
Note! The stream operations defined in the library provided in these exercises is different from the one seen in the theory. The most noteworthy differences are
head, instead of
tail instead of
streamfilter, instead of
Exercise 5: Streams Primer
Exercise 6: Sinus Approximation
The implementation of
sinus-partial-sum does not make use of streams: but can still look quite daunting.
The easiest part is the fraction:
(/ (expt x (* n 2)) (factorial (* n 2))). However, the sign needs to alternate. Note that the following holds…
Therefore, the expression
(if (odd? n) + -) will alternate in returning either
-. Instead of storing this inside a variable, it can be passed as the procedure of the other procedure application. The following two programs are equivalent…
Remember that procedures are first-class values!
A different approach:
Instead of passing a value of
x directly to
Exercise 7: Collatz Streams
Finite (?) Collatz:
Numbers keep being printed on the stream, but as the stream is only generated while
print-stream is recursively reading the next element of a stream, no out of memory error will be generated. However, the Read-Eval-Print Loop will be stuck. You can so stop the execution of the program using
CTRL + K (
⌘ + K on Mac).