Lecture overview -- Keyboard shortcut: 'u'  Previous page: Filtering -- Keyboard shortcut: 'p'  Next page: Examples of filtering -- Keyboard shortcut: 'n'  Lecture notes - all slides and notes together  slide -- Keyboard shortcut: 't'  Textbook -- Keyboard shortcut: 'v'  Help page about these notes  Alphabetic index  Course home    Lecture 4 - Page 12 : 34
Functional Programming in Scheme
Higher-order Functions
The filtering function

The next item on the agenda is an implementation of filter .

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

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

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

Go to exerciseA straightforward filter function