CODEWITHSUNDEEP
functional-programmingschemeracketfold
user548976
user548976

Reputation: 49

(Scheme) Check a list of item are all satisfied an logical relation

I'm currently studying Scheme and encounter a question which description such like: Define and implement a function that takes something like a logical operator check and a list xs, then check whether that (check a b) evaluate to true for all two near by element a b in list xs.

Some example below like:

(check < '(15 16 17 18)) 
#t

(check > '(5)) 
#t

(check > '()) 
#t

(check (lambda (a b) (eq? b (+ a 1))) '(11 12 13))
#t

(check eq? '(4 4 5))
#f

In my view, I think this question similar to check a list is sorted in increasing order or not, but the implementation may have some difference. I intend to define a recursive function involved with foldl and do some conditional checks, but my question is how to detect which the logical operator is and how they doing their work in my code, so anyone could help with it? Thank you in advance.

Upvotes: 2

Views: 552

Answers (2)

coredump
coredump

Reputation: 38809

There are two trivial cases where the function can return true, namely empty lists and lists with a single element. You check for empty lists with null?. You need to check first whether the list is empty, and if it isn't, if its sublist is empty (in which case there is necessarily only one element). If any of those lists is empty, the predicate trivially returns true.

Otherwise, in the general case, the predicate might return true only if check works for the pair of elements (that pair exists, since we ruled out lists of size 0 and 1), and if the sublist also satisfies the predicate.

(define (every-pair-check? check xs)
  (or (null? xs)
      (null? (cdr xs))
      (and (check (car xs) (cadr xs))
           (every-pair-check? check (cdr xs)))))

Upvotes: 3

Gwang-Jin Kim
Gwang-Jin Kim

Reputation: 9865

(define (check-every? check-operator lst)
  (cond ((or (null? lst) (= (length lst) 1)) #t)
        ((check-operator (car lst) (cadr lst)) (check-every? check-operator (cdr lst)))
        (else #f)))

This stops as soon first #f test occurs, thus is efficient.

I wanted to save some checks by this:

;; cave! Erroneous code!!
(define (check-every? check-operator lst)
  (cond ((and (null? (cdr lst)) (<= (length lst) 1)) #t)
        ((check-operator (car lst) (cadr lst)) (check-every? check-operator (cdr lst)))
        (else #f)))

This strategy would work in common lisp, because (cdr '()) in common lisp returns '(). But in Racket/Scheme, this returns an error. How confusing! Thanks to remind me, @coredump!

My thinking was:

(null? (cdr lst)) is a hack for (or (null? lst) (= (length lst) 1)), however, if one element of lst is '(), then we would be in trouble. But with normal number list it works. Otherwise, one should use the longer test. Now I corrected to (and (null? (cdr lst)) (<= (length lst) 1)), which - due to short circuitry of and - tests only for (null? (cdr lst)), but if it is true, checks in addition, whether length of lst is 1 or zero. Only then, it returns #t for this case. So this form catches the case, that lst could contain a '() as an element somwhere else than in the last position, by still minimizing the number of tests per cycle.

But okay, since this is not possible in Racket, the first version is the shortest then ...

Upvotes: 2

Related Questions