What's the difference between a function and a functor in Haskell? Only definition?

Question

In Haskell, when writing a function, it means we map something(input) to another thing(output). I tried LYAH to understand the definition of Functor: seems just the same like a normal Functor.

1. Is there any restriction that a function could be called a Functor?
2. Is Functor allowed to have I/O or any other side effect?
3. If in Haskell, "everthing is a function", then what's the point of introducing the "Functor" concept? A restricted version of function, or an enhancement version of a function?

Very confused, need your advice. Thanks.

Answer 1

First of all, it's not true that "everything is a function" in Haskell. Many things are not functions, like 4. Or the string "vik santata".

In Haskell, a function is something which maps some input to an output. A function is a value which you can apply to some other value to get a result. If a value has a -> in its type, chances are that it may be a function (but there are infinitely many exceptions to this rule of thumb ;-)).

Here are some examples of functions (quoting from a GHCI session):

λ: :t fst
fst :: (a, b) -> a
λ: :t even
even :: Integral a => a -> Bool

Here are a few examples of things which are not functions:

• A (polymorphic) value which can assume any type a provided that the type is a member of the Num class (e.g. Int would be a valid type). The exact value would be inferred from how the number is used.

  Note that this type has => in it, which is something different altogether than ->. It denotes a "class constraint".

  λ: :t 5
  5 :: Num a => a
  

• A list of functions. Note that this has a -> in its type, but it's not the top level type constructor (the toplevel type is [], i.e. "list"):

  λ: :t [fst, snd]
  [fst, snd] :: [(a, a) -> a]
  

Functors are not things you can apply to values. Functors are types whose values can be used with (and returned by) the fmap function (provided that the fmap function complies to certain rules, often called 'laws'). You can find a basic list of types which are part of the Functor using GHCI:

λ: :i Functor
[...]
instance Functor (Either a) -- Defined in ‘Data.Either’
instance Functor [] -- Defined in ‘GHC.Base’
instance Functor Maybe -- Defined in ‘GHC.Base’
[...]

This means you can apply fmap to lists, or to Maybe values, or to Either values.

Answer 2

It helps to know a little category theory. A category is just a set of objects with arrows between them. They can model many things in mathematics, but for our purposes we are interested in the category of type; Hask is the category of Haskell types, with each type being an object in Hask and each function being an arrow between the argument type and the return type. For example, Int, Char, [Char], and Bool are all objects in Hask, and ord :: Char -> Int, odd :: Int -> Bool, and repeat :: Char -> [Char] would be some examples of arrows in Hask.

Each category has several properties:

1. Every object has an identity arrow.

2. Arrows compose, so that if a -> b and b -> c are arrows, then so is a -> c.

3. Identity arrows are both left and right identities for composition.

4. Composition is associative.

The reason that Hask is a category is that every type has an identity function, and functions compose. That is, id :: Int -> Int and id :: Char -> Char are identity arrows for the category, and odd . ord :: Char -> Bool are composed arrows.

(Ignore for now that we think of id is polymorphic function with type a -> a instead of a bunch of separate functions with concrete types. This demonstrates a concept in category theory called a natural transformation that you don't need to think about now.)

---

In category theory, a functor F is a mapping between two categories; it maps each object of one category to an object of the other, and it also maps each arrow of one category to an arrow of the other. If a is an object in one category, we say that F a is the object in the other category. We also say that if f is an arrow in the first category, the corresponding arrow in the other if F f.

Not just any mapping is a functor. It has to obey two properties which should look familiar.

1. F has to map the identity arrow for an object a to the identity arrow of the object F a.
2. F has to preserve composition. That means that the composition of two arrows in the first category has to be mapped to the composition of the corresponding arrows in the other category. That is, if h = g ∘ f is in the first category, then h is mapped to F h = F g ∘ F f in the other.

Finally, an endofunctor is a special name for a functor that maps one category to itself. In Hask, the typeclass Functor captures the idea of an endofunctor from Hask to Hask. The type constructor itself maps the types, and fmap is used to map the arrows.

---

Let's take Maybe as an example. The type constructor Maybe is an endofuntor, because it maps objects in Hask (types) to other objects in Hask (other types). (This point is obscured a little bit since we don't have new names for the target types, so think of Maybe as mapping Int to the type Maybe Int.)

To map an arrow a -> b to Maybe a -> Maybe b, we provide a defintion for fmap in the instance of Maybe Int. Maybe also maps functions, but using the name fmap instead. The functor laws it must obey are the same as two listed in the definition of a functor.

