[Haskell] Proposal for a Standard of Abstract Collections (with Reference Implementation)

[ajb at spamcop.net]

G'day all.

Quoting Robert Will <robertw at stud.tu-ilmenau.de>:

>  - a formal specification for a collection hierarchy (based on
>    Abstract Algebraic Data Structures (TM)), but also

I'm not happy with the "kind" of a collection.  I personally think that
the type of the object in the collection is better connected with the
type of the collection with a functional dependency.

Let me explain.  The proposed class interface starts like this:

    class (Eq (coll a), Eq a) => Collection coll a where
        empty :: coll a
        single :: a -> coll a
        {- etc -}

Here's how it would look with fundeps:

    class (Eq coll, Eq a) => Collection coll a | coll -> a where
        empty :: coll
        single :: a -> coll
        {- etc -}

Consider, for example, Patricia tries, which can only store integer keys.
Without fundeps, you need to use some kind of phantom type:

    data PatriciaTrie a  {- a must be Int -}
        = {- whatever -}

    instance Collection PatriciaTrie Int where
        {- etc -}

The comment gives a constraint that the compiler can't check.  With
fundeps, the constraint is checked:

    data PatriciaTrie = {- whatever -}

    instance Collection PatriciaTrie Int where
        {- etc -}

Another example is radix structures, which can only take keys which are
themselves sequences (for the purposes of this example, lists).  Here's
how you could do it with fundeps:

    data RadixCollection a = {- whatever -}

    instance Collection (RadixCollection a) [a] where
        {- etc -}

Consider how you'd do this without fundeps.

Another question that you might want to consider is how collections like
Data.HashTable, which is embedded in a monad, might fit into the scheme.

Cheers,
Andrew Bromage