[Haskell-cafe] ANN: signed-multiset-0.1
Stefan Holdermans
stefan at vectorfabrics.com
Fri Apr 20 10:55:00 CEST 2012
Richard,
Thanks for your excellent feedback! Very helpful!
> Signed multisets are unfamiliar to most of us, and I for one found the paper a little fast-paced. Can you put a bit more into the documentation?
Definitely. That's what weekends are for... :) I'll add some sections to the documentation that explain the main concepts and intuitions.
> Just for starters, I found it confusing when the documentation talks about "an element with multiplicity zero", because in the _paper_ a value that has multiplicity zero in an mzset is NOT an element of it.
I see... It seems that with multisets every value of the appropriate type is an element of the set, but some values (i.e., those with multiplicities > 0) are more of an element than others (i.e., those with multiplicity 0). In the paper this is reflected by having the "element-of" relation a ternary relation between elements, sets, and multiplicities (with a "functional dependency" from elements and sets to multiplicities). Confusingly, "not-an-element-of" notation is used as an abbreviation for "element-of with multiplicity zero".
The library labels elements with multiplicities > 0 as "members".
> For a specific example, I haven't the faintest intuition about
> what 'map' should do. Suppose we have
> {(k1)x1, (k2)x2}
> and f x1 == f x2 = y. Should the value of map f {...} be
> {(k1+k2)y} or {(k1`max`k2)y} or what?
"Should" is a tricky term here. It depends on what you consider to be the structure of a multiset. Currently, map applies its function argument copywise:
{x1_1, x1_2, ..., x1_k1, x2_1, x2_2, ..., x2_k2 }
| | | | | |
| f | f | f | f | f | f
v v v v v v
{y_1, y_2, ..., y_k1, y_k1+1, y_k1+2, ..., y_k1+k2}∑
That is, we preserve the additive structure.
But perhaps this is inconsistent: the Monoid instance for SignedMultiset operates on the extremal structure rather than the additive structure. A wrapper type Additive,
newtype Additive a = Additive (SignedMultiset a)
supplies a monoid instance that operates on the additive structure. So, perhaps, it's better to have map as it is implemented now, operate on Additive rather than SignedMultiset and have a map for SignedMultiset that uses max rather than (+).
A rationale for this would be that, this way, map would be a proper generalisation of ordinary sets. (The same rationale has been applied to union.)
Pondering over this, I realise that the difference operator also doesn't property generalise the concept for ordinary sets. However, that concept indeed seems a bit more tricky to generalise.
> Are you _sure_ that the definitions of isSubmultisetOf and
> isProperSubmultisetOf are correct? Proper sub<thing> is
> normally taken as requiring that only *one* member of the
> larger collection occur strictly fewer times in the smaller;
> here you require that for *all*.
You are right: isProperSubmultisetOf is too restrictive. I'll fix it.
Thanks,
Stefan
More information about the Haskell-Cafe
mailing list