Path: utzoo!dptcdc!jarvis.csri.toronto.edu!mailrus!ames!zodiac!ZOOKS.ADS.COM!rar
From: rar@ZOOKS.ADS.COM (Bob Riemenschneider)
Newsgroups: comp.lang.lisp
Subject: Re: Cartesian product
Message-ID: <8904182110.AA21720@zooks.ads.com>
Date: 18 Apr 89 21:10:33 GMT
Sender: daemon@zodiac.UUCP
Lines: 47

=>   From: Duchier-Denys@cs.yale.edu (Denys Duchier)
=>
=>   In article <3677@sdsu.UUCP>, ucselx!maxc0186@sdsu writes:
=>   > Does anyone have a lisp function that performs the Cartesian product
=>   > on a list, i.e.,
=>   >   (CARTESIAN '((A B) (C D) (E F))) will return
=>   >   ((A C E) (A C F) (A D E) (A D F) (B C E) (B C F) (B D E) (B D F))
=>   > not necessarily in that order.
=>
=>   (DEFUN CARTESIAN (L)
=>     (COND ((NULL L) NIL)
=>	   ((NULL (CDR L))
=>	    (MAPCAR #'LIST (CAR L)))
=>	   (T (MAPCAN #'(LAMBDA (X) (MAPCAR #'(LAMBDA (Y) (CONS Y X)) (CAR L)))
=>		      (CARTESIAN (CDR L))))))
=>
=>   --Denys

Now that ucselx!maxc0186@sdsu's homework deadline is, presumably, past, I
thought it might be worthwhile pointing out a small bug in Denys Duchier's
proposed solution.

Note that according to the definition of Cartesian product of a sequence of
sets,

      -----                     | |
       | |  X = { f: dom(X) --> | | X | for every i in dom(X), f(i) in X(i) }
       | |                       _

the Cartesian product of the empty sequence is the set consisting of the 
empty function.  Thus, (CARTESIAN '()) should return (()), not ().

The reason I brought this up is not that I think it's terribly important
that (CARTESIAN '()) ==> (NIL), but because not getting this right wound
up complicating the solution.  Denys has the recursion bottom out when
L's cdr is empty, and treats an empty L as a special case; once you fix the
bug, the definition can be simplified to

   (DEFUN CARTESIAN (L)
     (COND ((NULL L) '(()))
	   (T (MAPCAN #'(LAMBDA (X) (MAPCAR #'(LAMBDA (Y) (CONS Y X)) (CAR L)))
		      (CARTESIAN (CDR L))))))

So getting the mathematical "specification" right results in simpler code,
as is often the case.

							-- rar