Scheme : I have no idea to implement given functio

问题:

It's the exercise of "Programming language pragmatics, Michael Scott" .

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

I think that question require function which satisfy every predicate not only above. But I don't have any idea to implement such function. Please help.

回答1:

The filter procedure already exists in most Scheme implementations, it behaves as expected:

(filter (lambda (x) (< x 5)) '(3 9 5 8 2 4 7))
=> '(3 2 4)

Now, if the question is how to implement it, it's rather simple - I'll give you some hints so you can write it by yourself. The trick here is noticing that the procedure is receiving another procedure as parameter, a predicate in the sense that it'll return #t or #f when applied to each of the elements in the input list. Those that evaluate to #t are kept in the output list, those that evaluate to #f are discarded. Here's the skeleton of the solution, fill-in the blanks:

(define (filter pred? lst)
  (cond (<???>       ; if the list is empty
         <???>)      ; return the empty list
        (<???>       ; apply pred? on the first element, if it's #t
         (cons <???> ; then cons the first element
               (filter pred? <???>))) ; and advance recursion
        (else (filter pred? <???>)))) ; else just advance recursion