[r6rs-discuss] On the arity of comparators

[Alan Bawden]

   Date: Mon, 20 Oct 2008 10:34:28 -0700
   From: Ray Dillinger <bear at sonic.net>

   It has to do with a recursive implementation where the zero-argument
   or single-argument case is the base case.

   Date: Mon, 20 Oct 2008 11:00:23 -0700
   From: Ray Dillinger <bear at sonic.net>

   Sigh.  That'll teach me to trust my memory.  I shoulda wrote: 

   ;; be wary of bugs in this code; I am typing it from memory 
   ;; and have not tested it. 
   (define gencomp? (lambda (paircomp?)
       (define comp? (lambda  arglist
	   (cond ((empty-list? arglist) #t)
		 ((empty-list? (cdr arglist) #t)
		 ((paircomp? (car arglist) (cadr arglist)) 
		  (comp? (cdr arglist)))
		 (else #f))))
       comp?))

Correcting the bugs present only because you didn't test it:

    (define (gencomp? paircomp?)
      (define (comp? . arglist)
	(cond ((null? arglist) #t)
	      ((null? (cdr arglist)) #t)
	      ((paircomp? (car arglist) (cadr arglist)) 
	       (apply comp? (cdr arglist)))
	      (else #f)))
      comp?)

Or perhaps (because I hate to use `apply' unnecessarily):

    (define (gencomp? paircomp?)
      (define (comp? arglist)
	(cond ((null? arglist) #t)
	      ((null? (cdr arglist)) #t)
	      ((paircomp? (car arglist) (cadr arglist)) 
	       (comp? (cdr arglist)))
	      (else #f)))
      (lambda arglist
	(comp? arglist)))

Now I notice that the very first `cond' clause can only be true on the very
first call to `comp?' -- `arglist' is guaranteed to be non-empty on every
subsequent call.  So I can re-write it is follows:

    (define (gencomp? paircomp?)
      (define (comp? arglist)
	(cond ((null? (cdr arglist)) #t)
	      ((paircomp? (car arglist) (cadr arglist)) 
	       (comp? (cdr arglist)))
	      (else #f)))
      (lambda arglist
	(cond ((null? arglist) #t)
	      (else (comp? arglist)))))

That `null?' check in the preamble looks pretty arbitrary now.  It doesn't
have anything to do with the base case of the recursion.  The base case
occurs when the list has length one, not zero.  The decision to return #T
for zero arguments, if it is the correct one, must be driven by some other
concern.  (Like some nice mathematical identity.)

Now there might be some other way to write this code so that having the
zero argument case return #T really is the base case, but I don't see how
to do it.

I think I've said the same thing in three different ways now...