Haskell fmap composition misunderstanding

user_304423 0
Viewed 166

If I compose two fmaps

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

I get a function which applies a function to a value inside 2 nested leves of structure, f1 and f.

And I can use it—this works as I expected:

Prelude> (fmap.fmap) (+1) [[1,2]]
[[2,3]]

With inferred type as I expected (2 leves of structure around result)

Prelude> :t  (fmap.fmap) (+1) [[1,2]]
(fmap.fmap) (+1) [[1,2]] :: Num b => [[b]]

The following does not work. I also expect this (because we can't apply sum to a single number):

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

<interactive>:39:2: error:
    • Could not deduce (Num (t0 b))
      from the context: (Num (t b), Num b, Foldable t)
        bound by the inferred type for ‘it’:
                   (Num (t b), Num b, Foldable t) => [[b]]
        at <interactive>:39:2-24
      The type variable ‘t0’ is ambiguous
    • In the ambiguity check for the inferred type for ‘it’
      To defer the ambiguity check to use sites, enable AllowAmbiguousTypes
      When checking the inferred type
        it :: forall (t :: * -> *) b.
              (Num (t b), Num b, Foldable t) =>
              [[b]]
Prelude> :t  (fmap.fmap) sum [[1,2]]
(fmap.fmap) sum [[1,2]] :: (Num (t b), Num b, Foldable t) => [[b]]

BUT! If I change one level of structure to a Maybe type:

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

then it begins to work, but in my opinion breaking the type signature (fmap.fmap) :: (Functor f, Functor f1) => (a -> b) -> f1 (f a) -> f1 (f b) (because it applies the sum function inside the first level of structure, not the second as I expected).

I think problem in my undersanding how function application order evaluates here, because I find that with parentheses this works as expected inside two levels of structure with foldable list values (vs numbers in first exapmles):

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

But what happens here:

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

  1. Why is the first level of stucture skipped?

  2. What is the order of function applications here?

  3. How does Haskell infer the final type?

     Prelude> :t (fmap.fmap) sum Just [1,2]
 (fmap.fmap) sum Just [1,2] :: Num t => Maybe t

Why Maybe t and not Maybe List t as I understand (fmap.fmap) must determine f1 (f b) two levels of structure not one?

haskell
3 Answers

Let's compute, pretending that numeric literals are Ints for the sake of simplicity.

(fmap.fmap) sum Just [1,2]
= fmap (fmap sum) Just [1,2]
        |         |    \ -- an additional argument applied to the result of fmap
        |         \ -- the value with a type of the form f a with f Functor
        \ -- the function to fmap

Here, Just is a function [Int] -> Maybe [Int], so the first fmap operates on the functor f = (->) [Int], we have fmap = (.) because that's how it's defined in Functor ((->) [Int]).

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

Now, fmap f (Just x) = Just (f x) since that's how Functor Maybe is defined.

= Just (sum [1,2])
= Just 3
  1. why first level of structure skipped?

It isn't. The first level is (->) [Int].

  1. what is the order of function applications here?

The usual one. fmap.fmap is applied to sum. The result is applied to Just. The final result is applied to [1,2].

  1. how does Haskell infer the final type?

It sees that Just is a "value wrapped inside the (->) [Int] functor", and uses that to instantiate the first fmap. The second fmap is instead used on the Maybe level since Just returns that.

user_32349590

What you have just discovered is that functions are themselves functors. That statement may sound a bit confusing, so let’s explore this a bit further. Let’s have a look at the function composition operator (.):

Prelude> :t (.)
(.) :: (b -> c) -> (a -> b) -> a -> c

But now let’s rewrite the type signature slightly:

(.) :: (b -> c) -> ((->) a b) -> ((->) a c)

Here, I’ve behaved as if the function composition arrow were a normal infix operator, and could be placed in front of what look like its ‘type parameters’ (which in fact it can be). And now we notice something interesting — (.) looks almost exactly like fmap! See:

(.)  ::              (b -> c) -> ((->) a b) -> ((->) a c)
fmap :: Functor f => (b -> c) ->  f      b  ->  f      c

And in fact it’s possible to write a Functor instance for the partially applied function arrow (->) r (where ((->) r) a is the same as (r -> a)):

instance Functor ((->) r) where
    fmap = (.)
-- type signature here would be:
--  fmap :: (a -> b) -> ((->) r) a -> ((->) r) b
-- that is:
--  fmap :: (a -> b) -> (r -> a) -> (r -> b)

So, if f and g are functions, then fmap f g = f . g.

Now, how does that relate to your question? Let’s have a look at the expression you’re confused about:

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

Let’s go through this bit by bit. First, notice that this can be rewritten as: (fmap (fmap sum) Just) [1,2]. Now, fmap sum is a function — that means it’s a functor! So, using fmap = (.) for functions as I said above, this becomes: ((fmap sum) . Just) [1,2], that is fmap sum (Just [1,2]). And of course that simply evaluates to Just 3.

user_73452980

Thanx for answers, it cleans for me that Just not Just [1,2] goes as second argument to (fmap.fmap).

I want to write type inference as I understand in more details (correct me if I wrong)

We have expression: (fmap.fmap) sum Just [1,2]

the type of (fmap.fmap) is (a -> b) -> f1 (f a) -> f1 (f b)

this determine that it takes two next arguments - sum and Just and return function.

sum has type List int -> int (for simplicity int) this implies that a = List int and b = int

Second argument Just has type a -> Maybe a or another words (->) a (Maybe a) so f1 = (->) a and f = Maybe

this implies that f1 (f b) = (->) (List int) (Maybe int)

Or another words the result type of expression (fmap.fmap) sum Just is List int -> Maybe int So the result is function.

And finnaly we apply value [1,2] to this function and get value Just 3 as expected with infered types.

user_3044230
Related