Theme index -- Keyboard shortcut: 'u'  Previous theme in this lecture -- Keyboard shortcut: 'p'  Next slide in this lecture -- Keyboard shortcut: 'n'Higher-order Functions
15.  Mapping and filtering

In this chapter we will focus on higher-order functions that work on lists. It turns out that the appropriate combinations of these make it possible to solve a variety of different list processing problems.

15.1 Classical higher-order functions: Overview15.5 Filtering
15.2 Mapping15.6 The filtering function
15.3 The mapping function15.7 Examples of filtering
15.4 Examples of mapping

15.1.  Classical higher-order functions: Overview
Contents   Up Previous Next   Slide    Subject index Program index Exercise index 

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


15.2.  Mapping
Contents   Up Previous Next   Slide    Subject index Program index Exercise index 

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

The idea of mapping is illustrated below.

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


15.3.  The mapping function
Contents   Up Previous Next   Slide    Subject index Program index Exercise index 

(define (mymap f lst)
  (if (null? lst)
      (cons (f (car lst))
            (mymap f (cdr lst)))))
Program 15.1    An implementation of map.

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

There is no solution to this exercise


15.4.  Examples of mapping
Contents   Up Previous Next   Slide    Subject index Program index Exercise index 



  (list 1 'en "en" 2 'to "to"))
(#f #f #t #f #f #t)
   (lambda (x) (* 2 x))
   (list 10 20 30 40))
(20 40 60 80)
   (compose li 
    (compose b 
     (lambda (x)
      (font-color red x))))
   (list "a" "b" "c")
  • a
  • b
  • c
Same as above
   <b><font color = "#ff0000">a</font></b>
   <b><font color = "#ff0000">b</font></b>
    <b><font color = "#ff0000">c</font></b>
Table 15.1    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.


15.5.  Filtering
Contents   Up Previous Next   Slide    Subject index Program index Exercise index 

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

The figure below illustrates the filtering idea.

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


15.6.  The filtering function
Contents   Up Previous Next   Slide    Subject index Program index Exercise index 

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

As a consequence of the observation above, we now program a tail recursive version of filter. Notice that it is the function filter-help, which does the real filtering job.

(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)))
           (filter-help pred (cdr lst)  res))))
Program 15.2    An implementation of filter which is memory efficient.

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



15.7.  Examples of filtering
Contents   Up Previous Next   Slide    Subject index Program index Exercise index 



 '(1 2 3 4 5))
(2 4)
  (negate even?)
  '(1 2 3 4 5))
(1 3 5)
 (map li
  (filter string?
     1 'a "First" "Second" 3))))
  1. First
  2. Second
Same as above
  <li>First</li> <li>Second</li>
Table 15.2    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.

Generated: Tuesday July 2, 2013, 09:15:35
Theme index -- Keyboard shortcut: 'u'  Previous theme in this lecture -- Keyboard shortcut: 'p'  Next slide in this lecture -- Keyboard shortcut: 'n'