The filtering function

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

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

A straightforward filter function