Avoiding circularity: a simple example

Here’s a simple example of dealing with a naturally circular function definition.

Common Lisp has a predicate called some. Here is what looks like a natural definition of a slightly more limited version of this predicate, which only works on lists, in Racket:

(define (some? predicate . lists)
  ;; Just avoid the spread/nospread problem
  (some*? predicate lists))

(define (some*? predicate lists)
  (cond
    [(null? lists)
     ;; if there are no elements the predicate is not true
     #f]
    [(some? null? lists)
     ;; if any of the lists is empty we've failed
     #f]
    [(apply predicate (map first lists))
     ;; The predicate is true on the first elements
     #t]
    [else
     (some*? predicate (map rest lists))]))

Well, that looks neat, right? Except it is very obviously doomed because some*? falls immediately into an infinite recursion.

Well, the trick to avoid this is to check whether the predicate is null? and handle that case explicitly:

(define (some*? predicate lists)
  (cond
    [(null? lists)
     ;; 
     (error 'some? "need at least one list")]
    [(eq? predicate null?)
     ;; Catch the circularity and defang it
     (match lists
       [(list (? list? l))
        (cond
          [(null? l)
           #f]
          [(null? (first l))
           #t]
          [else
           (some? null? (rest l))])]
       [_ (error 'some? "~S bogus for null?" lists)])]
    [(some? null? lists)
     ;; if any of the lists is empty we've failed
     #f]
    [(apply predicate (map first lists))
     ;; The predicate is true on the first elements
     #t]
    [else
     (some*? predicate (map rest lists))]))

And this now works fine.

Of course this is a rather inefficient version of such a predicate, but it’s nice. Well, I think it is.

Note: a previous version of this had an extremely broken version of some*? which worked, by coincidence, sometimes.