Haskell: What does type f a actually mean?

Question

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.

Answer 1

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.

Answer 2

The short answer is that f ~ (->) (t a). To see why, just rearrange the type signature for sum slightly, using -> as a prefix operator instead of an infix operator.

sum :: (Foldable t, Num a) => (->) (t a) a
                              ~~~~~~~~~~
                                  f

---

In general, (->) r is a functor for any argument type r.

instance Functor ((->) r) where
    fmap = (.)

It's easy to show that (.) is the only possible implementation for fmap here by plugging ((->) r) into the type of fmap for f:

fmap :: (a -> b) -> f a -> f b
     :: (a -> b) -> ((->) r) a -> ((->) r) b
     :: (a -> b) -> (r -> a) -> (r -> b)

This is the type signature for composition, and composition is the unique function that has this type signature.

---

Since Data.Functor defines <$> as an infix version of fmap, we have

(,) <$> sum == fmap (,) sum
            == (.) (,) sum

From here, it is a relatively simple, though tedious, job of confirming that the resulting type is, indeed, (Foldable t, Num a) => t a -> b -> (a, b). We have

(b' -> c') -> (a' -> b') -> (a' -> c')  -- composition
b' -> c' ~ a -> b -> (a,b)              -- first argument (,)
a' -> b' ~ t n -> n                     -- second argument sum
----------------------------------------------------------------
a' ~ t n
b' ~ a ~ n
c' ~ a -> b -> (a,b)
----------------------------------------------------------------
a' -> c' ~ t a -> b -> (a,b)