FiniteMap: modifyFM

Hal Daume III hdaume@ISI.EDU
Wed, 19 Jun 2002 11:16:04 -0700 (PDT)


On Wed, 19 Jun 2002, Simon Marlow wrote:

> There have been lots of proposals for collection classes over the years,
> and no single one stands out as an obvious choice.  However, I don't
> think we should stop looking - this is arguably one of the most
> important pieces still missing from the libraries, and the longer we go
> on without a good framework for collections, the harder it will be to
> add one.  So get designing!

I am definately in favor of getting a good collections library in the
hierarchical libs.  I am more in favor of that than having the *correct*
one in (if such a thing actually exists).  So if the choice is between
having a 98% good one and none at all, I vote strongly for the former

That said, I'm in favor of modelling such a collections library after the
one found in Java or C# (which are virtually identical).  There are some
things I don't like in there (for instance, I don't think elements in a
collection shoudl necessairly we instances of Eq), but all in all, I think
it's a good set up.

----moving away from the likely----

I believe John Hughes' proposal about the wfd class needs to be done to
do collections correctly (but see my first comment).

I also believe we need existential quantificiation on function types to do
collections correctly; otherwise we end up with ridiculously complex
functional dependencies.  For instance, supposing there's a Map class (as
in HashMaps, FiniteMaps, etc...) along the lines of:

class Map m a b where
  lookup :: m a b -> a -> Maybe b
  setValue :: m a b -> a -> b -> m a b

suppose we want a function to return the keys and elements.  one option
(bad, imo) is to return this as a list.  What we want is something like:

class Map m a b where
  keys :: exists s . Set s a => m a b -> s a
  vals :: exists c . Collection c a => m a b -> c b

Of course this isn't possible.  We could have:

class (Set s a, Collection c a) => Map m a b s c | m -> s, c where
  keys :: m a b -> s a
  vals :: m a b -> c b

but I think we can all agree this is ugly.

anyway, I'm sure this won't happen, but I think it's something to keep in

 - Hal