Recursion and Higher-order Functions

**2.1 The append function ****

The function `append`, which is a standard Scheme function, concatenates two or more lists. Let us
here show a version which appends two lists:

(define (my-append lst1 lst2) (cond ((null? lst1) lst2) (else (cons (car lst1) (my-append (cdr lst1) lst2)))))

We will now challenge ourselves by programming an iterative solution, by means of tail recursion. We start with the standard setup:

(define (my-next-append lst1 lst2) (my-next-append-1 lst1 lst2 ...))

where `my-next-append-1` is going to be the tail recursive function:

(define (my-next-append-1 lst1 lst2 res) (cond ((null? lst1) ...) (else (my-next-append-1 (cdr lst1) lst2 ...))))

Fill out the details, and try out your solution.

You may encounter a couple of problems! Do your best to work around these problems, maybe by changing aspects of the templates I have given above.

**Solution**

One common problem with iterative solutions and tail recursive functions is that
lists will be built in the "wrong order". This is due to our use of `cons` to construct lists, and
the fact that `cons` operates on the front end of the list. The common medicine is to
reverse a list, using the function `reverse`, either on of the input, or on the output.

Here is my solution

(define (my-next-append lst1 lst2) (my-next-append-1 (reverse lst1) lst2 lst2)) (define (my-next-append-1 lst1 lst2 res) (cond ((null? lst1) res) (else (my-next-append-1 (cdr lst1) lst2 (cons (car lst1) res)))))

In order to compensate for the 'reversing problem' I pass `lst1` in reversed form to the iterative function `my-next-append-1`.

Also I pass the list `lst2` as the initial value of `res`. This is crucial in order to get
the lists appended at all.

As an additional observation, the second parameter of `my-next-append-1` is not used. Thus, it can be eliminated. I have not done so, however.

**2.2 A list replication function ****

Write a tail recursive function called `replicate-to-length`, which in a cyclic way (if necessary) replicates the elements in a list
until the resulting list is of a certain exact length. You should think of `replicate-to-length` as a function that iterates over the elements of
the list, repeatedly, if necessary. You will probably need to write a helping function to `replicate-to-length`, which
is tail recursive.

The following serves as an example:

