Question about use of | in a class declaration

Andrew J Bromage
Thu, 22 Aug 2002 11:29:47 +1000

G'day all.

On Wed, Aug 21, 2002 at 02:31:05PM +0100, Guest, Simon wrote:

> Please could someone explain the meaning of | in this class
> declaration (from Andrew's example):
> 	class (Ord k) => Map m k v | m -> k v where
> 	  lookupM :: m -> k -> Maybe v

Others have answered the question about what it means.  However, this
doesn't explain why I used a fundep when Haskell has perfectly good
constructor classes.  I could have written:

	class (Ord k) => Map m k v where
	  lookupM :: m k v -> k -> Maybe v

	instance (Ord k) => Map FiniteMap k v where
	  lookupM = lookupFM

However, this would not work for the other two cases (the assoc list
and the function).  For that, I'd have to introduce a new type, such

	newtype MapFunc k v = MapFunc (k -> Maybe v)

	instance (Ord k) => Map MapFunc k v where
	  lookupM (MapFunc f) = f

A good Haskell compiler would optimise the representation of the type,
so it wouldn't cost much (or possibly _anything_) at run time, but it's
still a pain to program with.  You need to pack and unpack the MapFunc
type at awkward places, when all you really want to do is rearrange
type variables for one declaration.  Fundeps let you avoid many of these
"artificial" constructors.

Unfortunately, I don't think that fundeps will help you to get rid
of all of them.  For example, the standard state transformer monad:

	newtype State s a = State { runState :: s -> (a, s) }

I don't think you can get rid of the constructor here.

Andrew Bromage