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?
where is the current proposed DData library anyway?
John
--
John Meacham - ⑆repetae.net⑆john⑈
