« Return to index

HOP WPO 5 (Solutions)

Assistant: Bjarno Oeyen (bjarno.oeyen@vub.be)

Section 1: More Environment Diagrams

Exercise 1: A Bug in A Let

Converted to lambda:




		

The variable 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 let* expression.




		

Environment Diagram:

ed-letbug.png

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:

  1. Accumulate a list of filtered values: then convert the list to a vector
  2. 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
  3. 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.




		

The 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 #f!

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 stream-car, tail instead of stream-cdr and streamfilter, instead of stream-filter.

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 + and -. 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 sinus-partial-sum.

Exercise 7: Collatz Streams

Finite (?) Collatz:




		

Infinite 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).

Exercise 8: Streams Advanced