Hi all,
On Mon, 8 Mar 2004 16:58:13 -0000, Simon Marlow
Regarding the Seq type, I like the one that we use in GHC. See:
The "Seq" and "Queue" modules are less "mature" than the Map/Set/Bag modules -- it may be good if someone consistently extends them with the GHC modules as examples.
How do DData.Map and DData.IntMap compare in performance to the existing Data.FiniteMap? Similarly for Sets?
In terms of worst-case bounds, DData.Map equals Data.FiniteMap. DData.IntMap has an incomparable worst-case bound than Data.FiniteMap I *suspect* that the absolute efficiency of DData.Map will be close to Data.FiniteMap as they use essentially the same algorithms and representation. On some operations DData.Map will be better as it uses "hedge" variations. However, I have never tested this with proper benchmarks. (now that I think about it, I might have tested it with improper benchmarks... I'll try to find on my computer when I get home). I have measured different DData.IntMap against DData.Map instantiated with Int's and it strongly outperformed it on all operations. (I'll give numbers if I can find them again). This was my motivation for including a specialized implementation based on (big-endian) patricia trees.
Can IntMap and IntSet be implemented by specialisation or overloading the Set type (ala the overloaded arrays in Data.Array)? (The interfaces look very similar, but I didn't compare them in detail).
IntMap/IntSet have completely different algorithms than the corresponding Map/Set modules. The interfaces are very similar off course :-) I think that making them an instance of a common "Set" type should not be goal of DData but rather a goal of a framework like Edison, for which DData can provide concrete implementations.
Why is there no direct translation between Seqs and Sets/Maps, but there is for lists? I guess there's a consistency issue here - do we want to (a) use lists exclusively, (b) use Seq exclusively, or (c) have all operations available for both types?
I personally prefer to use lists exclusively, and to make the "seqFromList" function really efficient, in the sense that we guarantee that "listFromSeq . seqFromList" takes constant time. All the best, Daan.