views:

73

answers:

2

It normally seems the following is illegal:

class Foo a where
    foo :: a -> b -> a

Which makes sense; how do we know what b is?

However, if we look at Functor's definition:

class Functor f where
    fmap :: (a -> b) -> f a -> f b

we see a and b showing up even though we only specify f as a type variable. I'm guessing this is allowed because the compiler sees e.g. f a and can figure out that f itself must take an a, so it's safe to use that a elsewhere in our Functor definition. Am I correct?

+3  A: 

It doesn't need to "know". It just needs to typecheck (i.e. not fail to typecheck). b can be anything; and the function foo must be able to take any type as second parameter.

Consider the const function from Prelude:

const            :: a -> b -> a
const x _        =  x

How does it "know" what b (or a, for that matter) is?

newacct
+5  A: 

Let's look at each line separately.

class Functor f where

This declares a single-parameter type class called Functor; the type which satisfies it will be called f.

  fmap :: (a -> b) -> f a -> f b

Like any function definition, all the free type variables are implicitly foralled—they can be replaced with anything. However, thanks to the first line, f is in scope. Thus, fmap has the type signature fmap :: forall a b. Functor f => (a -> b) -> f a -> f b. In other words, every functor needs to have a definition of fmap which can work for any a and b, and f must have kind (the type of a type) * -> *; that is, it must be a type which takes another type, such as [] or Maybe or IO.

What you said, then, is incorrect; the a isn't special, and if we had another function in Functor, it wouldn't see the same a or b. However, the compiler does use the f a bit to figure out what the kind of f must be. Additionally, your Foo class is perfectly legal; I could specify an instance as follows

instance Foo (a -> b) where
  foo f _ = f

This satisfies foo :: a -> b -> a for any b; note that the b in Foo (a -> b) is different. Admittedly, it's not a very interesting instance, but it's perfectly legal.

Antal S-Z