# § HOP WPO 3 (Solutions)

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

## § General Remarks

• If you are still struggling with car, cdr, cons and list, I advise you to draw a box-and-pointer diagram and play “interpreter” yourself.
• If you are still puzzled after drawing box-and-pointer diagrams, you have to understand the definition of lists in Scheme (see below).
• Some of these exercises require you (or will at least make your solution easier) to either reuse previously written code, or another primitive built-in the language. Check the reference manual: r5rs.pdf
• I assume that some procedures (such as add1 are easy to implement), so sometimes you have to implement these yourself.

The following is the definition of lists.

1. The empty list (denoted as '()) is a list.
2. If a is a list, then (cons x a) is also a list for every value of x.
3. No other value can be a list.

For different notations of lists, refer to introduction of Section 1 of Lab Session 2

Other languages allow you to immediately index values of a list (e.g., arrays in most regular languages). In order to get the nth element of a list you have to apply cdr n times on the list structure. If you do not want this kind of behaviour, take a look at vector (which will be introduced in the next session).

## § Section 1: Recursion and Iteration (Again)

### § Exercise 2: Iterative Map / Filter

The implementation of deep-map is straightforward. If the list is empty, the empty list will be returned. If the list is indeed a list (or its more generic form: a pair), then deep-map will be applied recursively on the car and cdr of the pair. Otherwise, we assume it to be a number, boolean, or other non-pair value, and we apply the supplied mapper function on it.

The implementation of deep-filter is more complicated. It follows the same pattern: check for empty list, check for pair, otherwise, execute the given function.

The third case is the most important one: since it can either return 1 or no values. This is implemented by it either returning a singleton list, or the empty list. However, we need to take into account the structure of the empty list. Therefore in the second case there are some additional checks on the type. If the recursive call on car is on a non-pair, this wrapped list needs to be removed via car.

Depending on whether both car and cdr have, or do not have, items to process, either only car or cdr can be returned, or a new pair.

The last peculiar case is when cdr-result is the empty list, then (list car-result) is returned. Since in this case the input element of deep-filter was a list (or at least a pair), the returned element should again be a list.

### § Exercise 3: Flatten

By making use of append two lists are concatenated. Therefore, if the recursive calls on car and cdr return flattened lists, then they can easily be concatenated to create a larger flattened list. Therefore, in the last case of cond the elements are wrapped in a singleton list (a flattened list by definition) such that flatten can only receive flattened lists as arguments.

The implementation of filter can be reused from previous exercises.

## § Section 2: Lambda and Let

let:

let*:

### § Exercise 5: A Lexical Bug

Conversion to lambda:

The variable x is a free variable that is not defined outside of lambda.

Fix:

By modifying the code such that let* is used instead of let.

Conversion to lambda (correct version):

## § Section 3: Lists

### § Exercise 6: Shuffling with Lists

Before starting this expression, it is worth checking what the values of p, q and r are.

Variable Result Explanation
p '(#<procedure:mcons> #<procedure:+>) This is a list containing the procedure cons and the procedure +.
q '(cons +) This is a list containing the symbolis 'cons' and '+. Not the procedures!
r '(cons +) Identical to q, but more explicit that it creates a list

Note that DrRacket will not print the quote character! It is immediatialy showing the structure.

Expression Result Explanation
((car p) 3 4) '(3 . 4) (car p) evaluates to the procedure cons, it is thus applied on its arguments 3 and 4. Thus producing a new pair.
((cadr p) 3 4) 7 (cdr p) is the singleton list containing the procedure +, to gets its value car needs to be applied on this singleton list. Thus (cadr p) evaluates to the procedure +. It is supplied the arguments 3 and 4 and thus produces the number 7.
((car r) 3 4) ERROR This expression will result in an exception being thrown. As (car r) will evaluate to the symbol known as 'cons, not the procedure +. It will thus try to apply a symbol on a number of arguments, which is not allowed.
((cadr q) 3 4) ERROR This expression will result in an exception being thrown for the same reason as the previous one. Only now the symbol '+ is used instead of the procedure +.

### § Exercise 7: Adding elements to the end of a list

Adding an element to the end of a list:

Note that this solution is not tail-call recursive. As preperation for the next exercise, it might be useful to create an iterative (tail-call recursive) version of add-to-end.

Adding an element to the end of a list (tail-call recursive):

By doing the regular pattern of passing an accumulator as input to a loop procedure, we construct a list. However, this list is constructed in reverse (since we cons the first element to the empty list, which is not correct). Therefore, the primitive procedure reverse is used to reverse the list.

This solution is not fast, since the entire list needs to be reversed at the end, but it is tail-call recursive (thus identical to iteration). In a later session we will see a variant that is destructive: it will immediately alter the listed structure without creating a new one that needs to be iterated on.

Appending two lists:

First, let us implement this without iteration (tail-call recursion).

Nothing out of the ordinary in this version, except, to avoid name clashes, the implementation is named my-append.

The implementation of append in a tail-recursive manner is slightly more difficult. The loop starts iterating over the values of the second list, and the accumulator starts with the reversed elements of the first list.

## § Bonus Exercises

### § Bonus Exercise 1: Imperative Loops

As with previous exercises that introduced side effects, the syntax for begin is used for sequential evaluation of multiple expressions. It is needed in this case if multiple expressions need to be evaluated inside the consequent or alternative of an if expression.