« Return to index

HOP WPO 3

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

Section 1: Recursion and Iteration (Again)

Exercise 1: Iterative sum

In the previous exercise session you have implemented procedures that calculate the total sum of a list. The solution is shown below.




		

Rewrite this procedure using iteration, instead of recursion. Do the same for product.

Hint! Iteration in Scheme can be reached by making use of tail-call recursion optimisation.

Exercise 2: Deep Map / Filter

Create two procedures that filter, map values in a nested list structure.




		

Hint! For deep-filter you need more than 3 branches for all the possible combinations in which filtered car and filtered cdr values of pairs can exist.

Exercise 3: Flatten

  1. Write a procedure flatten that flattens nested lists into a single list.
  2. Write a procedure accumulate-symbols that uses flatten but removes all non-symbolic values from a nested list structure.

Section 2: Lambda and Let

Exercise 4: Convert to lambdas

Convert the following two programs to equivalent syntax using lambda.




		



		

Exercise 5: A Lexical Bug

The following program contains a bug.




		

Explain why this program fails using by converting the program text using lambda. Fix the bug, and convert it again to only lambdas.

Section 3: Lists

Exercise 6: Shuffling with lists

Assume that p, q and r have been defined as follows.




		

What is the result of executing the following expressions?

Exercise 7: Adding elements to the end of a list

Bonus Exercises

Bonus Exercise 1: Imperative Loops

Recommended after exercise 7

Write an implementation of a recursive, iterative program using set! (e.g., sum). Explain what the disadvantages (or advantages) are using this approach.