Why do I need to call the constructor again in the definition of fmap even when I don't apply the f argument?

user_652528 0
Viewed 116

I have no idea why fmap _ a = a below is illegal. Here is the code:

data Sum a b = First a | Second b

instance Functor (Sum a) where
  fmap f (Second b) = Second (f b)
  fmap _ (First a)  = First a
  fmap _ a          = a  -- Why can't I do this instead?

Other question is, does this have performance penalty implications or is something that happens only at compile time?

sum-type algebraic-data-types functor haskell
3 Answers

Regarding performance: quite late in the compilation process, when GHC has erased most type information, it does its best to notice when a value is being reconstructed like that. This step catches a lot of situations, but not all; sometimes the code will have been transformed in such a manner that the reconstruction is no longer obvious.

user_14776670

You need to call the constructor anew to create a new value, so it will have a different type than the one you've started with.

fmap ::   (b -> c) ->    Sum a b  -> Sum a c
fmap (f :: b -> c) ::    Sum a b  -> Sum a c
fmap (f :: b -> c) (x :: Sum a b) -> Sum a c

                 a ::     a               a ::     a
           First a :: Sum a b       First a :: Sum a c

                 b ::       b             c ::       c
          Second b :: Sum a b      Second c :: Sum a c

Given a :: a, First a has type Sum a t with t determined by the context in which First a appears. The two First a on both sides of the equal sign define two different values, each of its own type. Using the variable a on the right, it still refers to the same value of type Sum a b as it is on the left. But we need a different type, according to fmap.

user_8498910

The reason you can't do this is because the result type of fmap depends on the result type of f, but the expression a does not. That is to say, you do not have the constraint f b ~ a.

user_47796360
Related