Search code examples
functionhaskellfunctordifference

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

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.

Solution

  • 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.