This is a functional dependency. You can probably find informationin the GHC docs. It's a way of telling the compiler how to derive type information on multiparameter classes. For example, if I have a class: class C a b where f :: a -> b the type of f is (C a b) => a -> b The problem here is that you may have multiple instances of C with the same a: instance C Int Bool ... instance C Int Char ... so when you use f, it doesn't know which instance to use. Writing 'a -> b' means "a uniquely determines b" and makes it so for any given a, you can only have one instance of C, so the two above instances would be rejected: you could only have one. This means that when you write 'f (5::Int)' it knows which instance to choose, since there can only be one. - Hal -- Hal Daume III "Computer science is no more about computers | hdaume@isi.edu than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume On Wed, 21 Aug 2002, Guest, Simon wrote:

Hello all,

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

I couldn't find reference to this in any of my standard Haskell tutorials, nor the Haskell 98 report. Any references?

cheers, Simon

-----Original Message----- From: Andrew J Bromage [mailto:ajb@spamcop.net] Sent: 21 August 2002 04:19 To: haskell-cafe@haskell.org Subject: Re: Question about sets

G'day all.

On Tue, Aug 20, 2002 at 10:57:36AM -0700, Hal Daume III wrote:

...

Lists with arbitrary elements are possible, but not very useful. After all, what could you do with them?

It's often useful to have containers of arbitrary _constrained_ types, because then you can do something with them. For example, given the class of partial mappings on orderable keys:

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

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

instance (Ord k) => Map [(k,v)] k v where lookupM m k = case [ v | (k',v) <- m, k == k' ] of [] -> Nothing (v:_) -> Just v

instance (Ord k) => Map (k -> Maybe v) k v where lookupM = id

You can make a list of elements, which can be any type so long as they are a member of that class:

data MAP k v = forall m. (Map m k v) => MAP m

type ListOfMap k v = [MAP k v]

Then you can do things with it:

lookupLom :: (Ord k) => ListOfMap k v -> k -> [ Maybe v ] lookupLom xs k = [ lookupM a k | MAP a <- xs ]

test :: [Maybe Int] test = lookupLom maps 1 where maps = [ MAP finiteMap, MAP assocListMap, MAP functionMap ] finiteMap = listToFM [(1,2)] assocListMap = [(1,3)] functionMap = \k -> if k == 1 then Just 4 else Nothing

It's a little unfortunate that you have to introduce the MAP type here. You can in fact construct a list of this type:

type ListOfMap k v = [ forall m. (Map m k v) => m ]

But then you can't use the elements in the list because the Haskell type checker can't find the (Map m k v) constraint.

Cheers, Andrew Bromage _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

Here what the User's Guide says:

...

Functional dependencies are implemented as described by Mark Jones in "Type Classes with Functional Dependencies", Mark P. Jones, In Proceedings of the 9th European Symposium on Programming, ESOP 2000, Berlin, Germany, March 2000, Springer-Verlag LNCS 1782.

There should be more documentation, but there isn't (yet). Yell if you need it.

Folks, let's yell together! This is a nice feature. It SHOULD be better known. If Simon's team has no time to write it, perhaps it would be nice to put the reference to Mark's paper on line? http://www.cse.ogi.edu/~mpj/pubs/fundeps.html

I've put the above link in the docs. Cheers, Simon

On Wed, 21 Aug 2002, Christian Sievers wrote: (snip)

It might not have become clear from the previous answers: this construction is not Haskell 98, but an extension. That's why it's not in the report. (snip)

One issue we have here is that any Haskell we write is stuff we'll probably want to keep using for a while so, although we've only just got most of the bugs out of the H98 report, I'll certainly watch with interest as people come to a consensus about multi-parameter typeclasses, concurrency libraries, etc. and such things start to look very much like they'll be fixed in the next round of standardisation. It's hard to know which are experiments that ultimately will be shunned in favour of something else, and which are just all-round good ideas. (-: -- Mark

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 as: 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. Cheers, Andrew Bromage