Need help on this one using scheme function Return a list containing all elements of a given list that satisfy a given predicate. For example, (filter (lambda (x) (< x 5)) '(3 9 5 8 2 4 7)) should return (3 2 4).
5 Answers
filterb - just in case there is already a function called filter.
(define filterb (lambda (pred lst) (cond ((null? lst) '()) ((pred (car lst)) (cons (car lst) (filterb pred (cdr lst)))) (else (filterb pred (cdr lst)))))) Here it is, though I am sure it can be made to look nicer.
A simple way to write the filter procedure:
(define (my-filter pred lst) (cond ((null? lst) null) ((pred (first lst)) (cons (first lst) (my-filter pred (rest lst)))) (else (my-filter pred (rest lst))))) Notice that I named the procedure my-filter, because a built-in procedure called filter already exists and it's not a good idea to overwrite its definition.
The textbook definition of filter is the (non-tail) recursive one that other posters have shown—and it's important to understand that one. However, if you're writing it as a library function, it's useful to figure out how to do it with tail recursion, so that you don't blow up the stack or heap with long lists:
(define (filter pred? list) (define (filter-aux result current-pair xs) (cond ((null? xs) result) ((pred? (car xs)) (set-cdr! current-pair (cons (car xs) '())) (filter-aux result (cdr current-pair) (cdr xs))) (else (filter-aux result current-pair (cdr xs))))) (let ((init (cons 'throw-me-out '()))) (filter-aux (cdr init) init list))) Or, using the let loop syntax:
(define (filter pred? xs) (let ((result (cons 'throw-me-out '())) (xs xs)) (let loop ((current-pair result)) (cond ((null? xs) (cdr result)) ((pred? (car xs)) (set-cdr! current-pair (cons (car xs) '())) (loop (cdr current-pair) (cdr xs))) (else (loop current-pair (cdr xs))))))) Try defining filter as an instance of fold-right:
(define (my-filter op xs) (fold-right (lambda (next result) ...) '() xs)) Hint: use if and cons
For an alternate tail-recursive filter that doesn't require mutable lists, you could use something like this:
(define (my-filter f lst) (define (iter lst result) (cond ((null? lst) (reverse result)) ((f (car lst)) (iter (cdr lst) (cons (car lst) result))) (else (iter (cdr lst) result)))) (iter lst '())) Reverse requires you to walk the list a second time, but it can be implemented in O(n) time with constant stack space on immutable lists, so the overall time is still O(n).
