# 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:**

## 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.

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