How to invert the predicate here?

user_651174 0
Viewed 237

I have the following filter procedure:

; (2) filter
(define (filter test sequence)
  ; return a list of the elements that pass the predicate test
  (let ((elem (if (null? sequence) nil (car sequence)))
        (rest (if (null? sequence) nil (cdr sequence))))
    (cond ((null? sequence) nil)
          ((test elem) (cons elem (filter test rest)))
          (else (filter test rest)))))

And here would be an example of using it to return the even-numbered elements of a list:

(define even? (lambda (x) (= (modulo x 2) 0)))
(define sequence '(1 2 3 4 5 8 9 11 13 14 15 16 17))
(filter even? sequence)
; (2 4 8 14 16)

Is there a simple way to use the not test to invert the selection? For example, I thought the following might work:

(filter (not even?) sequence)

But it returns an error. I can define odd separately, of course:

(define odd?  (lambda (x) (not (even? x))))

But I'm trying not to do this. Is there a way to write the odd procedure without defining it directly, but instead using the not directly like I'm trying to do above?

racket function-composition scheme lisp predicate
3 Answers

There is a complement function in Common Lisp that does what I think you are looking for. complement is a higher-order procedure that takes a procedure as its argument, and returns a procedure that takes the same arguments as the input procedure and performs the same actions, but the returned truth value is inverted.

Racket has a similar procedure, negate, and it is easy enough to implement this in Scheme:

(define (complement f)
  (lambda xs (not (apply f xs))))

> (filter even? '(1 2 3 4 5))
(2 4)
> (filter (complement even?) '(1 2 3 4 5))
(1 3 5)
> (> 1 2 3 4 5)
#f
> ((complement >) 1 2 3 4 5)
#t

And in Racket:

scratch.rkt> (filter even? '(1 2 3 4 5))
'(2 4)
scratch.rkt> (filter (negate even?) '(1 2 3 4 5))
'(1 3 5)
scratch.rkt> (> 1 2 3 4 5)
#f
scratch.rkt> ((negate >) 1 2 3 4 5)
#t
user_68798260

The general answer to this is to simply compose not and the function you care about. Racket has a compose function which does this, but you can easily write a simple one yourself:

(define (compose-1 . functions)
  ;; simple-minded compose: each function other than the last must
  ;; take just one argument; all functions should return just one
  ;; value.
  (define (compose-loop fns)
    (cond
      ((null? fns)
       (λ (x) x))
      ((null? (cdr fns))
       (car fns))
      (else
       (λ (x) ((car fns) ((compose-loop (cdr fns)) x))))))
  (compose-loop functions))

Making it efficient and more general takes more work of course.

Then you can define odd? (which is already defined of course):

(define odd? (compose-1 not even)

Or in fact define a more general CL-style complement function:

(define (complement f)
  (compose-1 not f))
Admin1

One option is to write an invert function which will curry things along (so the initial function still accepts one argument) until the final evaluation occurs:

(define invert (lambda (func) (lambda (x) (not (func x)))))
(define sequence '(1 2 3 4 5 6 8 9 11 13 14 15 16 17))
(filter (invert even?) sequence)
; (1 3 5 9 11 13 15 17)
user_6511740
Related