Exercise index of this lecture   Alphabetic index   Course home   

Name binding, Recursion, Iteration, and Continuations

3.1   HTML Header functions * 

This is a small exercise that aims at construction of slightly different header functions than those provided by the native header functions h1, ..., h6.

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 a variant of header which returns a native header function if it receives a single parameter (level), and which returns the value, such as, ((header 3) "Header text"), if it receives both a level parameter and a header text string.



3.2   The function outline-copy * 

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


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

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.



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



3.5   Sublists of a list *** 

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

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:

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

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.


Generated: Tuesday July 2, 2013, 09:15:09