(replicate-to-length '(a b c) 8) => (a b c a b c a b)

(replicate-to-length '(a b c) 2) => (a b)

In other words, in `(replicate-to-length lst n)`, take elements out of `lst`, cyclic if necessary, until you reach `n` elements.

**Solution**

;; Replicate lst cyclically to a list of the exact length lgt ;; The helping function builds the list in reversed order. This is compensated by reversing its result. (define (replicate-to-length lst lgt) (reverse (replicate-to-length-1 lst lst '() 0 lgt))) ; Helping function to replicate-to-length. ; original-lst is constant through this function. ; The elements are taken out of lst. ; The result is accumulated up in res. ; count goes from 0 to lgt. (define (replicate-to-length-1 original-lst lst res count lgt) (cond ((null? lst) (replicate-to-length-1 original-lst original-lst res count lgt)) ((< count lgt) (replicate-to-length-1 original-lst (cdr lst) (cons (car lst) res) (+ 1 count) lgt)) (else res)))

**2.3 More about string-merge ***

We have seen two variants of `string-merge` on the accompanying slide. Both make use of `(apply string-merge ...)` in the cases where one of the lists become empty. `apply` calls a function on a list of parameters.
Thus `(apply + (list 1 2))` is equivalent to `(+ 1 2)`.

Eliminate the use of `apply`, such that `string-merge` (tail) recursively builds the end of the list by a number of calls to `string-append` (one for each element in the non-empty list).

**Solution**

Here is a solution for the non-tail recursive variant of string-merge:

(define (string-merge str-list-1 str-list-2) (cond ((and (null? str-list-1) (not (null? str-list-2))) (string-append (car str-list-2) (string-merge '() (cdr str-list-2)))) ((and (not (null? str-list-1)) (null? str-list-2)) (string-append (car str-list-1) (string-merge (cdr str-list-1) '()))) ((and (null? str-list-1) (null? str-list-2)) "") (else (string-append (car str-list-1) (car str-list-2) (string-merge (cdr str-list-1) (cdr str-list-2))))))

**2.4 Sublists of a list ****

The first part of this exercise is similar to an exercise from the previous lecture.

In this exercise we will program a function `front-sublist` which returns the first n elements of a list.
The signature (the head) of the function should be `(front-sublist lst n)` where `lst` is a list and `n` is a number.
As a precondition it can be assumed that `lst` is a proper list and that `n` is a non-negative integer.
As a postcondition we want to guarantee that the length of the result is `n`.

As an example

(front-sublist '(a b c d e) 3) => (a b c) (front-sublist '(a b c d e) 6) => ERROR

First, identify the extreme, border cases and be sure that you know how to handle these. Next, program the function with due respect to both the precondition and the postcondition. Next, test the function carefully in a dialogue with your Scheme system.

Given the function `front-sublist` we will program the function `sublists`, which breaks a proper list into a list of sublists
of some given size. As an example

(sublists '(a b c d e f) 3) => ((a b c) (d e f))

Program the function `sublists` with use of `front-sublist`. Be careful to prepare you solution by recursive thinking.
It means that you should be able to break the overall problem into a smaller problem of the same nature,
as the original problem. You should feel free to formulate both preconditions and postconditions of the function `sublists`,
such that the existing function `front-sublist` fits well.

*Hint*: The Scheme function `list-tail` is probably useful when you program the function `sublists`.

**Solution**

; Precondition: lst is a proper list, n is an integer, n >= 0. (define (front-sublist lst n) (cond ((= n 0) '()) ((null? lst) (error "Too few elements in list")) ((not (null? lst)) (cons (car lst) (front-sublist (cdr lst) (- n 1)))))) ; Precondition: The length of lst is a multiplum of n. n is an integer. n > 0. (define (sublists lst n) (cond ((null? lst) '()) (else (cons (front-sublist lst n) (sublists (list-tail lst n) n)))))

**2.5 A variant of number-interval ***

We have studied the function `number-interval` in this lecture (on this slide) and we have seen that `(number-interval 10 1)` evaluates to the empty list.

Program a variant of `number-interval` such that `(number-interval 10 1)` ealuates to the list (10 9 8 7 6 5 4 3 2 1).

**Solution**

(define (number-interval f t) (cond ((< f t) (cons f (number-interval (+ f 1) t))) ((> f t ) (cons f (number-interval (- f 1) t))) (else ; (= f t) (list f))))

**2.6 A variant of string-of-char-list? ****

The function `string-of-char-list?` was programmed with use of a help function which we called `string-of-char-list-1?` on this slide.
The help function was programmed side by side with `string-of-char-list?`. As an altertive, `string-of-char-list-1?` could be programmed as a local function
of string-of-char-list? Please do that, using an appropriate name binding form.

The help function keeps track of an index `i` in an additional parameter.
It is possible to program `string-of-char-list?` without use of a help function.
This function should iterate over shorter and shorter text strings. Please do that now. Consider the efficiency of this function and our original version of `string-of-char-list?`. (The function `substring` is useful).

**Solution**

Here is the variant where the helping function is local - notice the use of `letrec` (using `let` will not work):

(define (string-of-char-list? str char-list) (letrec ((string-of-char-list-1? (lambda (str char-list i lgt) (if (= i lgt) #t (and (memv (string-ref str i) char-list) (string-of-char-list-1? str char-list (+ i 1) lgt)))))) (string-of-char-list-1? str char-list 0 (string-length str))))

Here is a variant of `string-of-char-list?` that does not apply a help function:

(define (string-of-char-list? str char-list) (let ((str-lgt (string-length str))) (if (= str-lgt 0) #t (and (memv (string-ref str 0) char-list) (string-of-char-list? (substring str 1 str-lgt) char-list)))))

It may be rather expensive to call `string-length` in this function. As a partial remedy, we bind `str-lgt` to the value of `(string-length str)` once and for all.
It may be even cheaper to measure the length of the orginal string once - at top level - and to reduce this length by one for each recursive call.
This, however, requires and extra parameter, and therefore it calls for a help function.

It may be even more expensive to call `substring` in each incarnation of `string-of-char-list?` With this we materialize a bunch of (shorter and shorter) suffixes of the original string.
This should be avoided, and therefore our first version of the function is far better.

**2.7 Using flip, negate, and compose ***

Define and play with the functions `flip`, `negate`, and `compose`, as they are defined on this page .

Define, for instance, a flipped `cons` function and a flipped minus function.

Define the function `odd?` in terms of `even?` and `negate`.

Be sure you understand your results.

**Solution**

I would try the following activations of `flip`, `negate` and `compose`.The notation `expr => v` means that the expression gives the value v when evaluated by Scheme.

`((flip -) 5 6)`=>`1``((flip cons) 'a 'b)`=>`(b . a)``(let ((non-string? (negate string?))) (non-string? 5))`=>`#t``((compose b em) "bold emphasize text")`=>`"<b><em>bold emphasize text</em></b>"`

**2.8 Linear string search ****

Lists in Scheme are linear linked structures, which makes it necessary to apply linear search techniques.

Strings are also linear structures, but based on arrays instead of lists. Thus, strings can be linearly searched, but it is also possible to access strings randomly, and more efficiently.

First, design a function which searches a string linearly, in the same way as `find-in-list`. Will you just replicate the parameters from `find-in-list`, or will you prefer something different?

Next program your function in Scheme.

**Solution**

It is not obvious to replicate the parameter profile from find-in-list. The reason is that the element type of strings is always char. Thus, a predicate will typically (but not necessarily) check for equality relative to a given, fixed character. In that case find-in-string from my (LAML) lib/general.scm is a reasonable solution. Here it is:

;; Search linearly for the character ch in the string str. ;; An optional start postion start-post tells at which position to start the search (default is position 0). ;; Return the index of the first occurence of ch, or #f if it does not exist in str. ;; The index of the first character in a string is 0. (define (find-in-string str ch . start-pos) (let ((start-pos-1 (if (null? start-pos) 0 (car start-pos)))) (find-in-string-1 str ch start-pos-1 (string-length str)))) (define (find-in-string-1 str ch i lgt) (cond ((>= i lgt) #f) ((eqv? ch (string-ref str i)) i) (else (find-in-string-1 str ch (+ i 1) lgt))))

Please be aware if you make a tail recursive function or not. The function above is tail-recursive.

**2.9 Index in list ****

It is sometimes useful to know *where in a list* a certain element occurs, if it occurs at all.
Program the function `index-in-list-by-predicate` which searches for a given element.
The comparison between the given element and the elements in the list is controlled by a comparison parameter to `index-in-list-by-predicate`. The function should return the list position of the match (first element is number 0), or #f if no match is found.

Some examples will help us understand the function:

(index-in-list-by-predicate '(a b c c b a) 'c eq?) => 2 (index-in-list-by-predicate '(a b c c b a) 'x eq?) => #f (index-in-list-by-predicate '(two 2 "two") 2 (lambda (x y) (and (number? x) (number? y) (= x y)))) => 1

Be aware if your function is tail recursive.

**Solution**

;; Return the index of the first occurrence of el in lst. ;; Return #f is el is not found in lst. ;; Comparison is done by comparator. ;; The index of the first element is 0. (define (index-in-list-by-predicate lst el comparator) (index-in-list-by-predicate-1 lst el comparator 0)) (define (index-in-list-by-predicate-1 lst el comparator i) (cond ((null? lst) #f) ((comparator el (car lst)) i) (else (index-in-list-by-predicate-1 (cdr lst) el comparator (+ i 1)))))

**2.10 Binary search in sorted vectors *****

Linear search, as illustrated by other exercises, is not efficient. It is often attractive to organize data in a sorted vector, and to do binary search in the vector.

This exercise is meant to illustrate a real-life higher-order function, generalized with several parameters that are functions themselves.

Program a function `binary-search-in-vector`, with the following signature:

(binary-search-in-vector v el sel el-eq? el-leq?)

`v` is the sorted vector. `el` is the element to search for. If `v-el` is an element in the vector,
the actual comparison is done between `el` and `(sel v-el)`. Thus, the function `sel` is used as a selector on vector elements.
Equality between elements is done by the `el-eq?` function. Thus, `(el-eq? (sel x) (sel y))` makes sense on elements x and y in the vector.
The ordering of elements in the vector is defined by the `el-leq?` function. `(el-leq? (sel x) (sel y))` makes sense on elements x and y in the vector.

The call `(binary-search-in-vector v el sel el-eq? el-leq?)` searches the vector via binary search and it returns an element `el-v` from the vector which satisfies
(el-eq? (sel el-v) el). If no such element can be located, it returns #f.

Here are some examples, with elements being cons pairs:

(binary-search-in-vector '#( (2 . x) (4 . y) (5 . z) (7 . i) (9 . c) (11 . c)) 7 car = <=) => (7 . i) (binary-search-in-vector '#( (2 . x) (4 . y) (5 . z) (7 . i) (9 . c) (11 . c)) 2 car = <=) => (2 . x) (binary-search-in-vector '#( (2 . x) (4 . y) (5 . z) (7 . i) (9 . c) (11 . c)) 10 car = <=) => #f

Be sure to program a tail recursive solution.

**2.11 Generating a C-style compare function ****

A C-style compare function `(cmp x y)` returns *-1* if x is less than y, *0* if x is equal to y, and *1* if x is greater than y.

Write a higher-order function `make-comparator`, that takes two functions `lt` (less than) and `gt` (greater than) as parameters and generates a C-style compare function.

With a little more thought we can generate a C-style compare function from only the function `lt`. Give it a try.

Use `make-comparator` and a standard function `string<?` to generate a function that compares two strings in a C-style (a Scheme version of `strcmp`).

The other way around, write a higher-order function that takes a C-style compare function and generates a list of functions: `lt`, `equal`, `gt`. Test each of the three generated functions and make sure they work as expected.

**Solution**

Here is a possible generation of the C-style compare function

(define (make-comparator lt) (lambda (e1 e2) (cond ((lt e1 e2) -1) ((lt e2 e1) 1) ; notice the trick: we used lt with arguments reordered. (else 0))))

It can used in the following ways:

> (define strcmp (make-comparator string<?)) > (strcmp "abe" "kat") -1 > (strcmp "kat" "abe") 1 > (strcmp "kat" "kat") 0

Here is a function that generates a list of a 'less than', 'equal to', and 'greater than' from a C-style compare function:

(define (lt-eq-gt cmp) (list (lambda (x y) (< (cmp x y) 0)) (lambda (x y) (= (cmp x y) 0)) (lambda (x y) (> (cmp x y) 0))))

**2.12 Higher-order functions in 'Functional Programming Languages' ****

A number of short papers appeared in 1996 in the journal Computing Surveys (as part of the 50 years celebration of the ACM) - among them a paper titled 'Functional Programming Languages' by Benjamin Goldberg. Take a brief look at the paper - in particular the section about 'Higher-order functions'. It is an easy paper to read.

Rewrite the functions `prod`, `fac`, and `power` in Scheme, and give them a try. Do you get the results you would expect? If not, carry out the necessary corrections.

The product operator is introduced to improve the recursive factorial function, suposedly in the direction of iteration. However, the paper is not successful in that respect. Why?

Write an iterative, memory efficient, tail-recursive version of `prod` in Scheme.

**Solution**

Here is the Scheme version of the `prod`, `fac`, and `power` functions from the paper - directly translated.

(define (prod m n f) (if (= n m) (f m) (* (f m) (prod m n f)))) (define (fact n) (let ((f (lambda (i) i))) (prod 1 n f))) (define (power x n) (let ((f (lambda (i) x))) (prod 1 n f)))

The problem is that `prod` recurses forever. It is an easy fix, however:

(define (prod m n f) (if (= n m) (f m) (* (f m) (prod (+ m 1) n f)))) ; First parameter of prod: (+ m 1) instead of just m. (define (fact n) (let ((f (lambda (i) i))) (prod 1 n f))) (define (power x n) (let ((f (lambda (i) x))) (prod 1 n f)))

Here is an iterative, memory efficient, tail-recursive version of `prod`:

(define (prod m n f) (prod-iter m n f 1)) (define (prod-iter m n f r) (if (> m n) r (prod-iter (+ m 1) n f (* r (f m)))))

**2.13 Iterative mapping function ****

In contrast to the function `mymap` on this page , write an iterative mapping function which is tail recursive.

Test your function against `mymap` on this page, and against the native `map` function of your Scheme system.

**Solution**

Here is my attempt to define an iterative mapping function:

(define (mymap-iter f lst) (mymap-help-iter f lst '())) (define (mymap-help-iter f lst result) (cond ((null? lst) (reverse result)) (else (mymap-help-iter f (cdr lst) (cons (f (car lst)) result)))))

Please notice the reversing of the result in the case where lst becomes empty.
It is not efficient to operate on the rear end of a list. Therefore we insert `(f (car lst))`
in the front of the list, and 'turn the list around' (reverses it) once and for all as the last thing
before finally returning the result.

An iteratively programmed function is characterized by having all its 'state' in the parameter list. The relevant 'state' for the iterative mapping task is the original list (which gradually becomes shorter) and the new list of f applications (which gradually gets longer).

Talking about state that changes over time
does not fit with well with functional programming. However, recall from an earlier lecture, that
a chain of tail recursive calls **in principle** creates new 'state variables' for each new call.
**In reality**, however, the state (parameters) are updated imperatively, as a memory optimization.
This does not compromise the functional nature of the program.

**2.14 Table exercise: transposing, row elimination, and column elimination. ****

In an earlier section we have shown the application of some very useful table manipulation functions. Now it is time to program these functions, and to study them in further details.

Program the functions `transpose`, `eliminate-row`, and `eliminate-column`, as they have
been illustrated earlier. As one of the success criteria of this exercise, you should attempt to use higher-order functions as much and
well as possible in your solutions.

**Hint:** Program a higher-order function, `(eliminate-element n)`. The function should return a function which eliminates element number n from a list.

**2.15 A straightforward filter function ****

The `filter` function illustrated in the material is memory efficient, using tail recursion.

Take a moment here to implement the straightforward recursive filtering function, which isn't tail recursive.

**Solution**

Here follows a straightforward implementation of filter:

(define (filter pred lst) (cond ((null? lst) '()) ((pred (car lst)) (cons (car lst) (filter pred (cdr lst)))) (else (filter pred (cdr lst)))))

**2.16 Quantifier Functions ****

The mathematical quantifiers *for all* and *there exists* are well-known. In this exercise we will
write similar Scheme quantifier functions.

The function `(for-all lst p)` is supposed to check if all elements in the list `lst` satisfy the predicate `p`.

The function `(there-exists lst p)` is supposed to check if one or more elements in the list `lst` satisfy the predicate `p`.

Finally, the function `(there-exists-1 lst p)` is supposed to check if exactly on element in the list `lst` satisfies `p`.

Program and test these functions.

You should in addition consider how to program these function by use of `map`, `filter`, and reduction (accumulation).

Please decide if your functions are tail recursive.

**Solution**

; Directly programmed functions. These functions terminate ; if the predicate fails on an element (for-all) or if ; if the predicate holds on an element (there-exists) ; Notice that both functions are tail-recursive. (define (for-all lst p) (cond ((null? lst) #t) ((p (car lst)) (for-all (cdr lst) p)) (else #f))) (define (there-exists lst p) (cond ((null? lst) #f) ((p (car lst)) #t) (else (there-exists (cdr lst) p)))) ; It is easy to program there-exists-1 by use of ; filter - see below. Here is another attempt which makes use of for-all: (define (there-exists-1 lst p) (cond ((null? lst) #f) ((p (car lst)) (for-all (cdr lst) (negate p))) (else (there-exists-1 (cdr lst) p)))) ; Versions of for-all and there-exists programmed with ; mapping and accumulation. These function will traverse the ; whole list twice. This should be avoided, if possible. (define (for-all lst p) (accumulate-right and-fn #t (map p lst))) (define (there-exist lst p) (accumulate-right or-fn #f (map p lst))) (define (there-exists-1 lst p) (= (length (filter p lst)) 1)) ; Here is the stuff necessary for theses functions to work: (define (accumulate-right f init lst) (if (null? lst) init (f (car lst) (accumulate-right f init (cdr lst))))) (define (and-fn x y) (and x y)) ; and is special form - short circuited (define (or-fn x y) (or x y)) ; or is special form - short circuited (define (filter pred lst) (reverse (filter-help pred lst '()))) (define (filter-help pred lst res) (cond ((null? lst) res) ((pred (car lst)) (filter-help pred (cdr lst) (cons (car lst) res))) (else (filter-help pred (cdr lst) res)))) (define (negate p) (lambda (x) (if (p x) #f #t)))

**2.17 Playing with curried functions in Scheme ***

Try out the functions `curry2` and `curry3` on a number of different functions.

You can, for instance, use then curry functions on plus (+) and map.

Demonstrate, by a practical example, that the uncurry functions and the curry functions are inverse to each other.

**2.18 Generation of functions with a very flexible signature *****

Write a function `grouping-abstraction-by-predicates`

(define (grouping-abstraction-by-predicates collector pred1 pred2) ....)

with the following characteristics:

- It takes 3 parameters.
`collector`is another function of three parameters: (1) The list of those that satisfy`pred1`, (2) the list of those that satisfy`pred2`, and (3) the list of all others.`pred1`is a predicate`pred2`is another predicate`grouping-abstraction-by-predicates`returns a function that accept an arbitrary number of parameters. The returned function traverses the (list of) parameters passed to it. The elements that satisfy`pred1`are collected in one list; The elements that satisfy`pred2`are collected in another list; The remaining elements are collected in a third list. The three lists of collected elements are passed to`collector`.`grouping-abstraction-by-predicates`returns the result the call to`collector`.

Use `grouping-abstraction-by-predicates` to generate a function that accepts an arbitrary number of parameter. The functions should add all numbers in the parameter list,
form a string of all characters in the parameter list, and throw away all others away. Thus, the generated function should return a list of one number and one string. Here is an example:

> (define h (grouping-abstraction-by-predicates (lambda (l1 l2 l3) (list (sum l1) (apply string l2))) number? char?)) > (h 1 3 #\a 4 7 #\b 8 #\c #t 5 #t #t #\d) (28 "abcd")

You may want to play with your function for other purposes, with other predicates, etc.

**Solution**

Here is a possible solution:

(define (grouping-abstraction-by-predicates collector pred1 pred2) (lambda parameters (let* ((res-3 (group-in-3 parameters pred1 pred2 '() '() '())) (list-of-pred-1-elements (car res-3)) (list-of-pred-2-elements (cadr res-3)) (other-elements (caddr res-3))) (apply collector (list list-of-pred-1-elements list-of-pred-2-elements other-elements))))) (define (group-in-3 parameters pred1 pred2 lst1 lst2 lst3) (cond ((null? parameters) (list (reverse lst1) (reverse lst2) (reverse lst3))) ((pred1 (car parameters)) (group-in-3 (cdr parameters) pred1 pred2 (cons (car parameters) lst1) lst2 lst3)) ((pred2 (car parameters)) (group-in-3 (cdr parameters) pred1 pred2 lst1 (cons (car parameters) lst2) lst3)) (else (group-in-3 (cdr parameters) pred1 pred2 lst1 lst2 (cons (car parameters) lst3))))) (define (sum number-list) (cond ((null? number-list) 0) (else (+ (car number-list) (sum (cdr number-list)))))) (define h (grouping-abstraction-by-predicates (lambda (l1 l2 l3) (list (sum l1) (apply string l2))) number? char?))

**2.19 Generalization of curry-2 and curry-3 *****

On an earlier slide page we have seen how to generate curried functions with 2 and 3 parameters - `curry2` and `curry3`.
We have also seen how to generate uncurried functions from curried functions - `uncurry2` and `uncurry3`.

Now generalize `curry2` and `curry3:`

(define (curry f n) ...)

where `f` is a function with n parameters.

Similary, generalize `uncurry2` and `uncurry3:`

(define (uncurry cf n) ...)

where `cf` is a curried function with n levels.

Test your functions appropriately, and be sure that `(uncurry (curry f n) n)` is equivalent with `f` (where `f` is a function of n parameters).

**Solution**

Here is a solution with some explaining comments.
The `curry` function was suggested by Søren Envoldsen (student in the PP 2013 class).

; f is a function with n parameters. Return a curried version of f. ; Søren Enevoldsen, Sept. 12, 2013: (define (curry f n) (curry-internal f n '())) ; This function generates a nesting of lambda expression, each accepting a single parameter. ; While nesting lambda expressions (lambda (x) ...) into each other we form a list of all parameters in the last parameter. ; When all nested lambda expressions have been formed, (reverse args) is the list of parameters. f is applied on (reverse args). ; Sample rewritings, currying -: ; (curry - 3) => ; (curry-internal - 3 ()) => ; (lambda(x) (curry-internal - 2 (list x))) => ; (lambda (x) (lambda (y) (curry-internal - 1 (list y x)))) => ; (lambda (x) (lambda (y) (lambda (z) (apply - (reverse (list z y x)))))) (define (curry-internal f n args) (if (= n 1) (lambda (x) (apply f (reverse (cons x args)))) (lambda (x) (curry-internal f (- n 1) (cons x args))))) ; The following variant of uncurry has been suggested by KN: ; The function cf is a curried function with n levels of parameters. ; Return an uncuried variant of cf that - flatly - accepts n parameters. (define (uncurry cf n) (lambda pars (if (= (length pars) n) (apply-n n cf pars) (error "Illegal function signature")))) ; This function successively applies the curried functions. ; parameters holds the remaing parameter list, to be used step-wise by the forthcoming calls of the single-parameter functions. ; At each level, a lambda expression is applied on the first element of parameters. The tail of parameters is passed to the next call of apply-n. (define (apply-n n cf parameters) (if (= n 1) (cf (car parameters)) (apply-n (- n 1) (cf (car parameters)) (cdr parameters))))

Here are some example uses:

> (define cp4 (curry + 4)) > ((((cp4 1) 2) 3) 4) 10 > (define p4 (uncurry cp4 4)) > (p4 1 2 3 4) 10 > (p4 1 2 3 4 6 7 8) Illegal function signature > (p4 1 2 3) Illegal function signature > (define x (uncurry (curry + 4) 4)) > (x 1 2 3 4) 10 > (x 1 2 3 4 5) Illegal function signature

**2.20 Generalized compose *****

We have seen the `compose` function on a previous slide.

Let us here work with a variant of compose called `self-compose`:

(define (self-compose-2 f) (lambda (x) (f (f x))))

You first job is to generalize `self-compose-2` to `self-compose*`, which composes the `f` with itself `n` times:

(define (self-compose* f n) ...)

Test your function appropriately.

Also, program a function `compose*` which takes *a list of functions* as arguments.
Each function in the list must be of a single parameter.
Your function must return the composition of all the functions.
Here is an example of the intended use of the function:

> ((compose* (list incr - fac)) 5) -119

`fac` is here supposed to be the factorial function, and `incr` is the usual increment function.
The expression `(compose* (list incr - fac))` should be equivalent to `(lambda (x) (incr (- (fac x))))`.

Are you able to program `compose*` with a reduction function and `compose`?

**Solution**

; Return a function that applies f n times on its parameter. n >= 1. (define (self-compose* f n) (cond ((= n 1) f) ((> n 1) (lambda (x) (f ((self-compose* f (- n 1)) x)))) (else (error "self-compose*: n must be an integer larger than 0")))) ; Return a function that applies all functions to each other sequentially. The first function in f-list is applied as the last one. (define (compose* f-list) (cond ((= (length f-list) 1) (car f-list)) ((> (length f-list) 1) (lambda (x) ((car f-list) ((compose* (cdr f-list)) x)))) (else (error "compose* must be applied on a non-empty function list")))) ; Alternative, and more attractive variants: (define (self-compose* f n) (cond ((= n 1) f) ((> n 1) (compose f (self-compose* f (- n 1)))) (else (error "self-compose*: n must be an integer larger than 0")))) (define (compose* fn-lst) (cond ((= (length fn-lst) 1) (car fn-lst)) ((> (length fn-lst) 1) (compose (car fn-lst) (compose* (cdr fn-lst)))) (else (error "compose* must be applied on a non-empty function list")))) (define (curry2 f) (lambda(x) (lambda(y) (f x y)))) (define (reduce-right f lst) (if (null? (cdr lst)) (car lst) (f (car lst) (reduce-right f (cdr lst))))) ; An alternative implementation of compose* in terms of compose and reduce-right: (define (compose* fn-lst) (reduce-right compose fn-lst)) (define compose* ((curry2 reduce-right) compose)) (define (incr n) (+ n 1)) (define (fac n) (if (= n 0) 1 (* n (fac (- n 1))))) (define (compose f g) (lambda (x) (f (g x))))

**2.21 Generation of approximations to differentiated functions ****

Given a function `fr` from real numbers to real numbers. Program a higher-order function `derivative`, which dfferentiates a function like `fr`.

In this exercise you are asked to work numerically, in order to approximate the function. This stands as a contrast to symbolic differentiation.

As examples, `(derivative (lambda (x) (* x x)))` should behave (almost) as `(lambda (x) (* 2 x))`; `(derivate sin)` should behave almost as `cos`;
and `(derivate exp)` should behave almost like `exp` itself. Play with `derivative` to confirm these observations. (Map your functions over a number of numeric values, and compare...).

*The inspiration to the exercise comes from Christian Wagenknecht's book 'Programmierparadigmen', from Springer Verlag.*

**Solution**

(define (derivative f) (lambda (x) (let ((h 0.000001)) (/ (- (f (+ x h)) (f x)) h)))) (map (derivative (lambda (x) (* x x))) (list 1.0 2.0 3.0 4.0 5.0)) (map (lambda (x) (* 2 x)) (list 1.0 2.0 3.0 4.0 5.0))

**2.22 The cartesian product of two sets ****

Program a function that returns the cartesian product of two sets. Each set should be represented as a list.

In this exercise, make as much use of `map` as possible. You may also use a reduction function, if needed.
All the involved iteration over lists should done by mapping or reducing functions.
(Do not write your own recursive function that 'just does the job').

**Solution**

Here follows two slightly different solutions. The first without reduce.

(define (cartesian-product set-list-1 set-list-2) (apply append (map (lambda (b) (map (lambda (a) (cons a b)) set-list-1)) set-list-2))) (define (cartesian-product set-list-1 set-list-2) (reduce-right append (map (lambda (b) (map (lambda (a) (cons a b)) set-list-1)) set-list-2))) (define (reduce-right f lst) (if (null? (cdr lst)) (car lst) (f (car lst) (reduce-right f (cdr lst)))))

*The first solution comes from Christian Wagenknecht's book 'Programmierparadigmen', from Springer Verlag.*

**2.23 Powerset ****

Program a function `powerset`, which as input takes a set `S` (represented as a list). The function must return all possible subsets of `S`.

__Hint:__ What is `(powerset '())`? It should, of course, be a set of sets. Each set is a represented as a list.

**Solution**

(define (powerset set-list) (if (null? set-list) '(()) (let* ((powerset-of-smaller-set (powerset (cdr set-list))) (delta (map (lambda (e) (cons (car set-list) e)) powerset-of-smaller-set))) (append powerset-of-smaller-set delta))))

This function illustrates the real power of recursion. Assuming that we can calculate the powerset of `S` minus its first element,
the powerset of `S` is obtained by adding a systematic combination of the first element with each and every set in the smaller powerset.

*The solution is inspired directly from Christian Wagenknecht's book 'Programmierparadigmen', from Springer Verlag.*

**2.24 Generation of get-prop **

In an earlier exercise we programmed an accessor function, `get-prop`, on property lists. We encountered the following challenges:

- We would like to have variants of
`get-prop`for different key comparison functions, without programming a number of (almost identical) variants, with copy paste programming. - We would like to be able to control the "non-found" value, which normally is boolean false (#f). Boolean false is problematic if the values in the properlist are of type boolean.

Write a function

(configure-get-prop comparison-function not-found-value)

which returns a get-prop function which uses `comparison-function` (instead of `equal?`), which returns `not-found-value` instead of #f.

Generate the get-prop function from the earlier exercise, and generate new variants. Play with your generated functions, and make sure that they work as intended.

**Solution**

Here is my solution:

(define (configure-get-prop comparison not-found-value) (letrec ((get-prop (lambda (key property-list) (cond ((null? property-list) not-found-value) ((null? (cdr property-list)) (error "Malformed property list")) ((comparison key (car property-list)) (list key (car (cdr property-list)))) (else (get-prop key (cdr (cdr property-list)))))))) get-prop))

Notice the use of the letrec namebinding in order to provide for recursion in the generated function.

Generated: Tuesday September 18, 2018, 16:18:11