Тип неоднозначность в семьях типа Haskell

Question

Я пытаюсь соединить следующий класс Domain и его экземпляр TrivialDomain

{-# LANGUAGE TypeFamilies #-} 

data Transition = Transition 

class Domain d where 
    type Set d 
    type Engine d :: * -> * 

    top :: Engine d (Set d) 

    -- ... 
    complement :: Set d -> Engine d (Set d) 
    exclude :: Set d -> Set d -> Engine d (Set d) 
    -- ... 

data TrivialDomain = TrivialDomain 

instance Domain TrivialDomain where 
    type Set TrivialDomain = [Int] 
    type Engine TrivialDomain = IO 

    top = return [0..10] 

    -- ... 
    complement a = top >>= (flip exclude) a 
    exclude a b = return $ filter (not . (`elem` b)) a 
    -- ... 

, но я получаю следующее сообщение об ошибке, которую я не понимаю,

test3.hs:25:21: 
    Couldn't match type ‘Engine d0’ with ‘IO’ 
    The type variable ‘d0’ is ambiguous 
    Expected type: IO (Set d0) 
     Actual type: Engine d0 (Set d0) 
    In the first argument of ‘(>>=)’, namely ‘top’ 
    In the expression: top >>= (flip exclude) a 
test3.hs:25:35: 
    Couldn't match type ‘Set d1’ with ‘[Int]’ 
    The type variable ‘d1’ is ambiguous 
    Expected type: Set d0 -> [Int] -> IO [Int] 
     Actual type: Set d1 -> Set d1 -> Engine d1 (Set d1) 
    In the first argument of ‘flip’, namely ‘exclude’ 
    In the second argument of ‘(>>=)’, namely ‘(flip exclude) a’ 

I Would ожидайте, что Engine d (Set d) разрешит IO [Int] в объявлении экземпляра, который, похоже, не так. По крайней мере, GHC так не думает. Что мне не хватает?

Answer 1

В вашем случае связанных типов недостаточно, чтобы вывести типы методов.

У вас есть класс Domain d, а Set и Engine связаны с d. Это означает, что всякий раз, когда в нашей программе есть известный d с известным примером Domain d, GHC может разрешить Set d и Engine d. Но это не работает в обратном направлении. GHC не может разрешить d или экземпляр Domain из-за наличия Set d или Engine d, так как вполне возможно, что существуют разные экземпляры Domain с теми же типами Set и Engine.

Так как методы вашего класса относятся только к Set и Engine, Domain d никогда не может быть выведено из использования метода.

Вы можете сделать пару вещей в зависимости от ваших целей.

Во-первых, вы могли бы сделать d зависеть от Set и Engine:

class Domain set engine where 
    type DomainOf set engine :: * 
    -- ... 

В целом, FunctionalDependencies дает гораздо больше возможностей для обеспечения соблюдения зависимостей между типами. Например, вы можете определенно заявить, что есть только один d для каждого Set, что достаточно, чтобы восстановить хороший вывод типа:

class Domain d set engine | d -> set engine, set -> d where 

    top  :: engine set 
    complement :: set -> engine set 
    exclude :: set -> set -> engine set 

data TrivialDomain = TrivialDomain 

instance Domain TrivialDomain [Int] IO where 

    top = return [0..10] 

    complement a = top >>= (flip exclude) a 

    exclude a b = return $ filter (not . (`elem` b)) a 

Наконец, если вы хотите использовать свой исходный класс, вы должны добавить Proxy d параметров ваши методы, для того, чтобы сделать экземпляр и связанных с ними типов разрешаемых:

import Data.Proxy 

data Transition = Transition 

class Domain d where 
    type Set d 
    type Engine d :: * -> * 

    top  :: Proxy d -> Engine d (Set d) 
    complement :: Proxy d -> Set d -> Engine d (Set d) 
    exclude :: Proxy d -> Set d -> Set d -> Engine d (Set d) 

data TrivialDomain = TrivialDomain 

instance Domain TrivialDomain where 
    type Set TrivialDomain = [Int] 
    type Engine TrivialDomain = IO 

    top _ = return [0..10] 

    complement d a = top d >>= (flip (exclude d)) a 
    exclude d a b = return $ filter (not . (`elem` b)) a 

Здесь цель Proxy d является точно указать, какой экземпляр вы хотите использовать.

Однако это означает, что мы должны написать top (Proxy :: Proxy d) по каждому способу использования (аналогично другим методам), что является довольно обременительным. С GHC 8 можно опустить Proxy с и использовать TypeApplications вместо:

{-# language TypeApplications, TypeFamilies #-} 

-- ... 

instance Domain TrivialDomain where 
    type Set TrivialDomain = [Int] 
    type Engine TrivialDomain = IO 

    top = return [0..10] 

    complement a = top @TrivialDomain >>= (flip (exclude @TrivialDomain)) a 
    exclude a b = return $ filter (not . (`elem` b)) a