Data.* collections maintenance

[Georg Martius]

Am Freitag, 21. Oktober 2005 16:41 schrieb Christian Maeder:
> Hi Adrian,
>
> I've always wanted to try out your AVL implementation, but never found
> the time to adapt your interface to that of Data.Set and Data.Map (or a
> sub-interface). If you have done so, that would only mean to replace
> import entries (and would allow to switch back if it doesn't work as
> expected).
>
> (It would also be handy if your modules could be passed to the same
> properties and performance checker if we had those.)

I heard that there have been such tests? Who has them and why not putting them 
into the testsuite in the ghc source distro. 

> A different performance profile is of course fine (and desirable if
> there is a big gain in certain or even most cases).
>
> So far, the problem always was to agree on an accepted interface (that I
> didn't want to be a class but leave to the discipline of library writers.)
>
> How about something like Data.Set.Tree.AVL (and Data.Set.Seq.Ordered)
> or Data.SetByAVLTree (and Data.SetByOrderedSeq)?

Why not having a class for Set and Map,... and then we can change the 
implementation in the instances. Furthermore we could specify optimised 
versions like IntMap as an instance.

Georg

> Cheers Christian
>
> Adrian Hey wrote:
> > Well not that I'm in any way biased :-) but might I suggest that if these
> > libraries are going to get an API overhaul you could probably save
> > yourself quite a bit of work (and get a performance boost too) if you
> > switched from using size balanced trees (aka Adams trees ?) to using
> > Data.Tree.AVL.
> >
> > AFAICT all the problems people seem to have mentioned recently with
> > current Data.Set/Map APIs are already solved in Data.Tree.AVL or are
> > trivially self solvable e.g. you can chose whether you want left or
> > right biasing (AVL is uncommitted), intersection works on trees of
> > different element types, strictness in elements is much more fine
> > tuneable..
> >
> > I was about to offer half finished AVL based clones of Data.Set/Map
> > I have written (but not published), but having just checked it seems I
> > must have deleted them at some point :-( I can remember implementation
> > was quite easy though.
> >
> > The only reservation I have about this is the size function and indexing
> > operations would be O(n) for AVL, not O(1) or O(log n). But the only
> > reason size is O(1) for size balanced trees is that you pay extra for
> > this information everywhere else, and I'm not sure that index functions
> > should be supported at all in an abstracted Map API (they seem a bit
> > unsafe to me). Does anybody use Data.Map indexing? and why doesn't
> > Data.Set support this too? (just curious :-)
> >
> > Also, more generally it seems impossible to have a single optimal Set/Map
> > implementation for all possible element or key types. IntSet/Map will
> > perform better for Ints, StringMap will perform better for Strings (the
> > latter could be generalised to ListMap I guess, or maybe even a
> > SequenceMap). Where would these fit in the general scheme of things?
> >
> > Regards
> > --
> > Adrian Hey
> >
> > _______________________________________________
> > Libraries mailing list
> > Libraries at haskell.org
> > http://www.haskell.org/mailman/listinfo/libraries
>
> _______________________________________________
> Libraries mailing list
> Libraries at haskell.org
> http://www.haskell.org/mailman/listinfo/libraries

-- 
---- Georg Martius,  Tel: (+49 34297) 89434 ----
------- http://www.flexman.homeip.net ----------
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
Url : http://www.haskell.org//pipermail/libraries/attachments/20051021/6a570375/attachment.bin