This page is part of the web mail archives of SRFI 113 from before July 7th, 2015. The new archives for SRFI 113 contain all messages, not just those from before July 7th, 2015.
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 cowan@xxxxxxxx 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