Recursion and Higher-order Functions

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.

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.

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.

;; 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)))

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

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

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.

; 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)))))

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

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.

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.

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.

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.

;; 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)))))

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.

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.

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

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.

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

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.

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.

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.

; 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)))

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.

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?))

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

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

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?

 
; 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))))

Given a function fr from real numbers to real numbers. Program a higher-order function derivative, which differentiates 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.

Write a function compare-2-functions

   (compare-2-functions f1 f2 numerical-input-list)

which applies f1 and f2 on elements in numerical-input-list, and outputs a list of differences between f1(x) and f2(x) for x in numerical-input-list. Use compare-2-functions to compare (derivative f) and f'.

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

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.

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

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.

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.

Exercises and solutions Recursion and Higher-order Functions

Exercises and solutions
Recursion and Higher-order Functions