Chapter 4
Higher-order Functions

Kurt NÝrmark
Department of Computer Science, Aalborg University, Denmark


Abstract
Previous lecture Next lecture
Index References Contents
In this lecture we will explore the higher-order functions, both on classical ground and with examples from the WWW domain.


Introduction to higher-order functions

Higher-order functions
Slide Annotated slide Contents Index
References Textbook 
The idea of higher-order functions is of central importance for the functional programming paradigm. As we shall see on this and the following pages, this stems from the fact that higher-order functions can be further generalized by accepting functions as parameters. In addition, higher-order functions may act as function generators, because they allow functions to be returned as the result from other functions.

The concept higher-order function: A higher-order function accepts functions as arguments and is able to return a function as its result
The concept higher-order language: A higher-order language supports higher-order functions and allows functions to be constituents of data structures

  • The order of data

    • Order 0: Non function data

    • Order 1: Functions with domain and range of order 0

    • Order 2: Functions with domain and range of order 1

    • Order k: Functions with domain and range of order k-1

Order 0 data have nothing to do with functions. Numbers, lists, and characters are example of such data.

Data of order 1 are functions which work on 'ordinary' order 0 data. Thus order 1 data are the functions we have been concerned with until now.

Data of order 2 - and higher - are example of the functions that have our interest in this lecture.

Functions of order i, i >= 2, are called higher-order functions

Reference

Some simple and general higher-order functions
Slide Annotated slide Contents Index
References Textbook 
It is time to look at some examples of higher-order functions. We start with a number of simple ones.

Program: The function flip changes the order of it's parameters. The function takes a function of two parameters, and returns another function of two parameters. The only difference between the input and output function of flip is the ordering of their parameters.
(define (flip f)
  (lambda (x y)
    (f y x)))

Program: An alternative formulation of flip without use of the sugared define syntax. For easy comparison we show the original version below the alternative formulation. The two different syntaxes are discussed in an earlier lecture, cf. the cross references.
(define flip
  (lambda (f)
    (lambda (x y)
      (f y x))))


(define (flip f)
  (lambda (x y)
    (f y x)))

