RFC: DData in hierarchical libraries
Dear haskellers, I propose to add a modified version of DData to the hierachical libraries. DData is a concrete library of collection types, by Daan Leijen. My modifications intend to make DData fit better in the hierarchical libraries. The haddock-generated documentation can be found here: http://users.skynet.be/jyp/DData/doc/index.html while the source code is at http://users.skynet.be/jyp/DData/ddata.tar.gz Any comment is welcome. (Including "I support this proposal" :)) Cheers, JP. PS. For those who don't follow the libraries list, the reasoning leading to this proposal goes as such: * Data.FiniteMap & Data.Set don't use the module system * We need better collection types * A fully fledged collection framework is difficult to agree on for integration in standard. * We should have a concrete types library, leaving the framework for later. * DData looks like a good candidate __________________________________ Do you Yahoo!? Yahoo! Search - Find what you�re looking for faster http://search.yahoo.com
JP Bernardy wrote:
I only looked at Set and Map
Any comment is welcome. (Including "I support this proposal" :))
Yes, I support this proposal. Maybe the documentation to the "0rdered lists" section can be improved. Set.toAscList is not really necessary as it is the same as Set.toList. In order to be a proper function, the result of Set.tolist must return a sorted list without duplicates, since equal sets should yield equal lists, if converted by Set.toList. (For debugging purposes this may be violated, though.) Returning a descending list is not necessary, because this can simply be achieved by reversing, if needed. The functions Set.fromAscList and Set.fromAscDistinctList should be marked as "unsafe", since it's not clear what sets result if the input is not ascending (and/or has duplicates). Furthermore, already for Set.fromList I expect it to be linear, if the input list happens to be ascending. "Set.map" is (still) missing. There are two variants of map functions with type: (Ord a, Ord b) => (a -> b) -> Set a -> Set b The first variant requires the function argument f to be strongly ascending, a < b => f a < f b, and corresponds to a map on the associated ascending lists. The second variant does not restrict the function argument but may result in a set of smaller size. Maybe this variant should be called "Set.image". The first variant, maybe call it "Set.mapAsc", is again "unsafe", since the argument function may not be ascending. (The descending case can be ignored.) The same argument about "ordered lists" apply to the Map module. In addition, it would be nice if there were a variant of "Map.keys" that returns a set of keys, since the invariant that the keys are ascending and distinct may easily get lost, if not captured by the Set type. A straight forward implementation is: Map.keySet = Set.fromDistinctAscList . Map.keys The use of "Set.fromDistinctAscList" is safe in this case, but - alas - Map needs to import Set. (But maybe there is even a faster implementation of Map.keySet that exploits the internal representation.) Christian
On Mon, Mar 08, 2004 at 12:32:21PM +0100, Christian Maeder wrote:
Yes, I support this proposal.
So do I.
Maybe the documentation to the "0rdered lists" section can be improved.
Set.toAscList is not really necessary as it is the same as Set.toList. In order to be a proper function, the result of Set.tolist must return a sorted list without duplicates, since equal sets should yield equal lists, if converted by Set.toList.
It is still a proper function this way, you only don't get some nice axioms.
Returning a descending list is not necessary, because this can simply be achieved by reversing, if needed.
If the descending list is built lazily, you can get M highest elements of N element Set in O(M log N) time, which is nice. Using reverse, you would pay O(N log N). Best regards, Tom -- .signature: Too many levels of symbolic links
Hi,
Maybe the documentation to the "0rdered lists" section can be improved.
Could you be more specific about this?
The functions Set.fromAscList and Set.fromAscDistinctList should be marked as "unsafe", since it's not clear what sets result if the input is not ascending (and/or has duplicates).
Would you prefix the function name with unsafe? I wonder what is the best way to do such a marking.
Furthermore, already for Set.fromList I expect it to be linear, if the input list happens to be ascending.
I'm afraid it's not, unfortunately. I intend not to fiddle with the implementation, to avoid the involved instability.
"Set.map" is (still) missing. There are two variants of map functions with type:
(Ord a, Ord b) => (a -> b) -> Set a -> Set b
The first variant requires the function argument f to be strongly ascending, a < b => f a < f b, and corresponds to a map on the associated ascending lists.
The second variant does not restrict the function argument but may result in a set of smaller size. Maybe this variant should be called "Set.image".
The first variant, maybe call it "Set.mapAsc", is
I'd choose "mapMonotonic", from Edison.
again "unsafe", since the argument function may not be ascending. (The descending case can be ignored.)
The same argument about "ordered lists" apply to the Map module. In addition, it would be nice if there were a variant of "Map.keys" that returns a set of keys, since the invariant that the keys are ascending and distinct may easily get lost, if not captured by the Set type. A straight forward implementation is:
Map.keySet = Set.fromDistinctAscList . Map.keys
The use of "Set.fromDistinctAscList" is safe in this case, but - alas - Map needs to import Set. (But maybe there is even a faster implementation of Map.keySet that exploits the internal representation.)
Fine. I'll come up with a revision soon. Thanks for your feedback, JP. __________________________________ Do you Yahoo!? Yahoo! Search - Find what you�re looking for faster http://search.yahoo.com
G'day all. Quoting JP Bernardy <jyp_7@yahoo.com>:
Would you prefix the function name with unsafe? I wonder what is the best way to do such a marking.
I would recommend not using that particular prefix. At the moment, I believe that "unsafe" is only used for functions which could potentially cause a core dump if misused. What we have here is a function whose domain is some subset of the entire set of values which can be passed to it, but fails to check this. As a suggestion, how about calling functions like this "uncheckedFoo", but also providing a "foo" which is checked? Cheers, Andrew Bromage
Hi Christian, (Some have already replied, but I'll say some more about some issues) On Mon, 08 Mar 2004 12:32:21 +0100, Christian Maeder <maeder@tzi.de> wrote:
Set.toAscList is not really necessary as it is the same as Set.toList.
Not necessarily: the lists from Set.toList will be equal for equal Set's, but may be unordered. Use "toAscList" or "toDescList" if you want an ordered variant. Now, my *implementation* might use "toAscList" for "toList", but that is a separate issue.
The functions Set.fromAscList and Set.fromAscDistinctList should be marked as "unsafe"
I think so too, although I like "unchecked" better?
Furthermore, already for Set.fromList I expect it to be linear, if the input list happens to be ascending.
That is not the case yet -- making it linear might be possible but one has to be very careful about "lost" laziness in that case.. For finite, strict lists, one can of course just check if the list is ordered in linear time and use "fromAscList" if that is the case.
The same argument about "ordered lists" apply to the Map module. In addition, it would be nice if there were a variant of "Map.keys" that returns a set of keys, since the invariant that the keys are ascending and distinct may easily get lost, if not captured by the Set type.
That seems a good thing. Let's add it.
A straight forward implementation is:
Map.keySet = Set.fromDistinctAscList . Map.keys
The use of "Set.fromDistinctAscList" is safe in this case, but - alas - Map needs to import Set. (But maybe there is even a faster implementation of Map.keySet that exploits the internal representation.)
Yes, we could do that -- but the circular dependency is terrible, and a wrapper module would need to look at the internal representation of Map/Set :-( -- Daan.
At 01:41 08/03/04 -0800, JP Bernardy wrote:
I propose to add a modified version of DData to the hierachical libraries.
I support the proposal in principle, though I don't feel qualified to comment on the specific modifications. #g ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact
participants (6)
-
ajb＠spamcop.net -
Christian Maeder -
Daan Leijen -
Graham Klyne -
JP Bernardy -
Tomasz Zielonka