[Haskell] Re: DData AscList

[JP Bernardy]

--- John Meacham <john at 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