CODEWITHSUNDEEP
haskellfunctional-programmingtypeclasscurrying
FtheBuilder
FtheBuilder

Reputation: 1437

Why can't I make Either instance of Functor using id in Haskell?

When making my custom Either, and Functor, just to understand clearer types and typeclasses, I found the following situation:

Functor

module Functor (Functor, fmap) where

import Prelude hiding(Functor, fmap)

class Functor f where
  fmap :: (a -> b) -> f a -> f b

Either

module Either(Either(..)) where
import Prelude hiding(Either(..), Functor, fmap)

data Either a b = Left a | Right b deriving(Show)

instance Functor (Either a) where
  fmap f (Right x) = Right (f x)
  fmap _ (Left x) = Left x

The code showed above compiles fine but, if I change it to use id, it doesn't compile:

instance Functor (Either a) where
  fmap f (Right x) = Right (f x)
  fmap _ = id

Why?? Did I miss something? The following code also doesn't work:

instance Functor (Either a) where
  fmap f (Right x) = Right (f x)
  fmap f all@(Left x) = all

... This seems to me very strange because the code showed below compiles:

data Shape = Circle Point Float | Rectangle Point Point deriving (Show)

data Point = Point Float Float deriving (Show)

test :: Shape -> String
test (Circle _ x) = show x
test all@(Rectangle _ x) = show all ++ " - "++ show x

Thank you in advance

Upvotes: 6

Views: 686

Answers (3)

Erik Kaplun
Erik Kaplun

Reputation: 38247

In terms of explaining the type error, I have nothing to add to the previous two answers, however I'd like to mention that Left x :: Either t a is represented in memory the same way as Left x :: Either t b. What this means is that even though the type system does not let you use an Either t a in place of a value of type Either t b, for reasons already explained in perfect clarity by the other answers, you can "force" it through the type checker using unsafeCoerce:

import Unsafe.Coerce (unsafeCoerce)

instance Functor (Either t) where
  fmap f (Right a) = Right (f a)
  fmap f l         = unsafeCoerce l

And even though unsafeCoerce is generally regarded as something to avoid, if you know what you are doing, and you have a valid reason to do so, such as performance, unsafeCoerce can be useful in letting the compiler know you are sure the runtime value will match the expected structure.

In this case, without unsafeCoerce, and not considering any potential GHC optimizations, fmap f (Left x) = Left x would always construct a new but physically identical Left value, whereas the unsafeCoerce flavor would just return the original Left value with no additional memory allocations.

Upvotes: 0

Ben
Ben

Reputation: 71535

What you're trying to do boils down to this:

f :: Either a Bool -> Either a ()
f (Right _) = Right ()
f left = left

with error:

foo.hs:3:7:
    Couldn't match type ‘Bool’ with ‘()’
    Expected type: Either a ()
      Actual type: Either a Bool
    In the expression: left
    In an equation for ‘f’: f left = left
Failed, modules loaded: none.

left is bound to the function argument. So the type checker knows it's of type Either a Bool. Then it's used as the return value. We know from the type f :: Either a Bool -> Either a () that the return value must be of type Either a (). If left is a valid return value, it's type must match the return type of f. So Either a () must be equal to Either a Bool; it is not, so the type checker rejects the program.

In turn, it's basically the same problem as this:

λ let l = Left () :: Either () ()
l :: Either () ()

λ l
Left ()
it :: Either () ()

λ l :: Either () Bool

<interactive>:10:1:
    Couldn't match type ‘()’ with ‘Bool’
    Expected type: Either () Bool
      Actual type: Either () ()
    In the expression: l :: Either () Bool
    In an equation for ‘it’: it = l :: Either () Bool

We gave l a binding and a type, then tried to use it as a different type. That's invalid (and feeding it through id wouldn't change its type either). Even though Left () is also valid source code text for a value of type Either () Bool, that doesn't mean that a particular value known to be of type Either () () that could be defined with the source text Left () can be used as if it were of type Either () Bool.

If you had a polymorphic value, you could do this:

λ let l = Left ()
l :: Either () b

λ l :: Either () ()
Left ()
it :: Either () ()

λ l :: Either () Bool
Left ()
it :: Either () Bool

Note that the original l value here was polymorphic in b; it can be used as an Either () b for any b.

But your fmap case is subtly different. The function fmap is polymorphic in the b, but the value of its argument is "within the scope of the polymorphism"; at the point you have your argument the type b has been chosen to be some specific type by the caller of fmap, so it's "some unknown type that could by anything" rather than "any type I feel like choosing". There is no way to somehow turn a value of type Either a b into a value of type Either a c, so you have to extract the a value and then create an Either a c containing it.

Upvotes: 7

Cactus
Cactus

Reputation: 27636

Let's look at the type of fmap specialized for the Either functor:

fmap :: (a -> b) -> Either e a -> Either e b

As we can see from this, in fmap f all@(Left _), the type of all is Either e a. This doesn't match the intended result type Either e b prescribed by the signature of fmap, so fmap f all@(Left _) = all is not well-typed.

Similarly for the case using id.

Upvotes: 7

Related Questions