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

- The empty list (denoted as
`'()`

) is a list. - If
`a`

is a list, then`(cons x a)`

is also a list for every value of`x`

. - 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 1: Iterative sum

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

### Exercise 4: Convert to lambdas

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