That's not really how I visualize functors. Let's go back to the function picture:
--- ---
|a| -- f --> |b|
--- ---
This is fairly simple--using f, you can go from a to b.
Now lets imagine a functor F (with f still being our function):
--- ---
|a| -- f --> |b|
--- ---
| |
|F|
\ /
V
---- ----
|a'| -- f' --> |b'|
---- ----
So a functor is just a function at a higher level. A function maps values of one type to values of another type. A functor maps types to other types. In Haskell, types in the Functor class always map types of kind * back onto * , so they're much like functions of type a -> a.
The crucial part to notice is that it not only maps between types but it also preserves functions. That is, you get new types corresponding to your old types and new functions corresponding to your old functions.
So the list type, for example, maps any type a to [a] and any function (a -> b) to ([a] -> [b]). In a sense, it is like a well-behaved function between types.
Coincidentally, thinking of functors like this is how I realized that functors in Haskell are not completely unrelated to functors in OCaml--they're just different reifications of the same mathematical idea.
That's right. That's how functors work in category theory.
I've seen a nice article explaining how Haskell types form a category. The objects of the category are types, an arrow a -> b is a function taking argument of type a and returning type b. A Haskell functor is then an endofunctor in this category (i.e. a functor from the category of types to itself). Unfortunately I cannot find the article anymore.
Thanks for the links! However I am thinking about a different article. If I remember correctly I found it somewhere in the Haskell Wiki. Wikibooks have also a similar article on the subject: http://en.wikibooks.org/wiki/Haskell/Category_theory
I like to think of fmap as a converting a normal function into a function that operates "through" a functor. This is clearer looking at the Haskell type signature, which can be written as:
In general, thinking about the different valid rewrites of the type signatures of the various higher order functions in Haskell tends to reveal quite a bit!
What is the relationship between fold + cons (::) and monadic bind? What is the natural transformation from fold to functorial map? Is there a sensical dual?
> What is the relationship between fold + cons (::) and monadic bind? What is the natural transformation from fold to functorial map? Is there a sensical dual?
Whew, working backwards.
Fold is like your swiss army knife for working with entire lists at once; you just need to tell it what to do when it sees a node (Cons) or a terminator (Nil). If, for example, you instruct fold to apply a function to each element of the list but leave the linked structure intact, you've implemented map! And for lists, the fuctorial map, or fmap, is exactly map.
The monadic bind in the List monad is a way of expressing Nondeterminism. Let's say I have two functions...
b = makeSomeBsFromAnA(a); c = makeSomeCsFromAB(b);
In the context of the List Monad, you would evaluate the first statement to produce a list of Bs. Then, for each B, you would generate a list of Cs, and then concatenate all of those lists into a big list. That's why bind is sometimes referred to as flatmap in the List Monad - take each element generate in the last list computation to generate a bunch of new lists, and then flatten them (smoosh them together; concatenate them). flatmap could of course be implemented using fold and cons.
The point here is that, since we're working within the context of the list monad, I can deal with a single B and a single C, even though the function calls are really giving back lists of those respective types.
By the way, in Haskell the code would really look like this
makeSomeCsFromAnA a = do
b <- makeSomeBsFromAnA a
makeSomeCsFromAB b
Now lets imagine a functor F (with f still being our function):
So a functor is just a function at a higher level. A function maps values of one type to values of another type. A functor maps types to other types. In Haskell, types in the Functor class always map types of kind * back onto * , so they're much like functions of type a -> a.The crucial part to notice is that it not only maps between types but it also preserves functions. That is, you get new types corresponding to your old types and new functions corresponding to your old functions.
So the list type, for example, maps any type a to [a] and any function (a -> b) to ([a] -> [b]). In a sense, it is like a well-behaved function between types.
Coincidentally, thinking of functors like this is how I realized that functors in Haskell are not completely unrelated to functors in OCaml--they're just different reifications of the same mathematical idea.