Haskell: What does type f a actually mean?

Ford O.

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.

ThreeFx

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.

Collected from the Internet

Please contact [email protected] to delete if infringement.

edited at
0

Comments

0 comments
Login to comment

Related