Higher-Order Programming » Lab Sessions

Session 5

Assistant: Steven Keuchel (steven.keuchel@vub.be)

Section 1: More higher-order functions on lists

Here is the accumulate function from previous exercises and the lectures

(define (accumulate proc default lst) (if (null? lst) default (proc (car lst) (accumulate proc default (cdr lst)))))

Exercise 1:

(Re)define the following functions in terms of accumulate

• Calculate the product of a list of numbers.

• Calculate the minimum and maximum of a list of numbers. Hint: +inf.0 and -inf.0 represent positive and negative infinity.

• Reimplement the standard append function

  (append '(1 2 3) '(4 5 6))

• Implement a function concat given a list of lists produces a flattened lists. (Only one level of flattening!)

  (concat '((1 2 3) (a b c) ((4 5 6))))

• Reimplement the filter function.

• We can represent polynomials as a list of coefficients, i.e. $$ 3x^2+1 $$ is represented as '(1 0 3). So the least significant coefficient appears first and 0 coefficients are explicit.

  Write an evaluation function eval-polynomial that evaluates a polynomial at a given value using accumulate and Horner's rule.

• Reimplement the flatmap function using accumulate:

  (define (flatmap proc lst) (concat (map proc lst)))

  flatmap takes as first argument a procedure proc which is assumed to give back a list of results and all results are concatenated.

  (flatmap (lambda (x) (list x (- x))) '(1 2 3)) ; -> (1 -1 2 -2 3 -3)

  Hint: You may reuse append.

Exercise 2: Non-deterministic programming using flatmap

A variant of the flatmap function from exercise 1 can be found in (the standard libraries of) many programming languages, where it is often also called concatmap or the bind of the list monad. It offers a basis for non-deterministic programming:

• The first argument to flatmap is a function that given an element produces a list of non-deterministic results. Failure can be encoded using an empty list. A deterministic result is a singleton list.
• The second argument is a list of possible result of an earlier computation.

flatmap then combines these two into a list of all possible combination.

For instance the following code first non-deterministically chooses an x from '(1 2 3) and then a y from '(a b c). A single result list is created which pairs up the two: (list (cons x y)). The overall final result is a list of all possible pairs.

(flatmap (lambda (x) (flatmap (lambda (y) (list (cons x y))) '(a b c))) '(1 2 3)) ; -> ((1 . a) (1 . b) (1 . c) (2 . a) (2 . b) (2 . c) (3 . a) (3 . b) (3 . c))

• Reimplement filter using flatmap.

• Define a function

  (define (pythagorean-triples n) ...)

  That creates a list of all pythagorean triples '(a b c) with $1 ≤ a ≤ b ≤ c ≤ n$.

  (pythagorean-triples 17) ; -> ((3 4 5) (5 12 13) (6 8 10) (8 15 17) (9 12 15))

Section 2: Streams

Download streams.rkt. Load this file in R5RS using (load "streams.rkt").

The following procedures are defined in this file: cons-stream, head, tail, empty-stream?, accumulate, map-stream, streamfilter, stream-for-each, append-streams, enumerate-interval, zip, print-stream, print-inf-stream, make-read-stream, cartesian-product, pairs, flatten, flatten-inf, flatmap, en list->stream. The empty stream (the-empty-stream) is also defined in this file and is available after loading.

Exercise 3: Streams Primer

The following is an explicit definition of the infinite streams of number ones.

(define (create-ones) (cons-stream 1 (create-ones)))

• Create a procedure take-n that takes the first n elements of a stream and puts them in a list.
• Create a stream of all positive integers. Make an explicit definition.
• Create a stream of all odd positive integers. Implement it twice, once using an explicit definition and once using streamfilter.
• Create a stream of all integers that are not divisble by 2, 3 or 5 by using streamfilter.

Exercise 4: Stream transformers

streamfilter is a so-called stream transformer. It takes a stream and create a new stream. Implement the following stream transformers. Handle both infinite and finite streams.

1. Pairwise combination

   • Create a function that given two streams creates a stream of their pairwise sums.

     $$x_0~x_1~x_2~x_3 \ldots + y_0~y_1~y_2~y_3 \ldots$$ $$\leadsto (x_0+y_0)~(x_1+y_1)~(x_2+y_2)~(x_3+y_3) \ldots$$

   • Create a function that given two streams creates a stream of their pairwise products.

   • Create an abstract function that can be instantiated to the two previous stream transformers.

2. Prefix calculation

   • Create a function that given a stream of numbers produces a new stream of prefix sums. $$x_0~x_1~x_2~x_3 \ldots$$ $$\leadsto (\Sigma_{i=0}^0 x_i)~(\Sigma_{i=0}^1 x_i)~(\Sigma_{i=0}^2 x_i) \ldots$$
   • Create a function that given a stream of numbers produces a new stream of prefix products.
   • Create an abstract function that can be instantiated to the two previous stream transformers.

3. Write a stream transformer that interleaves two input streams

   $$x_0~x_1~x_2~x_3 \ldots \qquad y_0~y_1~y_2~y_3 \ldots$$ $$\leadsto x_0~y_0~x_1~y_1~x_2~y_2~x_3~y_3 \ldots$$

   (interleave-stream ones (map-stream - ones)) ; -> (1 -1 1 -1 ...)

Exercise 5: Numerical Approximation

1. For this exercise you have to implement a procedure that approximates a sinus of a number using streams.

   $$sin(x) = \frac{x}{1!} - \frac{x^3}{3!} + \frac{x^5}{5!} - \frac{x^7}{7!} + \ldots $$

   • Write a procedure that generates an infinite stream of summands of the above series.
   • Then write a procedure that approximates the sinus by taking the $n$-th partial sum for a given n.

2. Do the same for an approximation of $\pi$:

   $$ \pi = 4 \times \frac{2 \times 4}{3 \times 3} \times \frac{4 \times 6}{5 \times 5} \times \frac{6 \times 8}{7 \times 7} \times \frac{8 \times 10}{9 \times 9} \times \ldots $$

Exercise 6: Collatz Streams

Remember the Collatz conjecture from the first exercise session? The function that is used to generate the next number in the sequence is shown below.

$$ f(n) = \begin{cases} n/2, & \text{if $n$ is even} \\ 3n+1, & \text{if $n$ is odd} \end{cases} $$

The conjecture is that for every given integer, this sequence goes to the number 1.

1. Create a procedure which creates a stream of Collatz streams.
2. What happens if you make your stream infinite? What happens when this stream is created?

Exercise 7: Streams Advanced

In exercise 3, you have implemented streams by making use of an aid procedure. It was also possible to write a definition of ones as follows.

(define ones (cons-stream 1 ones))

This is called an implicit definition.

1. Write an implicit definition of all integers.
2. Write an implicit definition of fibonacci
3. Write an implicit definition of factorial numbers.

Bonus Exercises

Bonus Exercise 1: Merge on Streams

Consider two sorted (infinite) streams. Write a procedure that creates a sorted procedure of the two streams, but merged.