[plt-scheme] re: the fastest way to calc a cartesian product

Good idea to "remind" people of functional representations of things.  
Now do that in Java without getting carpal tunnel :-)

How's Radford? -- Matthias

On Sep 19, 2006, at 1:02 PM, Barland, Ian wrote:

> This is NOT the answer you were looking for...
>
> But if you want to allow *infinite* sets, and take "element-of" as  
> your only
> primitive (and forgo being able to iterate over elements of the set),
> you can represent sets as their element-of (indicator) function.
> Then Cartesian-product (and union and intersection) are O(1)  :-)
>
> An uncommented example:
> ===========
> (define cars  (lambda (elt) (memq elt '(vw saab bmw audi))))
> (define evens (lambda (elt) (and (number? elt) (even? elt))))
>
> (define (element-of? elt set) (set elt))
>
> (define (cartesian-product A B)
>   (lambda (elt)
>      (and (length=2? elt)
>           (element-of? (first elt) A)
>           (element-of? (first elt) B))))
>
>
> (define (length=2? any)
>   (and (cons? any)
>        (cons? (rest any))
>        (empty? (rest (rest any)))))
>
> (define evenEuroCars (cartesian-product evens cars))
> (element-of? '(4 bmw) evenEuroCars) ; = #t
> (element-of? '(bmw 4) evenEuroCars) ; = #f
> ==============
>
> I actually use this in discrete math when introducing sets,
> as a tangential way to reinforce data abstraction:
> I give them a data definition which allows both lists and functions
> as ways to represent Sets.
> If they follow the book's math-definition of cartesian-product
> word-for-word, they are naturally led to the above code.
> If they are focused on the implementation of their inputs, they  
> instead
> gravitate into thinking their inputs are lists, and that therefore  
> their
> output also needs to be a list, and are then stuck with the problem  
> you are
> asking about.
>
> _________________________________________________
>   For list-related administrative tasks:
>   http://list.cs.brown.edu/mailman/listinfo/plt-scheme