HOP WPO 2
Assistant: Bjarno Oeyen (email@example.com)
Section 1: Box-and-pointer Diagrams
cons creates a new pair where the first argument is the first element in the pair, and the second argument is the second element in a pair.
car will get the value stored at the first location,
cdr the second location.
cdr contains another compound data type (e.g., another pair), then they are refered to by reference, not by copy. It is possible to modify the value stored in a pair via
set-cdr! (for usage, refer to the documentation). The following is a diagram of
(cons a 5).
The following structures are all identical, the first one is the canonical form.
'() refers to the empty list. You can check for the empty list using
All these structures have the following box-and-pointer diagram.
list builds a list of values.
Exercise 1: Simple box-and-pointer diagram
Using pen and paper, draw a box-and-pointer diagram of the following structure.
Exercise 2: Advanced box-and-pointer diagrams
Using pen and paper, draw a box-and-pointer diagram of the following structures. Explain the type of each structure (e.g., is it a tree? is it a list?).
Exercise 3: Shared memory in box-and-pointer-diagrams
Using pen and paper, draw a single box-and-pointer diagram of all the variables occuring in this program. What is shown when displaying every variable?
Hint! Refer to the report on R5RS to find out what the semantics of
What happens when evaluate
(set-cdr! c 'apple) afterwards? What is changed when you display every variable again?
Section 2: Higher-Order Procedures on Lists
In this course, we will make use of higher-order procedures, which are procedures that take a first-class procedure as argument.
Exercise 4: Sum
In this exercise, we will implement multiple versions of a
sum procedure, that calculates the sum of all elements in a given list structure.
- Implement the higher-order procedure
accumulatethat has three parameters: a procedure, a default value, and a list.
sumby making use of
For the first part, use the following boilerplate code.
Exercise 5: Filtering
Complete the following definition of
filter on the list
'(4 8 15 16 23 42) such that only odd numbers are kept.
Then, create a predicate that matches odd numbers, unless they are negative. And pass this predict to filter the following list:
(1 -1 2 -3 5 -8 13 -21 34 -55 89).
Hint! As a convention in Scheme, all names for predicate procedures should end on
Section 3: Higher-Order Procedures on Trees
For the exercises in this section, we will use the following trees.
If you feel stuck on one of these exercises, it can help to draw either a box-and-pointer diagram, or a tree diagram of these structures.
Exercise 6: Sum and depth of a tree
First, write a procedure that calculates the sum of all numbers in a tree, and the depth of a tree. If you are stuck, check the implementation of
count-leaves given during the theory.
Predict what will happen if you pass the given trees to your procedures, then apply this procedure on all given trees. Did your outcome match your expectations?
Second, write a generic procedure that processes all elements in a tree. Complete the following boilerplate code.
Third, write your procedures of the first part of this exercise using
tree-walk and verify whether you get the same result.
Exercise 7: Mapping the values on a tree.
Write a procedure
tree-map that maps all the values in a tree according to some mapper function. Can you make use of
tree-walk from the previous exercise to implement
tree-map? If so, implement this variant.
Bonus Exercise 1: Cycle
Recommended after exercise 3
Write a procedure that takes 3 arguments, and builds a cycle structure. E.g., the result of executing
(make-cycle 8 5 3) should look like:
What is the output of when you display a data structure with a cyclic dependency?
Bonus Exercise 2: Generic Function Composition
Recommended after exercise 5
In the previous exercise session you have implemented
compose for function composition. In the theory you have seen something that should make it possible to implement
compose such that it can be executed on a dynamic number of arguments. Improve your implementation of
compose such that it has support for multiple parameters.
Tip! Check section 4.1.4 of the R5RS manual for the different syntactical options for