Kevin Wortman scripsit:

> (define (cartesian left right)
>   (set-fold (lambda (a tuples)
>                 (set-fold (lambda (b tuples)
>                               (cons (list a b) tuples))
>                             tuples
>                             right))
>                '()
>                left))

Yes, nested folds will work up to the number of folds you nest, but not
for arbitrarily many sets.  It's like arrays: if there is a limit of N
dimensions, then N nested loops will suffice to process the elements,
but without a limit you need to use an external iterator.

Unfortunately, there is no natural external iterator for sets.  Call/cc
will let you create them, but lists can be externally iterated naturally.
I don't quite see the algo yet, but I feel that it's out there (like
the truth).

Of course, you can also create the products two at a time, merging as you
go, but you end up needing O(log k * n) space or worse, where k is the
number of sets provided.  This can thrash GC if the sets are large.

>   (define (powerset list)
>     (fold (lambda (x subsets)
>         (append subsets
>             (map (cute cons x <>) subsets)))
>       '(())
>       list))

Nice!  Thanks.

> One question here, is whether the returned value should be a list of sets,
> or a set of sets. Mathematically a power set is a set of sets, but
> constructing a list of sets is cheaper.

Good question.  I'll think about that one further.

--
John Cowan          http://www.ccil.org/~cowan        xxxxxx@ccil.org
One of the oil men in heaven started a rumor of a gusher down in hell.  All
the other oil men left in a hurry for hell.  As he gets to thinking about
the rumor he had started he says to himself there might be something in
it after all.  So he leaves for hell in a hurry.    --Carl Sandburg