CODEWITHSUNDEEP
haskell
Ahmad B
Ahmad B

Reputation: 117

Overlapping instances - how to circumvent them

I am a beginner at Haskell, so please be indulgent. For reasons that are not important here, I am trying to define a operator <^> that takes a function and an argument and returns the value of the function by the argument, irrespective of which of the function and the argument came first. In short, I would like to be able to write the following:

foo :: Int -> Int
foo x = x * x

arg :: Int
arg = 2

foo <^> arg -- valid, returns 4
arg <^> foo -- valid, returns 4

I have tried to accomplish that through type families, as follows:

{-# LANGUAGE FlexibleInstances, MultiParamTypeClasses, TypeFamilies, TypeOperators #-}

class Combine t1 t2 where
    type Output t1 t2 :: *
    (<^>) :: t1 -> t2 -> Output t1 t2

instance Combine (a->b) a where
    type Output (a->b) a = b
    f <^> x = f x

instance Combine a (a->b) where
    type Output a a->b = b
    x <^> f = f x

On this code, GHC throws a Conflicting family instance declarations. My guess is that the overlap GHC complains about occurs when type a->b and type a are the same. I don't know Haskell well enough, but I suspect that with recursive type definitions, one may be able to construct such a situation. I have a couple of questions:

Thanks!

Upvotes: 2

Views: 268

Answers (2)

AntC
AntC

Reputation: 2806

@chi is close; an approach using either FunDeps or Closed Type Families is possible. But the Combine instances are potentially ambiguous/unifiable just as much as the CTF Output equations.

When chi says the FunDep code is accepted, that's only half-true: GHC plain leads you down the garden path. It will accept the instances but then you find you can't use them/you get weird error messages. See the Users Guide at "potential for overlap".

If you're looking to resolve a potentially ambiguous Combine constraint, you might get an error suggesting you try IncoherentInstances (or INCOHERENT pragma). Don't do that. You have a genuinely incoherent problem; all that will do is defer the problem to somewhere else. It's always possible to avoid Incoherent -- providing you can rejig your instances (as follows) and they're not locked away in libraries.

Notice that because of the potential ambiguity, another Haskell compiler (Hugs) doesn't let you write Combine like that. It has a more correct implementation of Haskell's (not-well-stated) rules.

The answer is to use a sort of overlap where one instance is strictly more specific. You must first decide which you way you want to prefer in case of ambiguity. I'll choose function prefixed to argument:

{-# LANGUAGE UndecidableInstances, TypeFamilies #-}

instance {-# OVERLAPPING #-} (r ~ b)
         => Combine (a->b) a r  where ...

instance {-# OVERLAPPABLE #-} (Combine2 t1 t2 r)
         => Combine t1 t2 r  where
  (<^>) = revApp

class Combine2 t1 t2 r  | t1 t2 -> r  where
  revApp :: t1 -> t2 -> r

instance (b ~ r) => Combine2 a (a->b) r  where
  revApp x f = f x

Notice that the OVERLAPPABLE instance for Combine has bare tyvars, it's a catch-all so it's always matchable. All the compiler has to do is decide whether some wanted constraint is of the form of the OVERLAPPING instance.

The Combine2 constraint on the OVERLAPPABLE instance is no smaller than the head, so you need UndecidableInstances. Also beware that deferring to Combine2 will mean that if the compiler still can't resolve, you're likely to get puzzling error messages.

Talking of bare tyvars/"always matchable", I've used an additional trick to make the compiler work really hard to improve the types: There's bare r in the head of the instance, with an Equality type improvement constraint (b ~ r) =>. To use the ~, you need to switch on TypeFamilies even though you're not writing any type families.

A CTF approach would be similar. You need a catch-all equation on Output that calls an auxiliary type function. Again you need UndecidableInstances.

Upvotes: 1

chi
chi

Reputation: 116174

This is a bad idea, in my view, but I'll play along.

A possible solution is to switch to functional dependencies. Usually I tend to avoid fundeps in favor of type families, but here they make the instances compile in a simple way.

class Combine t1 t2 r | t1 t2 -> r where
    (<^>) :: t1 -> t2 -> r

instance Combine (a->b) a b where
    f <^> x = f x

instance Combine a (a->b) b where
    x <^> f = f x

Note that this class will likely cause problems during type inference if we use polymorphic functions. This is because, with polymorphic functions, the code can easily become ambiguous.

For instance id <^> id could pick any of the two instances. Above, melpomene already reported const <^> id being ambiguous as well.

The following is weakly related, but I want to share it anyway:

What about type families instead? I tried to experiment a bit, and I just discovered a limitation which I did not know. Consider the closed type family

type family Output a b where
   Output (a->b) a = b
   Output a (a->b) = b

The code above compiles, but then the type Output a (a->b) is stuck. The second equation does not get applied, as if the first one could potentially match.

Usually, I can understand this in some other scenarios, but here unifying

Output (a' -> b') b' ~ Output a (a -> b)

seems to fail since we would need a ~ (a' -> b') ~ (a' -> a -> b) which is impossible, with finite types. For some reason, GHC does not use this argument (does it pretend infinite types exist in this check? why?)

Anyway, this makes replacing fundeps with type families harder than it could be, it seems. I have no idea about why GHC accepts the fundeps code I posted, yet refuses the OP's code which is essentially the same thing, except using type families.

Upvotes: 1

Related Questions