Exercises and solutions
Name binding, Recursion, Iteration, and Continuations

Define a function (header level) which takes a parameter level. The header function should return the similar basic header function provided that n is between one and six. If n is outside this interval, we want header to return the identity function of one parameter.

It means that ((header 3) "Header text") is equal to (h3 "Header text") and that ((h 0) "Header text") is just "Header text".

Hint: Arrange the header functions in a list, and let header select the appropriate header function from this list.

(define header-functions (list h1 h2 h3 h4 h5 h6))

(define (header level)
  (if (and (>= level 1) (<= level 6))
      (list-ref header-functions (- level 1))
      id-1))

(define (alternative-header level . optional-parameter-list)
  (let ((txt (optional-parameter 1 optional-parameter-list #f))
        (native-header-function (list-ref header-functions (- level 1)))
       )
    (if txt (native-header-function txt) native-header-function)))

Program a function outline-copy which makes a deep copy of a list structure. Non-list data in the list should all be translated to a symbol, such as '-. You should be able to handle both proper lists and improper lists.

As an example:

  (outline-copy '((a b c) (d e . f) (h i))) =>
     ((- - -) (- - . -) (- -))

Here is my first attempt (which is not correct):

  (define (outline-copy x)
    (cond ((pair? x)
              (cons (outline-copy (car x)) (outline-copy (cdr x))))
	  (else '-)))

The problem with this function is that it does not handle the empty list part correct.

Here is a better, and correct version:

  (define (outline-copy-1 x)
      (cond ((null? x) '()) 
            ((pair? x)
               (cons (outline-copy-1 (car x)) (outline-copy-1 (cdr x))))
            (else '-)))

Notice how difficult it would be program the copying function without use of recursion. The reason is, of course, that we need recursive functions to process a recursive data structure.

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.

Most likely, you will encounter a couple of problems! Now, 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.

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 certain exact length. 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, cyclically if necessary, until you reach n elements.

;; Replicate lst cyclically to a list of the exact length lgt
(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)))

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.

A table can be represented as a list of rows. This is, in fact, the way tables are represented in HTML. The tr tag is used to mark each row; the td tag is used to mark each cell. The table tag is used to mark the overall table. Thus, the list of rows ((a b c) (d e f)) will be marked up as:

         <table>
           <tr> <td>a</td> <td>b</td> <td>c</td> </tr>
           <tr> <td>d</td> <td>e</td> <td>f</td> </tr>
         </table>

Write a Scheme function called table-render that takes a list of rows as input (as returned by the function sublists, which we programmed above) and returns the appropriate HTML rendering of the rows. Use the LAML mirror functions table, tr, and td. Be sure to call the LAML function xml-render to see the textual HTML rendering of the result, as opposed to LAML's internal representation.

Notice: During the course we will see better and better ways to program table-render. Nevertheless, it is a good idea already now to program a first version of it.