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