Wren, Sjoerd,
This is not just about map, but it also a problem for the Monoid instance.
You are basically adding an extra identity element, 0, to the max monoid,
which works but is weird.
Still that's how union is typically defined for hybrid sets. It's what
happens if want union and
On Apr 25, 2012, at 11:39 AM, Stefan Holdermans wrote:
The union of two sets is typically defined as the smallest set that is a
superset of both the operands; this definition extends nicely for multisets
and hybrid sets [1,2,3].
[3] differs from [1] and [2] (and your implementation). [3]
Sjoerd,
I am sorry, as I already wrote, I decided to deprecate the package.
[3] defines the union as h(u) = max(f(u), g(u)) where f, g and h are
multiplicity functions.
Which is the same, as [3] is about multisets, not signed multisets.
[...] and this is also what your implementation does.
On Apr 26, 2012, at 12:54 AM, Stefan Holdermans wrote:
Sjoerd,
I am sorry, as I already wrote, I decided to deprecate the package.
That's too bad, I really love these kind of data structures. (That's why I keep
ranting about it, sorry about that.)
[3] defines the union as h(u) =
Sjoerd,
[3] defines the union as h(u) = max(f(u), g(u)) where f, g and h are
multiplicity functions.
Which is the same, as [3] is about multisets, not signed multisets.
Chapter 3 of [3] is about Hybrid Sets.
And there the union is defined by taking the *minimum* of multiplicities, which
On 4/25/12 5:39 AM, Stefan Holdermans wrote:
The union of two sets is typically defined as the smallest set that is a
superset of both the operands;
Or, the smallest set containing all the elements of both/all operands.
The two definitions coincide for sets.
They diverge for bags/multisets:
On 4/25/12 7:27 PM, Stefan Holdermans wrote:
Sjoerd,
[3] defines the union as h(u) = max(f(u), g(u)) where f, g and h are
multiplicity functions.
Which is the same, as [3] is about multisets, not signed multisets.
Chapter 3 of [3] is about Hybrid Sets.
And there the union is defined by
Sjoerd,
I have a hard time believing you have implemented the semantics that people
have agreed on to be a sensible semantics for hybrid sets.
Noted.
Cheers,
Stefan
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
On 4/23/12 9:18 AM, Stefan Holdermans wrote:
Sjoerd,
This is not just about map, but it also a problem for the Monoid instance. You
are basically adding an extra identity element, 0, to the max monoid, which
works but is weird.
Still that's how union is typically defined for hybrid sets.
I don't think max would be a good choice, as that would mean that the default
multiplicity would have to be negative infinity (the identity element of max)
instead of 0, and then using Int as the type for multiplicity would not cut it.
greetings,
Sjoerd
On Apr 20, 2012, at 11:02 AM, Stefan
Sjoerd,
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?
I don't think max would be a good choice, as that would mean
This is not just about map, but it also a problem for the Monoid instance. You
are basically adding an extra identity element, 0, to the max monoid, which
works but is weird. You'll have to call norm everywhere to make it work, f.e.
you would expect this to work:
empty' = insert () $ delete ()
Sjoerd,
This is not just about map, but it also a problem for the Monoid instance.
You are basically adding an extra identity element, 0, to the max monoid,
which works but is weird.
Still that's how union is typically defined for hybrid sets. It's what happens
if want union and empty to
On Apr 23, 2012, at 3:18 PM, Stefan Holdermans wrote:
Sjoerd,
This is not just about map, but it also a problem for the Monoid instance.
You are basically adding an extra identity element, 0, to the max monoid,
which works but is weird.
Still that's how union is typically defined for
Sjoerd,
This is not just about map, but it also a problem for the Monoid instance.
You are basically adding an extra identity element, 0, to the max monoid,
which works but is weird.
Still that's how union is typically defined for hybrid sets. It's what
happens if want union and empty to
On Apr 23, 2012, at 4:34 PM, Stefan Holdermans wrote:
Sjoerd,
This is not just about map, but it also a problem for the Monoid instance.
You are basically adding an extra identity element, 0, to the max monoid,
which works but is weird.
Still that's how union is typically defined for
Sjoerd,
Then why would you want that?
You don't have to. (SignedMultiset a, additiveUnion, empty) gives you the
Monoid that you seem to have a preference for. The library supplies it
through the Additive wrapper. The point is that you have a choice: different
applications may ask for
On Apr 23, 2012, at 7:04 PM, Stefan Holdermans wrote:
if this is what people have agreed on to be a sensible semantics for hybrid
sets, I am fine implementing it like this.
I have a hard time believing you have implemented the semantics that people
have agreed on to be a sensible semantics
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
Wren,
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?
Good question. I'd suppose that they should be parametrized by
Release early, release often. Here's a second version:
http://hackage.haskell.org/package/signed-multiset-0.2
Changes:
* Added the functions Data.SignedMultiset.isPositive and
Data.SignedMultiset.isNegative, which return whether all elements in a
signed multiset have respectively
On 19/04/2012 4:10 AM, Stefan Holdermans wrote:
Release early, release often. Here's a second version:
http://hackage.haskell.org/package/signed-multiset-0.2
Very cool.
In the literature, we have found [1] that these are sometimes also
called 'hybrid sets'. They do have some rather
Jacques,
In the literature, we have found [1] that these are sometimes also called
'hybrid sets'.
They also go by the name of 'shadow sets', which also has a cool ring to it. ;)
PS: the Haddock did not work for 0.2, but did for 0.1, you might want to look
into that.
As I just uploaded
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? 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
On 4/19/12 7:02 PM, Richard O'Keefe wrote:
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?
Good question. I'd suppose
Ivan,
This package provides an efficient implementation of so-called
signed multisets, which generalise multisets by allowing for
negative membership.
That is, elements in a signed multiset can have negative multiplicities.
Wait, something can be not in the multiset more than once? :o
Stefan Holdermans stefan at vectorfabrics.com writes:
This package provides an efficient implementation of so-called
signed multisets, which generalise multisets by allowing for
negative membership.
SignedMultiset a = Data.Map.Map a Integer
so what do I gain by using your library?
(what is
Johannes,
This package provides an efficient implementation of so-called
signed multisets, which generalise multisets by allowing for
negative membership.
SignedMultiset a = Data.Map.Map a Integer
Indeed.
so what do I gain by using your library?
(what is the API difference?)
The library
I am pleased to announce the first release of signed-multiset, which implements
an abstract datatype for multisets with negative membership.
The package can be obtained from
http://hackage.haskell.org/package/signed-multiset-0.1
As always, feedback is welcome.
Cheers,
Stefan
On 18 April 2012 14:26, Stefan Holdermans ste...@vectorfabrics.com wrote:
I am pleased to announce the first release of signed-multiset, which
implements an abstract datatype for multisets with negative membership.
The package can be obtained from
30 matches
Mail list logo
