[Haskell] RFC: DData in hierarchical libraries

JP Bernardy jyp_7 at yahoo.com
Wed Mar 10 15:27:02 EST 2004


> 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
> "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,

Do you Yahoo!?
Yahoo! Search - Find what you’re looking for faster

More information about the Haskell mailing list