Search code examples
haskellfunctor

Haskell: What does type f a actually mean?

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.

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.