[Haskell-cafe] Newbie Q: Overloading and type classes

[Luke Palmer]

On Sat, Jun 7, 2008 at 5:07 PM, Dmitri O.Kondratiev <dokondr at gmail.com> wrote:
> {--
> And what does the word "newbie" imply to you when answering my question?
> In what case using 'fundeps' and 'associated types' will make sence for this
> example?
> --}

Well, functional dependencies ("fundeps") and associated types are
"advanced" extensions to the language (not Haskell98), and I
personally would not consider it a good idea to approach them until
you have a good handle on typeclasses.  Actually, associated types are
not that bad, save for the peculiar restrictions on what is possible
to define (because of decidability issues).  Fundeps are a bit
stranger, IMO..

However, since you asked, I'll here try to expound a situation in
which you might need associated types.

Let's say you have a CellHash type that very efficiently stores
key-value pairs, but only if the key is a string.  So you have:

data CellHash v = ...

In the simple case, there is no way to make this an instance of Store,
since Store requires a constructor with two parameters.  And we can't
really hack around it, because an instance of Store must support *any*
key type by definition.

Instead, we can use associated types, which associate *types* to
instances in a class.  These associated types will tell us about the
acceptable keys and values of a particular instance:

class Store s where
    type Key s :: *
    type Value s :: *
    put :: (Key s, Value s) -> s -> s
    get :: Key s -> s -> Value s

The ":: *" annotates the kind of the result; for 'normal' value types
it is *, for constructors with one parameter it is "* -> *", etc.

It is straightforward to implement Store for your Cell and CellList.

instance Store (Cell k v) where  -- note that this is not "instance
Store Cell" anymore
    type Key (Cell k v) = k
    type Value (Cell k v) = v
    -- as before

But now we can make an instance for CellHash too:

instance Store (CellHash v) where
    type Key (CellHash v) = String
    type Value (CellHash v) = v
    -- straightforward

There's a situation where you would want to use associated types.  But
they are quite new, and can be hard to work with because of all the
restrictions on their creation.  For example, IIRC something like this
would be illegal in the above instance:

    type Key (CellHash v) = HashKey String StringHashPolicy

Because the right hand side is larger in terms of number of symbols
than the left.  This is untested, and I'm unsure of my knowledge here,
so take the former with a grain of salt.

Fundeps could be used to achieve the same thing, but are not without
their caveats.

Luke