[Haskell] RFC: DData in hierarchical libraries

JP Bernardy jyp_7 at yahoo.com
Wed Mar 10 16:07:58 EST 2004


--- Simon Marlow <simonmar at microsoft.com> wrote:

> Regarding the Seq type, I like the one that we use
> in GHC.  See: [URL]
> 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.

I've done this, mostly. I'll submit another revision

> -------------
> 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?

I'd like to hear Daan's opinion about this...

> Can IntMap and IntSet be implemented by
> specialisation or overloading
> the Set type (ala the overloaded arrays in
> Data.Array)? 

It is intended to be so. As it is, a few functions are
missing, but nothing that can't be fixed easily.

> 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?

My view is that lists cannot be done away with; they
are pervasive in the current "haskell coding style".
I suspect there would be performance issues as well.

I used to consider "Seqs" for the sole purpose of

This implies to use lists everywhere, leaving the
conversion to sequences to the programmer, if ever
that's needed.

Thanks for your feedback,

Do you Yahoo!?
Yahoo! Search - Find what you’re looking for faster

More information about the Libraries mailing list