CODEWITHSUNDEEP
haskell
javinor
javinor

Reputation: 674

Why do the types in `(fmap . fmap) sum Just [1, 2, 3]` work?

I'm having the time of my life reading the wonderful Haskell Programming from first principles and I came by the following example that I'm just not able to take apart (Page 1286 e-reader):

Prelude> (fmap . fmap) sum Just [1, 2, 3]
Just 6

It is obvious to me how the following works:

Prelude> fmap sum $ Just [1,2,3]
Just 6

And I already manually deconstructed (fmap . fmap) to understand how the types work. But when thinking about this as "lifting twice" it doesn't make sense, since I'm lifting over both the Just and List data constructors.

I typed out the following in ghci:

Prelude> :t (fmap . fmap)
(fmap . fmap)
  :: (Functor f, Functor f1) => (a -> b) -> f1 (f a) -> f1 (f b)

Prelude> :t (fmap . fmap) sum
(fmap . fmap) sum
  :: (Num b, Foldable t, Functor f, Functor f1) =>
     f1 (f (t b)) -> f1 (f b)

Prelude> :t (fmap . fmap) sum Just
(fmap . fmap) sum Just :: (Num b, Foldable t) => t b -> Maybe b

I don't understand how to derive the last output. When feeding (fmap . fmap) sum the Just data constructor, How does the compiler know to replace both f1 and f for Maybe? After I'll get a good answer here, how could I have figured it out myself?

Upvotes: 8

Views: 278

Answers (2)

Dietrich Epp
Dietrich Epp

Reputation: 213827

If you don't understand how a particular answer works, line up the argument you are supplying with the type from the previous step.

Prelude> :t (fmap . fmap) sum
(fmap . fmap) sum
  :: (Functor f, Functor f1, Num b) => f (f1 [b]) -> f (f1 b)

So in order for this work, Just has to have type f (f1 [b]), and then (fmap . fmap) sum Just has to have type f (f1 b).

Just :: (Functor f, Functor f1, Num b) => f (f1 [b])

It's not obvious what f or f1 should be here, so let's try the RHS instead. We can cheat and ask GHCi to check what the actual value of (fmap . fmap) sum Just should be:

Prelude> :t (fmap . fmap) sum Just
(fmap . fmap) sum Just :: Num b => [b] -> Maybe b

But this should match:

(Functor f, Functor f1, Num b) => f (f1 b)

We're trying to figure out what f and f1 are here. So we have to rewrite it a little bit so it has the same structure (remember that -> is syntactic sugar and gets in the way sometimes):

(fmap . fmap) sum Just :: Num b => [b] -> Maybe b
-- Same as...
(fmap . fmap) sum Just :: Num b => (->) [b] (Maybe b)
-- Or...
(fmap . fmap) sum Just :: Num b => ((->) [b]) (Maybe b)
--                     Functor f = ((->) [b])
--                                Functor f1 = Maybe

So we can figure out that in order for the types to match, the Functor f has to be (->) [b]… remember that functions are functors too! And the Functor f1 is Maybe, which is a bit more obvious.

We can test this out:

Prelude> :t (fmap . fmap) sum :: Num b => ([b] -> Maybe [b]) -> ([b] -> Maybe b)
(fmap . fmap) sum :: Num b => ([b] -> Maybe [b]) -> ([b] -> Maybe b)
  :: Num b => ([b] -> Maybe [b]) -> [b] -> Maybe b

And GHCi thinks it type checks just fine.

The only part here that's easy to forget is just that (->) [b] is a valid functor!

Upvotes: 7

Li-yao Xia
Li-yao Xia

Reputation: 33569

That isn't lifting over both Maybe and List (that would be (fmap . fmap) sum (Just [1,2,3]), which has a type problem), but over the function type (->) and Maybe.

Just :: a -> Maybe a
     -- ((->) a) (Maybe a)
     -- f (g a)   for f ~ ((->) a)  and  g ~ Maybe

(fmap . fmap) :: (a   -> b) -> f (g a  ) -> f (g b)
     -- Num x => ([x] -> x) -> f (g [x]) -> f (g x)
     -- Num x => ([x] -> x) -> ([x] -> Maybe [x]) -> [x] -> Maybe x
     --          ^             ^                     ^
     --          sum           Just                  [1,2,3]

Upvotes: 9

Related Questions