1. fmap id = id (Maps id :: Int -> Int to id :: Maybe Int -> Maybe Int.
2. fmap f . fmap g = fmap f . g (That is, fmap odd . fmap ord $ x has to return the same value as fmap (odd . ord) $ x for any possible value x of type Maybe Int.

---

As an unrelated tangent, others have pointed out that some things in Haskell are not functions, namely literal values like 4 and "hello". While true in the programming language (you can't, for instance, compose 4 with another function that takes an Int as a value), it is true that in category theory that you can replace values with functions from the unit type () to the type of the value. That is, the literal value 4 can be thought of as an arrow 4 :: () -> Int that, when applied to the (only) value of type (), it returns a value of type Int corresponding to the integer 4. This arrow would compose like any other; odd . 4 :: () -> Bool would map the value from the unit type to a Boolean value indicating whether the integer 4 is odd or not.

Mathematically, this is nice. We don't have to define any structure for types; they just are, and since we already have the idea of a type defined, we don't need a separate definition for what a value of a type is; we just just define them in terms of functions. (You might notice we still need an actual value from the unit type, though. There might be a way of avoiding that in our definition, but I don't know category theory well enough to explain that one way or the other.)

For the actual implementation of our programming language, think of literal values as being an optimization to avoid the conceptual and performance overhead of having to use 4 () in place of 4 every time we just want a constant value.

Answer 3

Actually, a functor is two functions, but only one of them is a Haskell function (and I'm not sure it's the function you suspect it to be).

1. A type level function. The objects of the Hask category are types with kind *, and a functor maps such types to other types. You can see this aspect of functors in ghci, using the :kind query:

   Prelude> :k Maybe
   Maybe :: * -> *
   Prelude> :k []
   [] :: * -> *
   Prelude> :k IO
   IO :: * -> *
   

   What these functions do is rather boring: they map, for instance,

   • Int to Maybe Int
   • () to IO ()
   • String to [[Char]].

   By this I don't mean that they map integer numbers to maybe-integers etc. – that's a more specific operation, not possible for every functor. I just mean, they map the type Int, as a single entity, to the type Maybe Int.

2. A value-level function, which maps morphisms (i.e. Haskell functions) to morphisms. The target morphism always maps between the types that result from applying the type-level function to the domain and codomain of the original function.
   This function is what you get with fmap:

   • fmap :: (Int -> Double) -> (Maybe Int -> Maybe Double)
   • fmap :: (() -> Bool) -> (IO () -> IO Bool)
   • fmap :: (Char -> String) -> String -> [String].

Answer 4

3. Not everything in Haskell is a function. Non-functions include "Hello World", (3 :: Int, 'a'), and Just 'x'. Things whose types include => are not necessarily functions either, although GHC (generally) translates them into functions in its intermediate representation.

What is a functor? Given categories C and D, a functor f from C to D consists of a mapping fo from the objects of C into the objects of D and a mapping fm from the morphisms of C into the morphisms of D such that

1. If x and y are objects in C and p is a morphism from x to y then fm(p) is a morphism from fo(x) to fo(y).
2. If x is an object in C and id is the identity morphism from x to x then fm(id) is the identity morphism from fo(x) to fo(x).
3. If x, y, and z are objects in C, p is a morphism from y to z, and q is a morphism from x to y, then fm(p . q) = fm(p).fm(q), where the dot represents morphism composition.

How does this relate to Haskell? We like to think of Haskell types and Haskell functions between them as forming a category. This is only approximately true, for various reasons, but it's a useful guide to intuition. The Functor class then represents injective endofunctors from this Hask category to itself. In particular, a Functor consists of a mapping (specifically a type constructor or partial application of type constructor) from types to types, along with a mapping (the fmap function) from functions to functions which obeys the above laws.

Answer 5

For something to be a functor - you need two things:

• a container type*
• a special function that converts a function from containees to a function converting containers

the first is depending on your own definition but the second one has been codified in the "interface" called Functor and the conversion function has been named fmap.

thus you always start with something like

data Maybe a = Just a | Nothing

instance Functor Maybe where
    -- fmap :: (a -> b) -> Maybe a -> Maybe b
    fmap f (Just a) = Just (f a)
    fmap _ Nothing = Nothing

Functions on the other hand - do not need a container to work - so they are not related to Functor in that kind of way. On the other hand every Functor, has to implement the function fmap to earn its name.

Moreover convention wants a Functor to adhere to certain laws - but this cannot be enforced by the compiler/type checker.

_{*: this container can also be a phantom type, e.g. data Proxy a = Proxy in this case the name container is debatable, but I would still use that name}