# 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)
(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.