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

[Kevin Wortman <kwortman@xxxxxxxxx>]

I see two implementation strategies: using call/cc to escape from the
hash-table-for-each with each value, or converting each set/bag to an
alist and manipulating them as lists.  The first is more Schemey and
uses less overt storage, but has a hidden time/space cost of copying
stacks on Schemes where call/cc does that.  I lean to the second
strategy.  Opinions?

Both of those sound reasonable, and an implementer is free to choose anything that works, right? Personally, I default to using fold whenever I can. I think the following would work as a 2-ary Cartesian product, and can generalize to n-ary:

(define (cartesian left right)

  (set-fold (lambda (a tuples)

                (set-fold (lambda (b tuples)

                              (cons (list a b) tuples))

                            tuples

                            right))

               '()

               left))

 

I think the list strategy is clearly better here, particularly as the
number of stacks would be proportional to the size of the set rather
than the number of sets, as with cartesian product.

Yeah there is a slick recursive algorithm on lists:

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

      list))

I think you can replace fold and cons with set-fold and set-adjoin resp. to operate on sets directly without ever converting to a list.

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.

Kevin Wortman