Haskell: What does type fa mean?

Question

I came across this piece of code fold ((,) <$> sum <*> product) with type :: (Foldable t, Num a) => ta -> (a, a) and was completely lost.

I know what he does, but I don’t know how to do it. So I tried to break it into small pieces in ghci:

 λ: :t (<$>) (<$>) :: Functor f => (a -> b) -> fa -> fb λ: :t (,) (,) :: a -> b -> (a, b) λ: :t sum sum :: (Foldable t, Num a) => ta -> a 

Everything is in order, just basic material.

 λ: :t (,) <$> sum (,) <$> sum :: (Foldable t, Num a) => ta -> b -> (a, b) 

And I'm lost again ...

I see that there is some kind of magic that turns ta -> a into fa , but how this is done is a mystery to me. ( sum not even an instance of Functor !)

I always thought fa is some kind of box f containing a , but it looks like the value is much deeper.

Answer 1

The functor f in your example is the so-called “reader-functor”, which is defined as follows:

 newtype Reader r = Reader (r -> a) 

Of course, in Haskell this is implemented initially for functions, so there is no wrapping or deployment at run time.

The corresponding Functor and Applicative instances are as follows:

 instance Functor f where fmap :: (a -> b) -> (r -> a)_-> (r -> b) fmap fg = \x -> f (gx) -- 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 sense, a functor reader is a “box”, like all other functors, having a context r that creates a type a .

So, look at (,) <$> sum :

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

Now we can specialize type d to a ~ f , e to b -> (a, b) and c to tf . Now we get:

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

Application Functions:

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

This is exactly what ghc says.

Answer 2

Short answer: f ~ (->) (ta) . To understand why, just slightly change the type signature for sum , using -> as the prefix operator instead of the infix operator.

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

---

In the general case (->) r is a functor for any type of argument r .

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

It is easy to show that (.) Is the only possible implementation for fmap here, connecting ((->) r) to the fmap type for f :

 fmap :: (a -> b) -> fa -> fb :: (a -> b) -> ((->) r) a -> ((->) r) b :: (a -> b) -> (r -> a) -> (r -> b) 

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

---

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

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

Hence, a rather simple but tedious job, confirming that the resulting type is valid (Foldable t, Num a) => ta -> b -> (a, b) . We have

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