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

Question

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?

If you have a `s :: Sum Int Int` and you do `fmap show s`, what should happen, according to your implementation? — danidiaz, Jun 05 '21 at 16:26
It's just an exercise for a book, but it should behave like Either. — geckos, Jun 05 '21 at 16:28
assuming you have an `f : b -> c` then `fmap f a` is supposed to result in a `Sum a c` - but `a :: Sum a b` - see the problem? — Random Dev, Jun 05 '21 at 16:31

score 3 · Answer 1 · answered Jun 05 '21 at 18:41

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.

Will Ness · Accepted Answer · 2021-06-05T19:51:28.163

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.

I thought I answered some very similar question recently, but couldn't find it. — Will Ness, Jun 05 '21 at 17:14
[here it is](https://stackoverflow.com/questions/67522395/how-does-this-trick-type-check/67522546#67522546). — Will Ness, Jun 05 '21 at 19:20

score 1 · Answer 3 · answered Jun 06 '21 at 22:33

1

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.

answered Jun 06 '21 at 22:33

David Fox

654
4
10

That's was a simple and strait to the point answer, thanks! – geckos Jun 07 '21 at 21:18

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

3 Answers3