[Haskell] RFC: DData in hierarchical libraries

[Simon Marlow]

> I propose to add a modified version of DData to the
> hierachical libraries.
> 
> DData is a concrete library of collection types, by
> Daan Leijen.
> My modifications intend to make DData fit better in
> the hierarchical libraries.
> 
> The haddock-generated documentation can be found here:
> 
> http://users.skynet.be/jyp/DData/doc/index.html
> 
> while the source code is at
> 
> http://users.skynet.be/jyp/DData/ddata.tar.gz

Regarding the Seq type, I like the one that we use in GHC.  See:

http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/utils/Ord
List.lhs

Both libraries can support the same interface, but the implementation in
GHC's OrdList library is based on a concrete datatype:

data OrdList a
  = Many [a]
  | Two (OrdList a) (OrdList a)
  | One  a
  | None

which is more flexible, and probably more efficient.  Indeed for
performance reasons you might want two more constructors:

  | Cons a (OrdList a)
  | Snoc (OrdList a) a

I'd like to see many more operations defined over Seqs.  At least:

  snoc :: Seq a -> a -> Seq a
  concat :: Seq (Seq a) -> Seq a

and probably many other functions from Data.List.

-------------

Looking briefly at the rest of the library, I have a few
questions/comments:

Why are there IntBags but no Bags?

How do DData.Map and DData.IntMap compare in performance to the existing
Data.FiniteMap?  Similarly for Sets?

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).

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?

Internal functions like DData.Set.valid should not be visible.

Cheers,
	Simon