[Haskell] RFC: DData in hierarchical libraries

[Christian Maeder]

JP Bernardy wrote:
> http://users.skynet.be/jyp/DData/doc/index.html

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