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.
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.
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).
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.
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) evaluates to the list (10 9 8 7 6 5 4 3 2 1).
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).
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.
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.
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.
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.
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.
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.
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.
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.
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:
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.
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).
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?
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 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.
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').
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.
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:
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.
Generated: Friday September 17, 2021, 14:11:25