Haskell Overlapping/Incoherent Instances

Question

I know this is code is a bit silly, but can someone explain why this isList [42] returns True whereas isList2 [42] prints False, and how to prevent this? I'd like to get better understanding of some of the more obscure GHC type extensions, and I thought this would be an interesting example to figure out.

{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE OverlappingInstances #-}
{-# LANGUAGE IncoherentInstances #-}

class IsList a where
  isList :: a -> Bool

instance IsList a where
  isList x = False

instance IsList [a] where
  isList x = True

isList2 = isList

main = 
  print (isList 42) >> 
  print (isList2 42) >> 
  print (isList [42]) >> 
  print (isList2 [42])

Because your program is incoherent. Really, what did you *expect*? — C. A. McCann, Apr 17 '13 at 03:03
I expected the output to be `True True`, not `True False`. Why do you expect the output to be `True False`? Why wouldn't the incoherent program return `True True`? Are you saying that there's no reason for the output, and the result is undefined, and it may actually return `True True` sometimes? — Clinton, Apr 17 '13 at 03:04
possible duplicate of [How does IncoherentInstances work?](http://stackoverflow.com/questions/8371499/how-does-incoherentinstances-work) — n. m. could be an AI, Apr 17 '13 at 03:08
Try adding an explicit type signature `isList2 :: IsList a => a->Bool`. — n. m. could be an AI, Apr 17 '13 at 03:27

C. A. McCann · Answer 1 · 2013-04-17T03:31:39.197

It's really quite simple. Let's ask GHCi what the type of isList2 is:

∀x. x ⊢ :t isList2
isList2 :: a -> Bool

This doesn't match the [a] instance (even though it could, via unification), but it does match the a instance immediately. Therefore, GHC selects the a instance, so isList2 returns False.

This behavior is precisely what IncoherentInstances means. Actually, this is a rather nice demonstration of it.

Hilariously, if you simply disable IncoherentInstances, we get exactly the opposite effect, and GHCi now says this:

∀x. x ⊢ :t isList2
isList2 :: [Integer] -> Bool

This happens because isList2 is a top-level binding not defined using function syntax, and thus subject to the Dreaded Monomorphism Restriction. So it gets specialized to the instance it's actually used with.

Adding NoMonomorphismRestriction as well as disabling IncoherentInstances, we get this instead:

∀x. x ⊢ :t isList2
isList2 :: IsList a => a -> Bool
∀x. x ⊢ isList2 'a'
False
∀x. x ⊢ isList2 "a"
True
∀x. x ⊢ isList2 undefined

<interactive>:19:1:
    Overlapping instances for IsList a0 arising from a use of `isList2'

Which is the expected overlapping behavior, with the instance chosen based on use and complaints if the choice is ambiguous.

Regarding the edit to the question, I don't believe the desired result is possible without type annotations.

The first option is to give isList2 a type signature, which prevents IncoherentInstances from selecting an instance too early.

isList2 :: (IsList a) => a -> Bool
isList2 = isList

You'll probably need to do the same anywhere else isList is mentioned (even indirectly) without being applied to an argument.

The second option is to disambiguate the numeric literals and disable IncoherentInstances.

main = 
  print (isList (42 :: Integer)) >> 
  print (isList2 (42 :: Integer)) >> 
  print (isList [42]) >> 
  print (isList2 [42])

In this case, there's enough information to pick a most-specific instance, so OverlappingInstances does its thing.

I've edited the question. Could you address how I could get the above to compile and return `False False True True`? — Clinton, Apr 17 '13 at 03:20
@Clinton: There's no *nice* way to do that, I don't think. See the edit to my answer. — C. A. McCann, Apr 17 '13 at 03:32
@Clinton I will go a bit further and say there CANNOT be a nice way to do that. GHC must obey the open world assumption when it comes to typeclasses, and must never make a decision based on the lack of a certain typeclass. For `isList 42` to return `False` you actually NEED to violate that assumption. As you have to assume there does not exist `instance Num [a] where ...` because the existence of such a typeclass would change the answer from `False` to "it depends on which instance you pick", which is not a valid value of type `Bool`. — semicolon, Nov 08 '16 at 19:53

score 2 · Answer 2 · answered Apr 17 '13 at 05:55

The following code does the trick without requiring IncoherentInstances:

{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE OverlappingInstances #-}

class IsList a where
  isList :: a -> Bool

instance IsList a where
  isList x = False

instance IsList [a] where
  isList x = True

isList2 :: (IsList a) => a -> Bool
isList2 = isList

main = do
  print (isList (42 :: Int))
  print (isList [42 :: Int])
  print (isList2 (42 :: Int))
  print (isList2 [42 :: Int])

I'd recommend not using IncoherentInstances, it seems to cause a lot of trouble, as you can silently call different overloads depending on context quite easily.

Haskell Overlapping/Incoherent Instances

2 Answers2

Linked