How ghc knows what fmap definition etc. Use?

Question

I know that fmap is of type (a -> b) -> fa -> fb , where f is a functor (and does different things depending on what the functor is). My main question is this: given some call to fmap rx , how does ghc figure out what the functor f , are the types x and r just given?

Let me make it more accurate. Suppose that f and f' are functors such that fa = f' a for some type a , but fb and f' b different. If r is of type a -> b and x is of type fa , it seems that there are two different possible outcomes for fmap rx : something like fb and something like f' b . How is this ambiguity resolved?

Second question: I wanted to check this by creating a weird functor - maybe something that takes a before [Int] for any type a and does something stupid for functions ... but I apparently didn't find the right bit of syntax that allows me to specify functors this way. (Is there something like data Newtype a = [Int] that works? It seems I need to create a class name before I can make it an instance of a functor.)

EDIT: I am getting this now, but for the record, the real problem (which is only implied in my question) was that I did not understand that you cannot have a Foo functor, so Foo a type like Int , which is already exist.

Answer 1

Classes like Haskell are based on first-order logical resolution. The type type restriction for a type variable is a predicate (you may have seen error messages indicating this if you ever tried to use the type class name where the type name is required) in this logical system.

Haskell requires a unique solution for each pair (Predicate, Type) in the entire program, so you cannot create, for example, two different instances of Functor by Int. The standard way to do this, for example, in the Monoid class for numeric types, which can provide summation or a product depending on how you define the monoid operator you want to use, is to provide newtype wrappers over the specific type you want the class to have different instances for.

So, for Monoid we have newtype Sum a = Sum { getSum :: a } and instance Num a => Monoid (Sum a) for the sum of the monoid and newtype Product a = Product { getProduct :: a } and instance Num a => Monoid (Product a) for the product monoid.

Note that since type only creates an alias for the type, this is not enough to provide multiple instances of the class for the type. The newtype declaration is similar to type in the sense that it does not create an additional runtime structure for the new type, but unlike type , a new type is created in it, not a type alias.

Answer 2

I think the general answer you are looking for is that Haskell types are organized using "views" that are similar to type types.

Here Functor class

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

This is not explicit, but it means that f is a type constructor with the form * -> * . Only types of this type can be made by Functor s.

This is indeed a pretty strong statement. This means that any Functor must be parametric in the type argument. Now consider your statement:

Suppose that f and f 'are functors such that fa = f' a for some type a, but fb and f 'b are different.

Given the kind system, this is not possible. Since a Functor is parametric in an argument of its type, fa = f' a implies f = f' , therefore fb = f' b .

I'm not quite sure what you are asking for with a "weird functor", but it seems like it cannot be expressed by a class like Functor . IIRC Functor can only express endoscectors on Hask; you may need another abstraction that allows functors between categories.

Answer 3

It depends on which argument you pass. For example, a list is a functor, and so Maybe

 main = do putStrLn $ show (double [1..5]) putStrLn $ show (double (Just 3)) putStrLn $ show (double Nothing) double :: (Functor f, Num a) => fa -> fa double = fmap (*2) *Main> main [2,4,6,8,10] Just 6 Nothing 

This double function will work for any functor containing Num .

Answer 4

"Suppose f and f' are functors for which fa = f' a for some type a , but fb and f' b are different."

This makes no sense. Either f and f' match or not. It seems you are proposing some kind of intermediate state where it changes depending on the type of argument; this cannot be.

"If r is of type a -> b and x is of type fa , it seems that for fmap rx there are two different possible outcomes: something like fb and something like f' b . How is this ambiguity resolved?

Where did f' come from? Nothing in the above signatures mentions this. Since x is of type fa , the result of fmap must be of some type starting with f - in this case fb , since r :: a -> b . This is completely unambiguous. The result of fmap always in the same functor you started with.