Typeclass resolution in Haskell reporting ambiguity even if there is only one instance

user_14163025 0
Viewed 90

I am experimenting with transitive typeclass instances in Haskell. It is well-known that one cannot declare a transitive instance in the original typeclass (i.e. (C a b, C b c) => C a c). Therefore I tried to define another class representing the transitive closure of the original class instead. Minimal code is as below:

{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE UndecidableInstances #-}
{-# LANGUAGE AllowAmbiguousTypes #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE TypeApplications #-}
module Ambig where

class Coe a b where
  from :: a -> b

class CoeTrans a b where
  from' :: a -> b

instance CoeTrans a a where
  from' = id

instance (Coe a b, CoeTrans b c) => CoeTrans a c where
  from' = from' . from @a @b

instance Coe Bool Int where
  from False = 0
  from True = 1

instance Coe Int Integer where
  from x = toInteger x

where CoeTrans is the transitive closure of Coe. When I'm trying to use from' in CoeTrans, however, it always reports ambiguity:

-- >>> from' True :: Integer
-- Ambiguous type variable ‘b0’ arising from a use of ‘from'’
-- prevents the constraint ‘(Coe Bool b0)’ from being solved.
-- Probable fix: use a type annotation to specify what ‘b0’ should be.
-- These potential instance exist:
--   instance Coe Bool Int
--     -- Defined at /Users/t/Desktop/aqn/src/Ambig.hs:21:10

Even if there is virtually only one instance. But according to GHC docs a typeclass resolution will succeed iff there is one applicable instance.

Why would this happen and is there any way to solve the transitive instance problem?

typeclass ghc functional-programming haskell
1 Answers

I think you misunderstood the docs a bit. They really say that a typeclass resolution for a given type will succeed iff one instance is present. But in your case, no type is given. b0 is ambiguous.

The compiler needs to know b0 before it can pick an instance of Coe Bool b0, even though there is only one in the current scope. And this is done this way on purpose. And the key words there are "current scope". You see, if the compiler could just pick whatever is available in scope, your program would be vulnerable to subtle changes in scope: you may change your imports, or some of your imported modules may change their internal structure. This may result in different instances appearing or disappearing in your current scope, which may result in different behaviour of your program without any kind of warning.

If you really intend for there to always be at most one unambiguous path between any two types, you can solve it by adding a functional dependency to Coe:

class Coe a b | a -> b where
  from :: a -> b

This will have two effects:

  1. The compiler will know that it can always deduce b just by knowing a.
  2. And to facilitate that, the compiler will prohibit multiple instances with same a, but different bs from being defined.

Now the compiler can see that, since the argument of from' is Bool, it must search for an instance of Coe Bool b for some b, and from there it will know for sure what b has to be, and from there it can search for the next instance, and so on.

If, on the other hand, you really intended for there to be multiple possible paths between two given types, and for the compiler to just pick one - you're out of luck. The compiler refuses on principle` to randomly pick one of multiple possibilities - see explanation above.

user_1802860
Related