Understanding evaluation with fmaps

Learn
#1

Hi,

I am learning Haskell using the Haskell Programming from 1st Principles book.
And I can’t read/decode the following expression:

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

whose value is Just 6.

I mean, I tried to massage it in some ways (parenthesize, partially apply…) to see if I understand how it is evaluated but I just can’t!
Can’t even get the number of arguments for sure: 2 ? 3 ? Something else…

Obviously, I can get the same result with:

fmap sum (Just [1, 2, 3])
fmap sum $ Just [1, 2, 3]

But I can’t make sense of the first expression (grrrr…), Please somebody help me!

Thanks

B

2 Likes
#2

The thing to note here is that you aren’t doing:

(fmap . fmap) sum $ Just [1,2,3]

but really

(fmap . fmap) sum Just $ [1,2,3]

the Functor you’re fmapping on is the Just function, not the Just [1,2,3] value. As for what that means, well, fmap on functions is the same as function composition, so we get a reduction like this:

(fmap . fmap) sum Just [1,2,3] = fmap (fmap sum) Just [1,2,3]  -- (definition of .)
fmap (fmap sum) Just  [1,2,3]  = (fmap sum) . Just   [1,2,3]   -- (fmap on functions is .)
fmap sum . Just $ [1,2,3]      = fmap sum (Just [1,2,3])       -- (definition of .)
-- you know the rest, probably, but included anyway
fmap sum (Just [1,2,3])        = Just (sum [1,2,3])            -- (fmap on Maybe)
Just (sum [1,2,3])             = Just 6                        -- (definition of sum)
3 Likes
#3

Thanks for your reply. That is what I was hoping for.
(To carve into my brain: “fmap of function is function composition”)

Still I don’t get the first step of the reasoning. Why there? Is it because it’s the only way the expression type-checks ? Is it because of associativity and precedence ?

#4

The key thing to understand here is fmap . fmap, which is an instance of a more general pattern of n-times fmap composition.

  1. fmap f x applies f to all values in a functor, one level deep, so x could have types such as the following:
    x :: [a]
x :: Maybe a
x :: r -> a
...
  2. (fmap . fmap) f x goes two levels deep, so x could have types such as the following:
    x :: [[a]]
x :: Maybe [a]
x :: [Maybe a]
x :: r -> [a]
...
  3. (fmap . fmap . fmap) f x goes three levels deep, so x could have types such as the following:
    x :: [[[a]]]
x :: Maybe (Maybe (Maybe a))
x :: [Maybe [a]]
x :: r -> Maybe [a]
x :: [Maybe (r -> a)]
x :: r1 -> r2 -> r3 -> a
...

and so on and so forth. It’s all about reaching that a in nested functorial contexts.

Now let’s take a look at your example, and in particular this fragment:

(fmap . fmap) sum Just

The type of Just is a -> Maybe a, so with fmap . fmap you’re reaching two levels deep:

  • the outer functorial context is a ->
  • the inner functorial context is Maybe

And then you reach some a within it, to which sum is applied. Of course sum expects a foldable t b, so type inference instantiates a ~ t b, and you get:

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

Now you have a function that expects t b and turns it into Maybe b. You apply it to a list [1, 2, 3], which instantiates t ~ [] and b ~ Integer.

2 Likes
#5

Thanks! It is quite clear now.
Although, I remember reading about “Functors stacking” and using composition of fmap to "peel of the outer Functor layers, I am still not… used to the ((->) r) functor.

Also, I still can’t figure out how you can read:

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

And understand that what’s really going on is:

(fmap . fmap) sum Just $ [1, 2, 3]

I like the simplicity of Haskell syntax, but “everything” (I mean data constructor, function calls, argument list) looks the same. This is quite confusing…

#6

Function application f x is left-associative, so f a b c is to be read as ((f a) b) c.

The structure of your expression is this:

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

and then it’s a matter of style which parentheses to omit or whether to add a gratuitous $.