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

> I think the alist conversion procedures are important since they allow bags
> to be defined in program text and serialized with read and write.

I agree, and there is no question of flushing bag->alist or alist->bag.
It's only alist->bag! whose consistency and utility I'm beginning to
question.

> I guess the pertinent question is: does ((a . 1) (1 . 2)) mean (1) "1 copy
> of a, and then *an additional* 2 copies of a"; or (2) "currently the count
> of a's is 1; in the past the count for a was 2." The semantics of assoc
> make it seem that conventionally, (2) is how alists with duplicate entries
> are interpreted. Which I think is consistent with your first definition for
> how alist->bag and alist->bag! should work.

I agree that assoc semantics should dominate, and all entries after the
first should be ignored.  The question then is:  given an implicit bag
defined by an alist with duplicate entries ignored, what is the semantics
of merging this into an existing bag?  Is it union or sum or replacement?
It's not obvious to me that either semantics is a clear winner.

So perhaps we should only standardize alist->bag, and leave bag merger to
the user.  This also suggests that we need a procedure bag-sum(!), with
semantics {a, a, a} + {a, a} = {a, a, a, a, a}.  The current definition
of bag-union gives {a, a, a} on the assumption that the elements are
indistinguishable, whereas bag-sum would treat them as distinguishable.
Checking Wikipedia s.v. Multiset, I find that sum is defined precisely
this way, as well as scalar product: {a, a, a} x 2 = {a, a, a, a, a, a}.

Lastly, I think we should have cartesian product of both sets and bags.
I don't know how I came to overlook it before, probably because none of
the other libraries I have looked at (Scheme, Lisp, Python, Haskell,
etc.) have given it.  It is a fundamental set operation, however.
I'll assume that the tuples (a,b) in the product should be represented
in Scheme as (a b), unless someone has strong contrary feelings.

-- 
John Cowan          http://www.ccil.org/~cowan        cowan@xxxxxxxx
"The exception proves the rule."  Dimbulbs think: "Your counterexample proves
my theory."  Latin students think "'Probat' means 'tests': the exception puts
the rule to the proof."  But legal historians know it means "Evidence for an
exception is evidence of the existence of a rule in cases not excepted from."