2

This doesn't type check:

module DoesntTypeCheck where {
import Prelude(Either(..));
defaultEither :: a -> Either b c -> Either a c;
defaultEither a (Left _) = Left a;
defaultEither _ b = b;
}

But this does:

module DoesTypeCheck where {
import Prelude(Either(..));
defaultEither :: a -> Either b c -> Either a c;
defaultEither a (Left _) = Left a;
defaultEither _ (Right b) = Right b;
}

The compiler is probably buggy, an Either a c type can be only Left (x::a) or Right (y::c), if it isn't Left then it is Right, and we know that Right :: b -> Either a b so Right (y::c) :: Either a c.

Improve this question
4
  • 12
    "The compiler is probably buggy". First words of absolutely everybody trying to compile their first Haskell program. The real reason is never a compiler bug. Commented May 7, 2019 at 6:01
  • You can also write defaultEither = first . const with first coming from Data.Bifunctor. I might, however, call it something like setLeft, since there's nothing particularly defaulty about Left. Commented May 7, 2019 at 7:26
  • @n.m. It's never a compiler bug for beginner programs anyway. It definitely sometimes is when you're trying to do more esoteric things. Commented May 7, 2019 at 12:13
  • 1
    Although compilers have bugs, my experience is that once you start blaming the compiler, it (close to) certainty is not. In short, a Right x of type Either Int Int, is not a Right x of Either String Int. Commented May 7, 2019 at 13:11

4 Answers 4

Reset to default
10

The problem is that when you say

defaultEither _ b = b

you're saying that the output value b is the same as the second input value. And that's only possible if the values have the same type. But you've told the compiler that the input has type Either b c, while the output has type Either a c. These are different types, so no wonder the compiler complains.

I understand what you are trying to do - but even though a value Right x (with x of type c) on its own can be of type Either d c for any d, your type signature constrains the input and output values to versions with different ds. And that means you can't use the same variable to refer to both values.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

I don't say that the output has the same type as the second input. I only say that the output is the same as the second input. And just because they are different types doesn't mean they don't intersect! The intersection of Either a c and Either b c is precisely the values of the form Right (y::c)
But there is no such thing as an "intersection" of types. The value Right (y::c) has type Either a c, which you could also call Either b c, since the name of a type variable is arbitrary. But when you've used both Either a c and Either b c in a type signature, the compiler has to assume they're different types. It seems that you want GHC's type inference to be able to look at the implementation of Either and see that in your definition the b must be a value that could also be of type Either b c. And I don't think it's reasonable to expect it to be able to do that.
@ThePiercingPrince "And just because they are different types doesn't mean they don't intersect!" It does mean exactly that in Haskell. Haskell's type system is nominal (as is nearly every other static type system used in programming languages) - i.e. if two types have different names they (and their values!) are fully distinct. Of course it's possible to extract the right value and inject it as another right value of a different type, but that's not going to happen automatically.
6

Let's try an even simpler example:

data Foo x = Bar

foobar :: Foo a -> Foo b
foobar f = f

Take a look at the definition of Foo. There's a type variable on the left-hand side (x), which never actually appears anywhere on the right-hand side. This is an example of a so-called "phantom type variable". There's a type in the type signature which doesn't actually correspond to the type of anything in the actual value. (And this is perfectly legal, by the way.)

Now if you have the expression Just True, then since True :: Bool, then Just True :: Maybe True. However, the expression Nothing is definitely a Maybe something. But with no actual value present, there's nothing to force it to be any specific maybe-type. The type variable is phantom in this case.

We have a similar thing here; Bar :: Foo x, for any x. So you would think that our definition of foobar is legal.

And you would be wrong.

You cannot pass a value of Foo a where a value of type Foo b is expected, even if they have exactly the same run-time structure. Because the type checker doesn't care about the run-time structure; it only cares about types. As far as the type checker is concerned, Foo Int is different to Foo Bool, even though at run-time there's no observable difference.

And that is why your code is rejected.

In fact, you have to write

foobar :: Foo a -> Foo b
foobar Bar = Bar

to let the type checker know that the Bar you're outputting is a new, different Bar than the one you received as input (and hence it can have a different type).

Believe it or not, this is actually a feature, not a bug. You can write code that makes it so that (for example) Foo Int behaves differently than Foo Char. Even though at run-time they're both just Bar.

The solution, as you have discovered, is to just take your value b out of Right and then immediately put it back in again. It seems pointless and silly, but it's to explicitly signal to the type checker that the types have potentially changed. It's perhaps annoying, but it's just one of those corners of the language. It's not a bug, it's purposely designed to work this way.

Improve this answer

Comments

3

an Either a c type can only be...

Indeed, but in your first example, the value b does not have type Either a c! As your type signature proves, it has type Either b c. And of course, you cannot return an Either b c where an Either a c is expected. Instead, you must destructure the value and reconstruct it with the right type.

Improve this answer

Comments

0

an Either a c type can be only Left (x::a) or Right (y::c), if it isn't Left then it is Right, and we know that Right :: b -> Either a b so Right (y::c) :: Either a c.

I think you are confusing type constructors with data constructors. Either is defined like this in ghc-base:

data  Either a b  =  Left a | Right b

Either is a type constructor with two abstract variables. i.e. it takes any two types (Int, String, etc). and constructs a concrete type like Either Int String.

Left and Right on the other hand are data constructors. They take actual values like 1, "hi" and construct values like Left 1 and Right "hi".

Prelude> :t Left
Left :: a -> Either a b
Prelude> :t Right
Right :: b -> Either a b

Haskell type inference does not work with values (Left and Right). It only works on types (Either). So the type checker only knows about Either b c and Either a c - so in the first case the variables don't match.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.