Hello, I've updated DData again. http://users.skynet.be/jyp/DData/doc/ http://users.skynet.be/jyp/DData/ddata.tar.gz * Eq I've stated the policy regarding Eq: it should mean equality. This is because it most likely refects general use, and was already more or less implied in Set and Map code. Advanced users can still act differently at their own risk. In the same vein, I've renamed MultiSet to Bag; being synonyms, I favoured the most usual name. * Naming of functions. (ie. isSubsetOf, etc.) I still stick to Data.List naming scheme. These choices are guided by the general goal: having decent concrete data structures fitting nicely in the hierarchy, suitable for daily use. (As opposed to the ultimate all-purpose collection framework) Point left open: * Left/Right bias; structure first/last To me, this barely makes a difference whatever is chosen. For reasons of compatibility with the old FiniteMap/Set, "right bias+structure first" might be better. Since changing the convention is a tedious work, and Daan has expressed the wish to take care of the implementation, I leave the decision to him. I insist though that functions sharing a name with one in Data.List should not have their argument order changed. Namely, having Data.List.lookup :: Eq k => k -> [(k, a)] -> Maybe a DData.map.lookup :: Ord k => Map k a -> k -> Maybe a is inconsistent, thus not desirable. Cheers, JP. __________________________________ Do you Yahoo!? Yahoo! Finance Tax Center - File online. File on time. http://taxes.yahoo.com/filing.html
JP Bernardy wrote:
In the same vein, I've renamed MultiSet to Bag; being synonyms, I favoured the most usual name.
good, having looked at it, I'm missing a map (and mapMonotonic) function for bags and maybe "subset" should be renamed to "subbag"?
To me, this barely makes a difference whatever is chosen. For reasons of compatibility with the old FiniteMap/Set, "right bias+structure first" might be better.
I vote for the current state "left bias+structure last", as the bias should not matter much and a repeated lookup can be done using the section notation: (`Map.lookup` m) For folding "structure last" is to be preferred as even the type of FiniteMap.foldFM suggest! Thus e.g..insert should be like in DData.Map and not like addToFM in Data.FiniteMap. Christian
Am Donnerstag, 25. März 2004 18:09 schrieb Christian Maeder:
JP Bernardy wrote: [...]
To me, this barely makes a difference whatever is chosen. For reasons of compatibility with the old FiniteMap/Set, "right bias+structure first" might be better.
I vote for the current state "left bias+structure last", as the bias should not matter much
Does the bias matter at all if Eq means equality?
and a repeated lookup can be done using the section notation: (`Map.lookup` m)
For folding "structure last" is to be preferred as even the type of FiniteMap.foldFM suggest! Thus e.g..insert should be like in DData.Map and not like addToFM in Data.FiniteMap.
I'd vote for structure last, too.
Christian
Wolfgang
Wolfgang Jeltsch wrote:
I vote for the current state "left bias+structure last", as the bias should not matter much
Does the bias matter at all if Eq means equality?
No, not for sets and bags. The bias matters of course for the union/intersection of maps, since some elements of one side will be ignored (if not the "With"-variant is used). Since Map.insert should actually override a map entry it is left bias (as the structure comes last). How should Set.insert behave? I tend to replace an "equal" element and maybe Map.insert should even update the key and not only the value only to achieve the same behaviour of sets for bags (that are based on maps). On the other hand Set.insert could also do nothing when an element is already a set member. Conclusion: biasing for sets and bags should not be documented/relied on. Christian
I vote for the current state "left bias+structure last", as the bias should not matter much
Does the bias matter at all if Eq means equality?
It should be documented, so "advanced users" can rely on the behaviour.
--KW 8-)
--
Keith Wansbrough
Am Freitag, 26. März 2004 13:11 schrieb Keith Wansbrough:
I vote for the current state "left bias+structure last", as the bias should not matter much
Does the bias matter at all if Eq means equality?
It should be documented, so "advanced users" can rely on the behaviour.
In my opinion, even "advanced users" should adhere to The Haskell Report which says that (==) means equality.
--KW 8-)
Wolfgang
Does the bias matter at all if Eq means equality?
It should be documented, so "advanced users" can rely on the behaviour.
In my opinion, even "advanced users" should adhere to The Haskell Report which says that (==) means equality. Content-Transfer-Encoding: quoted-printable
Contrived example:
data Foo =3D Foo Int Int
instance Eq Foo where
(Foo x _) =3D=3D (Foo y _) =3D x =3D=3D y
mkFoo x =3D Foo x (expensive_calculation x)
fooX (Foo x _) =3D x
fooY (Foo _ y) =3D y
a =3D mkFoo 10
b =3D mkFoo 10
=
m =3D if fooY a > 10 then add a empty else empty
m' =3D add b m
Now it would be nice to know that a is in the collection, not b, because =
a's Y component has been forced, but b's hasn't. Replacing a with b woul=
d waste work.
Thus knowing the bias may be important for time/space analysis.
--KW 8-)
-- =
Keith Wansbrough
Does the bias matter at all if Eq means equality?
It should be documented, so "advanced users" can rely on the behaviour.
In my opinion, even "advanced users" should adhere to The Haskell Report which says that (==) means equality.
Sorry, not sure what happened with my previous reply. Here it is again:
data Foo = Foo Int Int
instance Eq Foo where
(Foo x _) == (Foo y _) = x == y
mkFoo x = Foo x (expensive_calculation x)
fooX (Foo x _) = x
fooY (Foo _ y) = y
a = mkFoo 10
b = mkFoo 10
=
m = if fooY a > 10 then add a empty else empty
m' = add b m
Now it would be nice to know that a is in the collection, not b,
because a's Y component has been forced, but b's hasn't. Replacing a
with b would waste work.
Thus knowing the bias may be important for time/space analysis.
--KW 8-)
--
Keith Wansbrough
Am Freitag, 26. März 2004 13:30 schrieb Keith Wansbrough:
Does the bias matter at all if Eq means equality?
It should be documented, so "advanced users" can rely on the behaviour.
In my opinion, even "advanced users" should adhere to The Haskell Report which says that (==) means equality.
Sorry, not sure what happened with my previous reply. Here it is again:
data Foo = Foo Int Int
instance Eq Foo where (Foo x _) == (Foo y _) = x == y
mkFoo x = Foo x (expensive_calculation x) fooX (Foo x _) = x fooY (Foo _ y) = y
a = mkFoo 10 b = mkFoo 10 =
m = if fooY a > 10 then add a empty else empty m' = add b m
Now it would be nice to know that a is in the collection, not b, because a's Y component has been forced, but b's hasn't. Replacing a with b would waste work.
Thus knowing the bias may be important for time/space analysis.
--KW 8-)
Ok, you're right. But a bias specification should not be needed to know what the result of the add function is semantically. A bias spec is, of course, needed for Map.add. Wolfgang
On Fri, Mar 26, 2004 at 01:16:27PM +0100, Wolfgang Jeltsch wrote:
Am Freitag, 26. März 2004 13:11 schrieb Keith Wansbrough:
I vote for the current state "left bias+structure last", as the bias should not matter much
Does the bias matter at all if Eq means equality?
It should be documented, so "advanced users" can rely on the behaviour.
In my opinion, even "advanced users" should adhere to The Haskell Report which says that (==) means equality.
A specified bias is very important for reasoning about time/space efficiency. I think it is quite important. plus, even though (==) means equality, every now and again it comes in handy to cheat a little :) -- John Meacham - ⑆repetae.net⑆john⑈
On Fri, 2004-03-26 at 11:15, John Meacham wrote:
A specified bias is very important for reasoning about time/space efficiency. I think it is quite important.
plus, even though (==) means equality, every now and again it comes in handy to cheat a little :)
Given a Map type with a specified value bias, you can construct a Set type with this bias with something like: type Set t = Map t t set_insert t set = map_insert t t set set_iterate f set = map_iterate (\key value -> f value) set Of course, it would be simpler to just document the bias on an existing Set implementation. :) Carl Witty
participants (6)
-
Carl Witty -
Christian Maeder -
John Meacham -
JP Bernardy -
Keith Wansbrough -
Wolfgang Jeltsch