--- John Meacham <john@repetae.net> wrote:

So, pursuient to discussion on the various other haskell lists and some talk about DData recently, I was wondering whether adding an ordered list type might be useful. Often, when one knows a list is ordered, many algorithms (like building a tree-based set, or a map) become more efficient, however it is up to the programmer to ensure an ordered list is used where one is expected or obscure bugs might occur.

I was thinking... (off the top of my head)

module

Data.OrdList(OrdList,toList,fromList,unsafeFromAscList)

where

newtype Ord a => OrdList a = OrdList { toList :: [a] }

fromList = OrdList . sort unsafeFromAscList xs = OrdList xs

with some appropriate instances which make an OrdList behave pretty much exactly like a list, except maintaining the ordered invarient...

then we can safely convert between the various container types in O(n) time without the posibility of messing up...

comments?

Fine, but OrdList should be a subtype of List... and so it has to be done in an "adhoc" fashion. Encoding every other property in a class hierarchy might lead to a big mess. (The ordered property is applicable to any sequence; crossing all independant properties leads to an explosion of the number of types.) To go a bit further, I find it unfortunate to define an extra type for essentially the same structure with more information on it. I'm interested on what Oleg has to say about this, in relation of his recent findings. Also, I wonder how the problem is approached in a dependent-types language. (understand epigram) For this purpose I move to the mother list.

where is the current proposed DData library anyway?

Simon Marlow expressed the wish to include part of it (excluding sequences) in the standard distribution. In the meantime, find it on my homepage: users.skynet.be/jyp/DData/ddata.tar.gz Cheers, JP. __________________________________ Do you Yahoo!? New and Improved Yahoo! Mail - 100MB free storage! http://promotions.yahoo.com/new_mail