Program: The function negate negates a predicate. Thus, negate takes a predicate function (boolean function) as parameter and returns the negated predicate. The resulting negated predicate returns true whenever the input predicate returns false, and vise versa.
(define (negate p)
  (lambda (x) 
    (if (p x) #f #t)))

Program: The function compose composes two functions which both are assumed to take a single argument. The resulting function composed of f and g returns f(g(x)), or in Lisp (f (g x)), given the input x . The compose function from the general LAML library accepts two or more parameters, and as such it is more general than the compose function shown here.
(define (compose f g)
  (lambda (x)
    (f (g x))))

Exercise 4.2. 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.

Finally, compose two HTML mirror functions, such as b and em, to a new function.

Be sure you understand your results.

Reference

Linear search in lists
Slide Annotated slide Contents Index
References Textbook 

Search criterias can be passed as predicates to linear search functions

Program: A linear list search function. A predicate accepts as input an element in the list, and it returns either true (#t) or false (#f). If the predicate holds (if it returns true), we have found what we searched for. The predicate pred is passed as the first parameter to find-in-list. As it is emphasized in blue color, the predicate is applied on the elements of the list. The first successful application (an application with true result) terminates the search, and the element is returned. If the first case in the conditional succeeds (the brown condition) we have visited all elements in the list, and we conclude that the element looked for is not there. In that case we return false.
;; A simple linear list search function.
;; Return the first element which satisfies the predicate pred.
;; If no such element is found, return #f.
(define (find-in-list pred lst)
  (cond ((null? lst) #f)
        ((pred (car lst)) (car lst))
        (else (find-in-list pred (cdr lst)))))

Program: A sample interaction using find-in-list. We define a simple association list which relates persons (symbols) and hair colors (strings). The third interaction searches for per's entry in the list. The fourth interaction searches for a person with pink hair color. In the fifth interaction nothing is found, because no person has yellow hair color. In the sixth interaction we illustrate the convenience of boolean convention in Scheme: everything but #f counts as true. From a traditional typing point of view the let expression is problematic, because it can return either a person (a symbol) or a boolean value. Notice however, from a pragmatic point of view, how useful this is.
1> (define hair-colors 
      (pair-up '(ib per ann) '("black" "green" "pink")))

2> hair-colors
((ib . "black") (per . "green") (ann . "pink"))

3> (find-in-list (lambda (ass) (eq? (car ass) 'per)) hair-colors)
(per . "green")

4> (find-in-list (lambda (ass) (equal? (cdr ass) "pink"))
                  hair-colors)
(ann . "pink")

5> (find-in-list (lambda (ass) (equal? (cdr ass) "yellow"))
                  hair-colors)
#f

6> (let ((pink-person
          (find-in-list
            (lambda (ass) (equal? (cdr ass) "pink")) hair-colors)))
    (if pink-person (car pink-person) #f))
ann

Exercise 4.5. 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.

Exercise 4.5. 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 comparion 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.

Exercise 4.5. 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.

Generation of list selectors
Slide Annotated slide Contents Index
References Textbook 

It is attractive to generate generalizations of the list selector functions car, cadr, etc

Program: A simple version of the make-selector-function function.
(define (make-selector-function n)
  (lambda (lst) (list-ref lst (- n 1))))

Program: The existing LAML make-selector-function. It is crucial that you get good error messages in case you access a non-existing list component. This version handles this. For error messages purposes this version of the function accepts an optional parameter, which (somehow redundantly) gives the name of the selector function.
;; Returns a function, which selects element number n in a list.
;; The second parameter, which is optional, is used for error message purposes.
;; In general, this parameter should be a string corresponding to the name of the selector function.
;; If the second parameter is given, we check whether the list is long enough for selection.
;; If not, we give a decent error message. We recommend use of the second parameter in order to
;; avoid meaningless error messages.
;; The first element is number 1.
;; (make-selector-function 1) corresponds to car, (make-selector-function 2) corresponds to cadr, etc.
;; .form (make-selector-function n [selector-name])
(define (make-selector-function n . optional-parameter-list)
 (let ((selector-name (optional-parameter 1 optional-parameter-list #f)))
   (if selector-name
       (lambda (lst)   
         (let ((lgt (length lst)))
            (if (> n lgt)
                (display-error (string-append "The selector function " (as-string selector-name) ": " 
                               "The list "  (as-string lst) " is is too short for selection. "
                               "It must have at least " (as-string n) " elements."
                               ))
                (list-ref lst (- n 1)))))
       (lambda (lst) (list-ref lst (- n 1))))))

Program: Example usages of the function make-selector-function. In interaction 1 through 3 we demonstrate generation and use of the first function. Next we outline how to define accessors of data structures, which are represented as lists. In reality, we are dealing with list-based record structures. In my every day programming, such list structures are quite common. It is therefore immensely important, to access data abstractly (via name accessors, instead of via the position in the list (car, cadr, etc). In this context, the make-selector-function comes in handy.
1> (define first (make-selector-function 1 "first"))

2> (first '(a b c))
a

3> (first '())
The selector function first: 
The list () is is too short for selection. 
It must have at least 1 elements.
> 

4> (define (make-person-record firstname lastname department) 
      (list 'person-record firstname lastname department))

5> (define person-record 
      (make-person-record "Kurt" "Normark" "Computer Science"))

6> (define first-name-of 
           (make-selector-function 2 "first-name-of"))

7> (define last-name-of 
           (make-selector-function 3 "last-name-of"))

8> (last-name-of person-record)
"Normark"

9> (first-name-of person-record)
"Kurt"


Mapping and filtering

Classical higher-order functions: Overview
Slide Annotated slide Contents Index
References Textbook 
We start with an overview of the classical higher-order functions on lists, not just mapping and filtering, but also including reduction and zipping functions which we cover in subsequent sections.

There exists a few higher-order functions via which a wide variety of problems can be solved by simple combinations

  • Overview:

    • Mapping: Application of a function on all elements in a list

    • Filtering: Collection of elements from a list which satisfy a particular condition

    • Accumulation: Pair wise combination of the elements of a list to a value of another type

    • Zipping: Combination of two lists to a single list

The functions mentioned above represent abstractions of algorithmic patterns in the functional paradigm

The idea of patterns has been boosted in the recent years, not least in the area of object-oriented programming. The classical higher-order list functions encode recursive patterns on the recursive data type list. As a contrast to many patterns in the object-oriented paradigm, the patterns encoded by map, filter, and others, can be programmed directly. Thus, the algorithmic patterns we study here are not design patterns. Rather, they are programming patterns for the practical functional programmer.

Mapping
Slide Annotated slide Contents Index
References Textbook 
The idea of mapping is to apply a function on each element of a list, hereby collecting the list of the function applications

A mapping function applies a function on each element of a list and returns the list of these applications

The function map is an essential Scheme function

Figure. Mapping a function m on a list. m is applied on every element, and the list of these applications is returned.

Reference

The mapping function
Slide Annotated slide Contents Index
References Textbook 
It is now time to study the implementation of the mapping function. We program a function called mymap in order not to redefine Scheme's own mapping function (a standard function in all Scheme implementations).

A possible implementation of map, called mymap:

Program: An implementation of map. This is not a good implementation because the recursive call is not a tail call. We leave it as an exercise to make a memory efficient implementation with tail recursion - see the exercise below.
(define (mymap f lst)
  (if (null? lst)
      '()
      (cons (f (car lst))
            (mymap f (cdr lst)))))

Exercise 4.7. 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.

Exercise 4.7. 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.

Examples of mapping
Slide Annotated slide Contents Index
References Textbook 
We will now study a number of examples.

Table. In the first row we map the string? predicate on a list of atoms (number, symbols, and strings). This reveals (in terms of boolean values) which of the elements that are strings. In the second row of the table, we map a 'multiply with 2' function on a list of numbers. The third row is more interesting. Here we map the composition of li , b , and red font coloring on the elements a, b, and c. When passed to the HTML mirror function ul , this makes an unordered list with red and bold items. Notice that the compose function used in the example is a higher-order function that can compose two or more functions. The function compose from lib/general.scm is such a function. Notice also that the HTML mirror function ul receives a list, not a string. The fifth and final row illustrates the raw HTML output, instead of the nicer rendering of the unordered list, which we used in the third row.
Expresion

Value

(map 
  string?
  (list 1 'en "en" 2 'to "to"))
(#f #f #t #f #f #t)
(map 
   (lambda (x) (* 2 x))
   (list 10 20 30 40))
(20 40 60 80)
(ul
  (map 
   (compose li 
    (compose b 
     (lambda (x)
      (font-color red x))))
   (list "a" "b" "c")
  )
)
  • a
  • b
  • c
Same as above
<ul>
  <li>
   <b><font color = "#ff0000">a</font></b>
  </li>
  <li>
   <b><font color = "#ff0000">b</font></b>
  </li>
   <li>
    <b><font color = "#ff0000">c</font></b>
  </li>
</ul>
 

Filtering
Slide Annotated slide Contents Index
References Textbook 
As the name indicates, the filter function is good for examining elements of a list for a certain property. Only elements which possess the property are allowed through the filter.

A filtering function applies a predicate (boolean function) on every element of a list. Only elements on which the predicate returns true are returned from the filtering function.

The function filter is not an essential Scheme function - but is part of the LAML general library

Figure. Filtering a list with a predicate f. The resulting list is the subset of the elements which satisfy f (the elements on which f returns true).

References

The filtering function
Slide Annotated slide Contents Index
References Textbook 
The next item on the agenda is an implementation of filter .

For practical purposes it is important to have a memory efficient filter function

Program: An implementation of filter which is memory efficient. If the predicate holds on an element of the list (the red fragment) we include the element in the result (the brown fragment). If not (the green fragment), we drop the element from the result (the purple fragment).
(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))))

Exercise 4.8. 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.

Examples of filtering
Slide Annotated slide Contents Index
References Textbook 
As we did for mapping, we will also here study a number of examples. As before, we arrange the examples in a table where the example expressions are shown to the left, and their values to the right.

Table. In the first row we filter the first five natural numbers with the even? predicate. In the second row, we filter the same list of numbers with the odd? predicate. Rather than using the name odd? we form it by calculating (negate even?) . We have seen the higher-order function negate earlier in this lecture. The third and final example illustrates the filtering of a list of atoms with the string? predicate. Only strings pass the filter, and the resulting list of strings is rendered in an ordered list by means of the mirror function of the ol HTML element.
Expression

Value

(filter 
  even?
 '(1 2 3 4 5))
(2 4)
(filter 
  (negate even?)
  '(1 2 3 4 5))
(1 3 5)
(ol 
 (map li
  (filter string?
   (list 
     1 'a "First" "Second" 3))))
  1. First
  2. Second
Same as above
<ol>
  <li>First</li> <li>Second</li>
</ol>
 


Reduction and zipping

Reduction
Slide Annotated slide Contents Index
References Textbook 

Reduction of a list by means of a binary operator transforms the list to a value in the range of the binary operator.

Figure. Left and right reduction of a list. Left reduction is - quite naturally - shown to the left, and right reduction to the right.

There is no natural value for reduction of the empty list. Therefore we assume as a precondition that the list is non-empty.

The reduction functions
Slide Annotated slide Contents Index
References Textbook 

The function reduce-right is a straightforward recursive function

The function reduce-left is a straightforward iterative function

Program: The function reduce-right. Notice the fit between the composition of the list and the recursive pattern of the right reduction.
y:/Kurt/Files/courses/prog3/prog3-03/sources/notes/includes/reduction.scm

Program: The function reduce-left. There is a misfit between left reduction and the recursive composition of the list with heads and tails. However, an iterative process where we successively combine e1 and e2 (giving r1), r1 and e3 etc., is straightforward. As we have seen several times, this can be done by a tail recursive function, here reduce-help-left.
y:/Kurt/Files/courses/prog3/prog3-03/sources/notes/includes/reduction.scm

Table. Examples of reductions. The - left reduction of the list corresponds to calculating the expression (- (- (- (- 1 2) 3) 4) 5). The - right reduction of the list corresponds to calculating the expression (- 1 (- 2 (- 3 (- 4 5)))).
Expression

Value

(reduce-left - '(1 2 3 4 5))
-13
(reduce-right - '(1 2 3 4 5))
3
(reduce-left string-append (list "The" " " "End"))
"The End"
(reduce-left append 
  (list (list 1 2 3) (list 'a 'b 'c)))
(1 2 3 a b c)
 

Exercise 4.9. 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.

Accumulation
Slide Annotated slide Contents Index
References Textbook 

It is not satisfactory that we cannot reduce the empty list

We remedy the problem by passing an extra parameter to the reduction functions

We call this variant of the reduction functions for accumulation

Program: The function accumulate-right. The recursive pattern is similar to the pattern of reduce-right.
y:/Kurt/Files/courses/prog3/prog3-03/sources/notes/includes/reduction.scm

Table. Examples of right accumulations. The first row illustrates that we can accumulate the empty list. The second and third rows are similar to the second and third rows in Table 15.1.
Expression

Value

(accumulate-right - 0 '())
0
(accumulate-right - 0 '(1 2 3 4 5))
3
(accumulate-right append '()
  (list (list 1 2 3) (list 'a 'b 'c)))
(1 2 3 a b c)
 

In relation to web programming we most often append accumulate lists and strings

accumulate-right is part of the general LAML library

Due to their deficiencies, the reduction functions are not used in LAML

Zipping
Slide Annotated slide Contents Index
References Textbook 

Two equally long lists can be pair wise composed to a single list by means of zipping them

Figure. Zipping two lists with the function z. The head of the resulting list is (z e i f i), where the element e i comes from the first list, and f i comes from the other.

The zipping function
Slide Annotated slide Contents Index
References Textbook 

Program: The function zip.
y:/Kurt/Files/courses/prog3/prog3-03/sources/notes/includes/zipping.scm

Table. Examples of zipping.
Expression

Value

(zip cons '(1 2 3) '(a b c))
((1 . a) (2 . b) (3 . c))
(apply string-append
 (zip 
  string-append
  '("Rip" "Rap" "Rup")
  '(", " ", and " "")))
"Rip, Rap, and Rup"
(string-merge 
  '("Rip" "Rap" "Rup") '(", " ", and "))
"Rip, Rap, and Rup"
 

Zip is similar to the function string-merge from the LAML general library

However, string-merge handles lists of strings non-equal lengths, and it concatenates the zipped results

Reference


Currying

The idea of currying
Slide Annotated slide Contents Index
References Textbook 
Currying is the idea of interpreting an arbitrary function to be of one parameter, which returns a possibly intermediate function, which can be used further on in a calculation.

The concept currying: Currying allows us to understand every function as taking at most one parameter. Currying can be seen as a way of generating intermediate functions which accept additional parameters to complete a calculation

Figure. The signatures of curried functions. In the upper frame we show the signature of a function f, which takes three parameters. The frames below show the signature when f is curried. In the literature, the notation shown to the bottom right is most common. The frame to the left shows how to parse the notation (the symbol -> associates to the right).

Currying and Scheme is not related to each other. Currying must be integrated at a more basic level to be elegant and useful

Reference

Currying in Scheme
Slide Annotated slide Contents Index
References Textbook 

It is possible to generate curried functions in Scheme.

But the parenthesis notation of Lisp does not fit very well with the idea of currying

Program: Generation of curried and uncurried functions in Scheme.
(define (curry2 f)
  (lambda(x)
    (lambda(y)
      (f x y))))

(define (curry3 f)
  (lambda(x)
    (lambda(y)
      (lambda(z)
       (f x y z)))))

(define (uncurry2 f)
  (lambda (x y)
    ((f x) y)))

(define (uncurry3 f)
  (lambda (x y z)
    (((f x) y) z)))

Exercise 4.10. 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.

Examples of currying
Slide Annotated slide Contents Index
References Textbook 

Curried functions are very useful building blocks in the functional paradigm

In particular, curried functions are adequate for mapping and filtering purposes

Table. Examples of currying in Scheme.
Expression

Value

(font-1 4 red "Large red text")
Large red text
(define curried-font-1 (curry3 font-1))
(define large-font (curried-font-1 5))
((large-font blue) "Very large blue text")
Very large blue text
(define small-brown-font ((curried-font-1 2) brown))
(small-brown-font "Small brown text")
Small brown text
(define large-green-font ((curried-font-1 5) green))
(list-to-string (map large-green-font (list "The" "End")) " ")
The End
 

Ad hoc currying in Scheme (1)
Slide Annotated slide Contents Index
References Textbook 

It is possible to achieve 'the currying effect' by generalizing functions, which requires two or more parameters, to only require a single parameter

Motivation:

Table. A legal mapping and an impossible attempt to curry the mapping function. The last example shows an application of curry2 to achieve the wanted effect, but as it appears, the solution is not very elegant.
Expression

Value

(map li (list "one" "two" "three"))
("<li>one</li>"
 "<li>two</li>"
 "<li>three</li>")
(define li-mapper (map li))
map: expects at least 2 arguments, given 1
(define li-mapper ((curry2 map) li))
(li-mapper (list "one" "two" "three"))
("<li>one</li>"
 "<li>two</li>"
 "<li>three</li>")
 

Program: The function curry-generalized. This is a higher-order function which generalizes the function passed as parameter to curry-generalized. The generalization provides for just passing a single parameter to f, in the vein of currying.
(define (curry-generalized f)
  (lambda rest
    (cond ((= (length rest) 1)
             (lambda lst (apply f (cons (car rest) lst))))
          ((>= (length rest) 2)
             (apply f (cons (car rest) (cdr rest)))))))

Ad hoc currying in Scheme (2)
Slide Annotated slide Contents Index
References Textbook 

Better results:

Table. Examples of curry generalization of map. Using curry-generalized it is possible to make a li-mapper in an elegant and satisfactory way. The last row in the table shows that gmap can be used instead of map. Thus, gmap can in all respect be a substitution for map, and we may chose to redefine the name map to the value of (curry-generalized map).
Expression

Value

(define gmap (curry-generalized map))
(define li-mapper (gmap li))
(li-mapper (list "one" "two" "three"))
("<li>one</li>" 
 "<li>two</li>" 
 "<li>three</li>")
(gmap li (list "one" "two" "three"))
("<li>one</li>" 
 "<li>two</li>"
 "<li>three</li>")
 


Web related higher-order functions

HTML mirror generation
Slide Annotated slide Contents Index
References Textbook 

There are three different cases to consider: double tag elements, single tag elements, and tags that can be both single and double.

A well-known tag, that can be both single and double is the p tag.

Program: The two higher-order functions for the HTML mirror generation. This version corresponds to the an earlier version of LAML's HTML mirror.
(define (generate-double-tag-function tag-name)
  (lambda (contents . attributes)
    (double-tag tag-name contents attributes)))

(define (generate-single-tag-function tag-name)
  (lambda attributes
    (single-tag tag-name attributes)))

Program: Functions that generate single and double tags.
(define (single-tag name attributes)
 (start-tag name attributes))

(define (double-tag name contents attributes)
 (string-append (start-tag name attributes)
                (as-string contents)
                (end-tag name)))

Program: Functions that generate individual single and double tags.
(define (start-tag kind attributes)
  (if (null? attributes) 
      (string-append "<" kind ">")
      (let ((html-attributes (linearize-attributes attributes)))
         (string-append "<" kind " " html-attributes " >"))))

(define (end-tag kind)
  (string-append "</" kind ">"))

Program: Functions for attribute linearization. The parameter attr-list is a property list.
(define (linearize-attributes attr-list)
  (string-append  
    (linearize-attributes-1
      (reverse attr-list) "" (length attr-list))))

(define (linearize-attributes-1 attr-list res-string lgt)
  (cond ((null? attr-list) res-string)
        ((>= lgt 2) 
          (linearize-attributes-1 
           (cddr attr-list)
           (string-append 
            (linearize-attribute-pair
             (car attr-list) (cadr attr-list)) " " res-string)
           (- lgt 2)))
        ((< lgt 2) 
          (error "The attribute list must have even length"))))

(define (linearize-attribute-pair val attr)
  (string-append (as-string attr)
                  " = " (string-it (as-string val))))

Program: All functions from above in a single file.
(define (generate-double-tag-function tag-name)
  (lambda (contents . attributes)
    (double-tag tag-name contents attributes)))

(define (generate-single-tag-function tag-name)
  (lambda attributes
    (single-tag tag-name attributes)))

(define (single-tag name attributes)
 (start-tag name attributes))

(define (double-tag name contents attributes)
 (string-append (start-tag name attributes)
                (as-string contents)
                (end-tag name)))



(define (start-tag kind attributes)
  (if (null? attributes) 
      (string-append "<" kind ">")
      (let ((html-attributes (linearize-attributes attributes)))
         (string-append "<" kind " " html-attributes " >"))))

(define (end-tag kind)
  (string-append "</" kind ">"))

(define (linearize-attributes attr-list)
  (string-append  
    (linearize-attributes-1
      (reverse attr-list) "" (length attr-list))))

(define (linearize-attributes-1 attr-list res-string lgt)
  (cond ((null? attr-list) res-string)
        ((>= lgt 2) 
          (linearize-attributes-1 
           (cddr attr-list)
           (string-append 
            (linearize-attribute-pair
             (car attr-list) (cadr attr-list)) " " res-string)
           (- lgt 2)))
        ((< lgt 2) 
          (error "The attribute list must have even length"))))

(define (linearize-attribute-pair val attr)
  (string-append (as-string attr)
                  " = " (string-it (as-string val))))

(define (map-concat f lst)
  (apply string-append (map f lst)))

The current HTML mirror in LAML is more advanced and sophisticated than the one illustrated above

References

HTML mirror usage examples
Slide Annotated slide Contents Index
References Textbook 

The example assumes loading of laml.scm and the function map-concat, which concatenates the result of a map application.

The real mirrors use implicit (string) concatenation

Table. An example usage of the simple HTML mirror which we programmed on the previous page. The bottom example shows, as in earlier similar tables, the HTML rendering of the constructed table. The map-concat function used in the example is defined in the general LAML library as (define (map-concat f lst) (apply string-append (map f lst))). In order to actually evaluate the expression you should load laml.scm of the LAML distribution first.
Expression

Value

(let* ((functions
         (map generate-double-tag-function 
              (list "table" "td" "tr")))
       (table (car functions))
       (td (cadr functions))
       (tr (caddr functions)))
 (table
  (string-append
   (tr 
     (map-concat td (list "c1" "c2" "c3"))
     'bgcolor "#ff0000")
   (tr
     (map-concat td (list "c4" "c5" "c6")))
   (tr
     (map-concat td (list "c7" "c8" "c9"))))
  'border 3))
<table border="3">
   <tr bgcolor="#ff0000">
     <td> c1 </td>
     <td> c2 </td> 
     <td> c3 </td>  
   </tr>
   <tr> 
     <td> c4 </td> 
     <td> c5 </td>
     <td> c6 </td>
   </tr>
   <tr> 
     <td> c7 </td>
     <td> c8 </td>
     <td> c9 </td>
   </tr>
</table>
Same as above
c1 c2 c3
c4 c5 c6
c7 c8 c9
 

Making tables with the real mirror
Slide Annotated slide Contents Index
References Textbook 

The real mirror provide for more elegance than the simple mirror illustrated above

Here we will use the XHTML1.0 transitional mirror

Table. A XHTML mirror expression with a table corresponding to the table shown on the previous page and the corresponding HTML fragment. Notice the absence of string concatenation. Also notice that the border attribute is given before the first tr element. The border attribute could as well appear after the tr elements, or in between them.
Expression

Rendered value

(table
  'border 3
   (tr 
     (map td (list "c1" "c2" "c3"))
     'bgcolor "#ff0000")
   (tr
     (map td (list "c4" "c5" "c6")))
   (tr
     (map td (list "c7" "c8" "c9")))
)
<table border = "3">
  <tr bgcolor = "#ff0000">
   <td>c1</td>
   <td>c2</td>
   <td>c3</td>
  </tr> 
  <tr>
   <td>c4</td> 
   <td>c5</td> 
   <td>c6</td>
  </tr> 
  <tr>
    <td>c7</td>
    <td>c8</td>
    <td>c9</td>
  </tr>
</table>
Same as above
c1 c2 c3
c4 c5 c6
c7 c8 c9
 

Tables with higher-order functions
Slide Annotated slide Contents Index
References Textbook 

Instead of explicit composition of td and tr elements we can use a mapping to apply tr to rows and td to elements

Table. In the table expression we map - at the outer level - a composition of tr and a td-mapper. The td-mapper is made by (gmap td).
Expression

Value

(define rows 
  '(("This" "is" "first" "row")
   ("This" "is" "second" "row")
   ("This" "is" "third" "row")
   ("This" "is" "fourth" "row"))
)

(table 'border 5
 (gmap
   (compose tr (gmap td)) rows))
This is first row
This is second row
This is third row
This is fourth row
 

The last example illustrates that (gmap td) is a useful building block, which can be composed with other functions.

The last example depends on the fact that the HTML mirror functions accept lists of elements and attributes.

HTML element modifications
Slide Annotated slide Contents Index
References Textbook 

The idea behind the function modify-element is to perform an a priori binding of some attributes and some of the contents of a mirror function.

Program: The function modify-element.
(define (modify-element element . attributes-and-contents)
  (lambda parameters 
   (apply element 
    (append parameters attributes-and-contents))))

Table. Examples of element modification using the function modify-element.
Expression

Value

(define td1 
 (modify-element td 
  'bgcolor (rgb-color-list red)
  'width 50))

(table 'border 5 
  (map (compose tr (gmap td1)) rows))
This is first row
This is second row
This is third row
This is fourth row
(define ol1 
  (modify-element ol 'type "A"))

(ol1 
 (map
   (compose li as-string)
   (number-interval 1 10)))
  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8
  9. 9
  10. 10
(define ul1 
  (modify-element ul 'type "square"))

(ul1 
 (map
  (compose li as-string)
  (number-interval 1 10)))
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
 

The function simple-html-table
Slide Annotated slide Contents Index
References Textbook 

In an earlier exercise - 'restructuring of lists' - we have used the function simple-html-table

We will now show how it can be implemented

Program: The function simple-html-table. Locally we bind gmap to the curry generalized map function. We also create a specialized version of td, which includes a width attribute the value of which is passed as parameter to simple-html-table . In the body of the let construct we create the table in the same way as we have seen earlier in this lecture.
(define simple-html-table 
 (lambda (column-widht list-of-rows)
  (let ((gmap (curry-generalized map))
        (td-width 
          (modify-element td 'width
                          (as-string column-widht))))
    (table 
      'border 1
      (tbody 
       (gmap (compose tr (gmap td-width)) list-of-rows))))))

Reference

The XHTML mirror in LAML
Slide Annotated slide Contents Index
References Textbook 

LAML supports an exact mirror of the 77 XHTML1.0 strict elements as well as the other XHTML variants

The LAML HTML mirror libraries are based on a parsed representation of the HTML DTD (Document Type Definition). The table below is automatically generated from the same data structure.

Table. HTML elements, their status, and their attributes in the XHTML1.0 strict Scheme mirror. The Content model information is - for most elements - shown as predicates which validate the individual elements. An EMPTY indication tells that there is no content model to validate, because the element is a terminal one (no constituent elements). For a few elements a non-trivial string is given as content model. These elements calls for specialized validation predicates, which have be hand written, from case to case.
Element

Content model

Attributes

html(sequence-with-optionals "head" "body")
langdir
xml:langxmlns
head"((script|style|meta|link|object)*, ((title, (script|style|meta|link|object)*, (base, (script|style|meta|link|object)*)?) | (base, (script|style|meta|link|object)*, (title, (script|style|meta|link|object)*))))"
langdir
xml:langprofile
titlepcdata-checker
langdir
xml:lang
base"EMPTY"
href
meta"EMPTY"
langname
xml:langcontent
dirscheme
http-equiv
link"EMPTY"
idonmousemove
classonmouseout
styleonkeypress
titleonkeydown
langonkeyup
xml:langcharset
dirhref
onclickhreflang
ondblclicktype
onmousedownrel
onmouseuprev
onmouseovermedia
stylepcdata-checker
langmedia
xml:langtitle
dirxml:space
type
scriptpcdata-checker
charsetdefer
typexml:space
src
noscript(zero-or-more "p" "h1" "h2" "h3" "h4" "h5" "h6" "div" "ul" "ol" "dl" "pre" "hr" "blockquote" "address" "fieldset" "table" "form" "ins" "del" "script" "noscript")
idonmousedown
classonmouseup
styleonmouseover
titleonmousemove
langonmouseout
xml:langonkeypress
dironkeydown
onclickonkeyup
ondblclick
body(zero-or-more "p" "h1" "h2" "h3" "h4" "h5" "h6" "div" "ul" "ol" "dl" "pre" "hr" "blockquote" "address" "fieldset" "table" "form" "ins" "del" "script" "noscript")
idonmouseup
classonmouseover
styleonmousemove
titleonmouseout
langonkeypress
xml:langonkeydown
dironkeyup
onclickonload
ondblclickonunload
onmousedown
div(zero-or-more "#PCDATA" "p" "h1" "h2" "h3" "h4" "h5" "h6" "div" "ul" "ol" "dl" "pre" "hr" "blockquote" "address" "fieldset" "table" "form" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript")
idonmousedown
classonmouseup
styleonmouseover
titleonmousemove
langonmouseout
xml:langonkeypress
dironkeydown
onclickonkeyup
ondblclick
p(zero-or-more "#PCDATA" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript")
idonmousedown
classonmouseup
styleonmouseover
titleonmousemove
langonmouseout
xml:langonkeypress
dironkeydown
onclickonkeyup
ondblclick
h1(zero-or-more "#PCDATA" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript")
idonmousedown
classonmouseup
styleonmouseover
titleonmousemove
langonmouseout
xml:langonkeypress
dironkeydown
onclickonkeyup
ondblclick
h2(zero-or-more "#PCDATA" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript")
idonmousedown
classonmouseup
styleonmouseover
titleonmousemove
langonmouseout
xml:langonkeypress
dironkeydown
onclickonkeyup
ondblclick
h3(zero-or-more "#PCDATA" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript")
idonmousedown
classonmouseup
styleonmouseover
titleonmousemove
langonmouseout
xml:langonkeypress
dironkeydown
onclickonkeyup
ondblclick
h4(zero-or-more "#PCDATA" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript")
idonmousedown
classonmouseup
styleonmouseover
titleonmousemove
langonmouseout
xml:langonkeypress
dironkeydown
onclickonkeyup
ondblclick
h5(zero-or-more "#PCDATA" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript")
idonmousedown
classonmouseup
styleonmouseover
titleonmousemove
langonmouseout
xml:langonkeypress
dironkeydown
onclickonkeyup
ondblclick
h6(zero-or-more "#PCDATA" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript")
idonmousedown
classonmouseup
styleonmouseover
titleonmousemove
langonmouseout
xml:langonkeypress
dironkeydown
onclickonkeyup
ondblclick
ul(one-or-more "li")
idonmousedown
classonmouseup
styleonmouseover
titleonmousemove
langonmouseout
xml:langonkeypress
dironkeydown
onclickonkeyup
ondblclick
ol(one-or-more "li")
idonmousedown
classonmouseup
styleonmouseover
titleonmousemove
langonmouseout
xml:langonkeypress
dironkeydown
onclickonkeyup
ondblclick
li(zero-or-more "#PCDATA" "p" "h1" "h2" "h3" "h4" "h5" "h6" "div" "ul" "ol" "dl" "pre" "hr" "blockquote" "address" "fieldset" "table" "form" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript")
idonmousedown
classonmouseup
styleonmouseover
titleonmousemove
langonmouseout
xml:langonkeypress
dironkeydown
onclickonkeyup
ondblclick
dl(one-or-more "dt" "dd")
idonmousedown
classonmouseup
styleonmouseover
titleonmousemove
langonmouseout
xml:langonkeypress
dironkeydown
onclickonkeyup
ondblclick
dt(zero-or-more "#PCDATA" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript")
idonmousedown
classonmouseup
styleonmouseover
titleonmousemove
langonmouseout
xml:langonkeypress
dironkeydown
onclickonkeyup
ondblclick
dd(zero-or-more "#PCDATA" "p" "h1" "h2" "h3" "h4" "h5" "h6" "div" "ul" "ol" "dl" "pre" "hr" "blockquote" "address" "fieldset" "table" "form" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript")
idonmousedown
classonmouseup
styleonmouseover
titleonmousemove
langonmouseout
xml:langonkeypress
dironkeydown
onclickonkeyup
ondblclick
address(zero-or-more "#PCDATA" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript")
idonmousedown
classonmouseup
styleonmouseover
titleonmousemove
langonmouseout
xml:langonkeypress
dironkeydown
onclickonkeyup
ondblclick
hr"EMPTY"
idonmousedown
classonmouseup
styleonmouseover
titleonmousemove
langonmouseout
xml:langonkeypress
dironkeydown
onclickonkeyup
ondblclick
pre(zero-or-more "#PCDATA" "a" "br" "span" "bdo" "map" "tt" "i" "b" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button")
idonmousedown
classonmouseup
styleonmouseover
titleonmousemove
langonmouseout
xml:langonkeypress
dironkeydown
onclickonkeyup
ondblclickxml:space
blockquote(zero-or-more "p" "h1" "h2" "h3" "h4" "h5" "h6" "div" "ul" "ol" "dl" "pre" "hr" "blockquote" "address" "fieldset" "table" "form" "ins" "del" "script" "noscript")
idonmousedown
classonmouseup
styleonmouseover
titleonmousemove
langonmouseout
xml:langonkeypress
dironkeydown
onclickonkeyup
ondblclickcite
ins(zero-or-more "#PCDATA" "p" "h1" "h2" "h3" "h4" "h5" "h6" "div" "ul" "ol" "dl" "pre" "hr" "blockquote" "address" "fieldset" "table" "form" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript")
idonmouseup
classonmouseover
styleonmousemove
titleonmouseout
langonkeypress
xml:langonkeydown
dironkeyup
onclickcite
ondblclickdatetime
onmousedown
del(zero-or-more "#PCDATA" "p" "h1" "h2" "h3" "h4" "h5" "h6" "div" "ul" "ol" "dl" "pre" "hr" "blockquote" "address" "fieldset" "table" "form" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript")
idonmouseup
classonmouseover
styleonmousemove
titleonmouseout
langonkeypress
xml:langonkeydown
dironkeyup
onclickcite
ondblclickdatetime
onmousedown
a(zero-or-more "#PCDATA" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript")
idonkeydown
classonkeyup
stylecharset
titletype
langname
xml:langhref
dirhreflang
onclickrel
ondblclickrev
onmousedownaccesskey
onmouseupshape
onmouseovercoords
onmousemovetabindex
onmouseoutonfocus
onkeypressonblur
span(zero-or-more "#PCDATA" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript")
idonmousedown
classonmouseup
styleonmouseover
titleonmousemove
langonmouseout
xml:langonkeypress
dironkeydown
onclickonkeyup
ondblclick
bdo(zero-or-more "#PCDATA" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript")
idonmousemove
classonmouseout
styleonkeypress
titleonkeydown
onclickonkeyup
ondblclicklang
onmousedownxml:lang
onmouseupdir
onmouseover
br"EMPTY"
idstyle
classtitle
em(zero-or-more "#PCDATA" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript")
idonmousedown
classonmouseup
styleonmouseover
titleonmousemove
langonmouseout
xml:langonkeypress
dironkeydown
onclickonkeyup
ondblclick
strong(zero-or-more "#PCDATA" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript")
idonmousedown
classonmouseup
styleonmouseover
titleonmousemove
langonmouseout
xml:langonkeypress
dironkeydown
onclickonkeyup
ondblclick
dfn(zero-or-more "#PCDATA" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript")
idonmousedown
classonmouseup
styleonmouseover
titleonmousemove
langonmouseout
xml:langonkeypress
dironkeydown
onclickonkeyup
ondblclick
code(zero-or-more "#PCDATA" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript")
idonmousedown
classonmouseup
styleonmouseover
titleonmousemove
langonmouseout
xml:langonkeypress
dironkeydown
onclickonkeyup
ondblclick
samp(zero-or-more "#PCDATA" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript")
idonmousedown
classonmouseup
styleonmouseover
titleonmousemove
langonmouseout
xml:langonkeypress
dironkeydown
onclickonkeyup
ondblclick
kbd(zero-or-more "#PCDATA" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript")
idonmousedown
classonmouseup
styleonmouseover
titleonmousemove
langonmouseout
xml:langonkeypress
dironkeydown
onclickonkeyup
ondblclick
var(zero-or-more "#PCDATA" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript")
idonmousedown
classonmouseup
styleonmouseover
titleonmousemove
langonmouseout
xml:langonkeypress
dironkeydown
onclickonkeyup
ondblclick
cite(zero-or-more "#PCDATA" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript")
idonmousedown
classonmouseup
styleonmouseover
titleonmousemove
langonmouseout
xml:langonkeypress
dironkeydown
onclickonkeyup
ondblclick
abbr(zero-or-more "#PCDATA" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript")
idonmousedown
classonmouseup
styleonmouseover
titleonmousemove
langonmouseout
xml:langonkeypress
dironkeydown
onclickonkeyup
ondblclick
acronym(zero-or-more "#PCDATA" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript")
idonmousedown
classonmouseup
styleonmouseover
titleonmousemove
langonmouseout
xml:langonkeypress
dironkeydown
onclickonkeyup
ondblclick
q(zero-or-more "#PCDATA" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript")
idonmousedown
classonmouseup
styleonmouseover
titleonmousemove
langonmouseout
xml:langonkeypress
dironkeydown
onclickonkeyup
ondblclickcite
sub(zero-or-more "#PCDATA" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript")
idonmousedown
classonmouseup
styleonmouseover
titleonmousemove
langonmouseout
xml:langonkeypress
dironkeydown
onclickonkeyup
ondblclick
sup(zero-or-more "#PCDATA" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript")
idonmousedown
classonmouseup
styleonmouseover
titleonmousemove
langonmouseout
xml:langonkeypress
dironkeydown
onclickonkeyup
ondblclick
tt(zero-or-more "#PCDATA" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript")
idonmousedown
classonmouseup
styleonmouseover
titleonmousemove
langonmouseout
xml:langonkeypress
dironkeydown
onclickonkeyup
ondblclick
i(zero-or-more "#PCDATA" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript")
idonmousedown
classonmouseup
styleonmouseover
titleonmousemove
langonmouseout
xml:langonkeypress
dironkeydown
onclickonkeyup
ondblclick
b(zero-or-more "#PCDATA" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript")
idonmousedown
classonmouseup
styleonmouseover
titleonmousemove
langonmouseout
xml:langonkeypress
dironkeydown
onclickonkeyup
ondblclick
big(zero-or-more "#PCDATA" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript")
idonmousedown
classonmouseup
styleonmouseover
titleonmousemove
langonmouseout
xml:langonkeypress
dironkeydown
onclickonkeyup
ondblclick
small(zero-or-more "#PCDATA" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript")
idonmousedown
classonmouseup
styleonmouseover
titleonmousemove
langonmouseout
xml:langonkeypress
dironkeydown
onclickonkeyup
ondblclick
object(zero-or-more "#PCDATA" "param" "p" "h1" "h2" "h3" "h4" "h5" "h6" "div" "ul" "ol" "dl" "pre" "hr" "blockquote" "address" "fieldset" "table" "form" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript")
idonkeydown
classonkeyup
styledeclare
titleclassid
langcodebase
xml:langdata
dirtype
onclickcodetype
ondblclickarchive
onmousedownstandby
onmouseupheight
onmouseoverwidth
onmousemoveusemap
onmouseoutname
onkeypresstabindex
param"EMPTY"
idvaluetype
nametype
value
img"EMPTY"
idonmousemove
classonmouseout
styleonkeypress
titleonkeydown
langonkeyup
xml:langsrc
diralt
onclicklongdesc
ondblclickheight
onmousedownwidth
onmouseupusemap
onmouseoverismap
map"((p | h1|h2|h3|h4|h5|h6 | div | ul | ol | dl | pre | hr | blockquote | address | fieldset | table | form | ins | del | script | noscript)+ | area+)"
langonmouseout
xml:langonkeypress
dironkeydown
onclickonkeyup
ondblclickid
onmousedownclass
onmouseupstyle
onmouseovertitle
onmousemovename
area"EMPTY"
idonmouseout
classonkeypress
styleonkeydown
titleonkeyup
langshape
xml:langcoords
dirhref
onclicknohref
ondblclickalt
onmousedowntabindex
onmouseupaccesskey
onmouseoveronfocus
onmousemoveonblur
form(zero-or-more "p" "h1" "h2" "h3" "h4" "h5" "h6" "div" "ul" "ol" "dl" "pre" "hr" "blockquote" "address" "fieldset" "table" "ins" "del" "script" "noscript")
idonmousemove
classonmouseout
styleonkeypress
titleonkeydown
langonkeyup
xml:langaction
dirmethod
onclickenctype
ondblclickonsubmit
onmousedownonreset
onmouseupaccept
onmouseoveraccept-charset
label(zero-or-more "#PCDATA" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript")
idonmouseover
classonmousemove
styleonmouseout
titleonkeypress
langonkeydown
xml:langonkeyup
dirfor
onclickaccesskey
ondblclickonfocus
onmousedownonblur
onmouseup
input"EMPTY"
idname
classvalue
stylechecked
titledisabled
langreadonly
xml:langsize
dirmaxlength
onclicksrc
ondblclickalt
onmousedownusemap
onmouseuptabindex
onmouseoveraccesskey
onmousemoveonfocus
onmouseoutonblur
onkeypressonselect
onkeydownonchange
onkeyupaccept
type
select(one-or-more "optgroup" "option")
idonmouseout
classonkeypress
styleonkeydown
titleonkeyup
langname
xml:langsize
dirmultiple
onclickdisabled
ondblclicktabindex
onmousedownonfocus
onmouseuponblur
onmouseoveronchange
onmousemove
optgroup(one-or-more "option")
idonmouseup
classonmouseover
styleonmousemove
titleonmouseout
langonkeypress
xml:langonkeydown
dironkeyup
onclickdisabled
ondblclicklabel
onmousedown
optionpcdata-checker
idonmouseover
classonmousemove
styleonmouseout
titleonkeypress
langonkeydown
xml:langonkeyup
dirselected
onclickdisabled
ondblclicklabel
onmousedownvalue
onmouseup
textareapcdata-checker
idonkeypress
classonkeydown
styleonkeyup
titlename
langrows
xml:langcols
dirdisabled
onclickreadonly
ondblclicktabindex
onmousedownaccesskey
onmouseuponfocus
onmouseoveronblur
onmousemoveonselect
onmouseoutonchange
fieldset(zero-or-more "#PCDATA" "legend" "p" "h1" "h2" "h3" "h4" "h5" "h6" "div" "ul" "ol" "dl" "pre" "hr" "blockquote" "address" "fieldset" "table" "form" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript")
idonmousedown
classonmouseup
styleonmouseover
titleonmousemove
langonmouseout
xml:langonkeypress
dironkeydown
onclickonkeyup
ondblclick
legend(zero-or-more "#PCDATA" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript")
idonmousedown
classonmouseup
styleonmouseover
titleonmousemove
langonmouseout
xml:langonkeypress
dironkeydown
onclickonkeyup
ondblclickaccesskey
button(zero-or-more "#PCDATA" "p" "h1" "h2" "h3" "h4" "h5" "h6" "div" "ul" "ol" "dl" "pre" "hr" "blockquote" "address" "table" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "ins" "del" "script" "noscript")
idonmouseout
classonkeypress
styleonkeydown
titleonkeyup
langname
xml:langvalue
dirtype
onclickdisabled
ondblclicktabindex
onmousedownaccesskey
onmouseuponfocus
onmouseoveronblur
onmousemove
table"(caption?, (col*|colgroup*), thead?, tfoot?, (tbody+|tr+))"
idonmousemove
classonmouseout
styleonkeypress
titleonkeydown
langonkeyup
xml:langsummary
dirwidth
onclickborder
ondblclickframe
onmousedownrules
onmouseupcellspacing
onmouseovercellpadding
caption(zero-or-more "#PCDATA" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript")
idonmousedown
classonmouseup
styleonmouseover
titleonmousemove
langonmouseout
xml:langonkeypress
dironkeydown
onclickonkeyup
ondblclick
thead(one-or-more "tr")
idonmousemove
classonmouseout
styleonkeypress
titleonkeydown
langonkeyup
xml:langspan
dirwidth
onclickalign
ondblclickchar
onmousedowncharoff
onmouseupvalign
onmouseover
tfoot(one-or-more "tr")
idonmousemove
classonmouseout
styleonkeypress
titleonkeydown
langonkeyup
xml:langspan
dirwidth
onclickalign
ondblclickchar
onmousedowncharoff
onmouseupvalign
onmouseover
tbody(one-or-more "tr")
idonmouseover
classonmousemove
styleonmouseout
titleonkeypress
langonkeydown
xml:langonkeyup
diralign
onclickchar
ondblclickcharoff
onmousedownvalign
onmouseup
colgroup(zero-or-more "col")
idonmouseover
classonmousemove
styleonmouseout
titleonkeypress
langonkeydown
xml:langonkeyup
diralign
onclickchar
ondblclickcharoff
onmousedownvalign
onmouseup
col"EMPTY"
idonmouseover
classonmousemove
styleonmouseout
titleonkeypress
langonkeydown
xml:langonkeyup
diralign
onclickchar
ondblclickcharoff
onmousedownvalign
onmouseup
tr(one-or-more "th" "td")
idonmouseover
classonmousemove
styleonmouseout
titleonkeypress
langonkeydown
xml:langonkeyup
diralign
onclickchar
ondblclickcharoff
onmousedownvalign
onmouseup
th(zero-or-more "#PCDATA" "p" "h1" "h2" "h3" "h4" "h5" "h6" "div" "ul" "ol" "dl" "pre" "hr" "blockquote" "address" "fieldset" "table" "form" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript")
idonkeypress
classonkeydown
styleonkeyup
titleabbr
langaxis
xml:langheaders
dirscope
onclickrowspan
ondblclickcolspan
onmousedownalign
onmouseupchar
onmouseovercharoff
onmousemovevalign
onmouseout
td(zero-or-more "#PCDATA" "p" "h1" "h2" "h3" "h4" "h5" "h6" "div" "ul" "ol" "dl" "pre" "hr" "blockquote" "address" "fieldset" "table" "form" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript")
idonkeypress
classonkeydown
styleonkeyup
titleabbr
langaxis
xml:langheaders
dirscope
onclickrowspan
ondblclickcolspan
onmousedownalign
onmouseupchar
onmouseovercharoff
onmousemovevalign
onmouseout
 

References

Generation of a leq predicate from enumeration
Slide Annotated slide Contents Index
References Textbook 

In some contexts we wish to specify a number of clauses in an arbitrary order

For presentational clarity, we often want to ensure that the clauses are presented in a particular order

Here we want to generate a leq predicate from an enumeration of the desired order

Table. A simple example of an application of generate-leq.
Expression

Value

(define simple-leq? 
  (generate-leq '(z a c b y x) id-1))

(sort-list '(a x y z c c b a) simple-leq?)
(z a a c c b y x)
 

Program: A hypothetical manual page clause. Before we present the clauses of the manual page we want to ensure, that they appear in a particular order, say title, form, description, pre-condition, result, and misc. In this example we will illustrate how to obtain such an ordering in an elegant manner.
(manual-page 
 (form '(show-table rows))
 (title "show-table")
 (description "Presents the table, in terms of rows")
 (parameter "row" "a list of elements")
 (pre-condition "Must be placed before the begin-notes clause")
 (misc "Internally, sets the variable lecture-id")
 (result "returns an HTML string")
)

Program: The functions generate-leq and the helping function list-index .
;; Generate a less than or equal predicate from the
;; enumeration-order. If p is the generated predicate,
;; (p x y) is true if and only if (selector x) comes before
;; (or at the same position) as (selector y) in the
;; enumeration-order. Thus, (selector x) is assumed to give a
;; value in enumeration-order. Comparison with elements in the
;; enumeration-list is done with eq?
(define (generate-leq enumeration-order selector)
  (lambda (x y)
     ; x and y supposed to be elements in enumeration order
     (let ((x-index (list-index (selector x) enumeration-order))
           (y-index (list-index (selector y) enumeration-order)))
       (<= x-index y-index))))

; A helping function of generate-leq.
; Return the position of e in lst. First is 1
; compare with eq?
; if e is not member of lst return (+ 1 (length lst))
(define (list-index e lst)
 (cond ((null? lst) 1)
       ((eq? (car lst) e) 1)
       (else (+ 1 (list-index e (cdr lst))))))

Program: An application of generate-leq which sorts the manual clauses.
(define (syntactic-form name)
  (lambda subclauses (cons name subclauses)))

(define form (syntactic-form 'form))
(define title (syntactic-form 'title))
(define description (syntactic-form 'description))
(define parameter (syntactic-form 'parameter))
(define pre-condition (syntactic-form 'pre-condition))
(define misc (syntactic-form 'misc))
(define result (syntactic-form 'result))

(define (manual-page . clauses)
 (let ((clause-leq? 
         (generate-leq
           '(title form description 
             pre-condition result misc)
           first))
      )
  (let ((sorted-clauses (sort-list clauses clause-leq?)))
    (present-clauses sorted-clauses))))


Collected references
Contents Index
Foldoc: higher order function
The syntax of function definition
Foldoc: map
Foldoc: filter
The LAML general library
The string-merge function
Foldoc: curried function
The XHTML1.0 strict validating mirror
The HTML4.01 transitional validating mirror
The page with the 'Restructuring of lists' exercise
The XHTML1.0 frameset validating mirror
The XHTML1.0 transitional validating mirror

 

Chapter 4: Higher-order Functions
Course home     Author home     About producing this web     Previous lecture (top)     Next lecture (top)     Previous lecture (bund)     Next lecture (bund)     
Generated: July 2, 2013, 09:15:26