[Haskell] RFC: DData in hierarchical libraries

[Daan Leijen]

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 at 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.