[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: LAST CALL for SRFI-113, Sets and bags

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.


I don't quite see the algo yet, but I feel that it's out there (like
the truth).

Nice X-Files reference (I think). Here is one approach:

Suppose you want the Cartesian product S0 × S1 ×... × Sn and have already computed (S1 ×... × Sn) as a list L of tuples, each tuple being a list of n elements. You can augment L to become a valid product S0 × (S1 ×... × Sn) by appending together one copy of L, for each x in S0, where x is prepended to each tuple already in L. In other words, add a new leftmost column to the tuples. Scheme code:

(define (cartesian . sets)
  (fold-right (lambda (set tuples)
        (append-map! (lambda (element)
                   (map (cute cons element <>) tuples))
                 set))
          '(())
          sets))

To work on set objects directly you'd need to change "set))" to "(set->list set)))".

Best regards,
Kevin Wortman