Haskell: What does type f a actually mean?

functor, haskell

Solution

The functor `f` in your example is the so-called "reader functor", which is defined like this:

newtype Reader r = Reader (r -> a)

Of course, in Haskell, this is implemented natively for functions, so there is no wrapping or unwrapping at runtime.

The corresponding `Functor` and `Applicative` instances look like this:

instance Functor f where
  fmap :: (a -> b) -> (r -> a)_-> (r -> b)
  fmap f g = \x -> f (g x) -- or: fmap = (.)

instance Applicative f where
  pure :: a -> (r -> a) -- or: a -> r -> a
  pure x = \y -> x -- or: pure = const
  (<*>) :: (r -> a -> b) -> (r -> a) -> (r -> b)
  frab <*> fra = \r -> frab r (fra r)

In a way, the reader functor is a "box" too, like all the other functors, having a context `r` which produces a type `a`.

So let's look at `(,) <$> sum`:

:t (,) :: a -> b -> (a, b)
:t fmap :: (d -> e) -> (c -> d) -> (c -> e)
:t sum :: Foldable t, Num f => t f -> f

We can now specialize the `d` type to `a ~ f`, `e` to `b -> (a, b)` and `c` to `t f`. Now we get:

:t (<$>) -- spcialized for your case
:: Foldable t, Num f => (a -> (b -> (a, b))) -> (t f -> f) -> (t f -> (b -> (a, b)))
:: Foldable t, Num f => (f -> b -> (f, b)) -> (t f -> f) -> (t f -> b -> (f, b))

Applying the functions:

:t (,) <$> sum
:: Foldable t, Num f => (t f -> b -> (f, b))

Which is exactly what ghc says.

Problem

I have stumbled on this piece of code `fold ((,) <$> sum <*> product)` with type signature `:: (Foldable t, Num a) => t a -> (a, a)` and I got completely lost. I know what it does, but I don't know how. So I tried to break it into little pieces in ghci: ``` λ: :t (<$>) (<$>) :: Functor f => (a -> b) -> f a -> f b λ: :t (,) (,) :: a -> b -> (a, b) λ: :t sum sum :: (Foldable t, Num a) => t a -> a ``` Everything is okay, just basic stuff. ``` λ: :t (,) <$> sum (,) <$> sum :: (Foldable t, Num a) => t a -> b -> (a, b) ``` And I am lost again... I see that there is some magic happening that turns `t a -> a` into `f a` but how it is done is mystery to me. (`sum` is not even instance of `Functor`!) I have always thought that `f a` is some kind of box `f` that contains `a` but it looks like the meaning is much deeper.

Original source