[Haskell] RFC: DData in hierarchical libraries
maeder at tzi.de
Mon Mar 8 12:32:21 EST 2004
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
"Set.map" is (still) missing. There are two variants of map functions
(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
The first variant, maybe call it "Set.mapAsc", is again "unsafe", since
the argument function may not be ascending. (The descending case can be
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.)
More information about the Haskell