[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.



Kevin Wortman scripsit:

> Yes, let's add a bag-sum and bag-sum!. I forgot that multiset union
> and summation were different operations.

Added to the SRFI, along with bag-product(!) for scalar product.
I'll add it to the code soon.

> This makes defining alist->bag! difficult; there are two ways of
> merging bags and it is unclear which should be used. I am onboard
> with just removing alist->bag!. The only downside I can see is that
> some clients get forced to use a pure procedure where a linear-update
> one may've sufficed, which adds a modest constant factor, which seems
> acceptable.

Removed from both code and SRFI, and SRFI pushed to ccil.org.

> I've found myself coding up my own Cartesian product several times,
> so I support adding a procedure for that. A list (a b) seems like
> the right data structure for each of the resulting tuples. I suggest
> standardizing an n-ary product, not just binary, so each tuple has as
> many elements as the number of set multiplicands.

+1

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?

> Another operation worth considering is power set. It's useful, but is
> O(2^n), so it would need a disclaimer about that.

+1

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.

-- 
John Cowan          http://www.ccil.org/~cowan        cowan@xxxxxxxx
As we all know, civil libertarians are not the friskiest group around --
comes from  forever being on the qui vive for the sound of jack-booted
fascism coming down the pike.           --Molly Ivins