我可以从函数依赖中魔术化类型相等吗？

Question

我正在尝试了解 MultiParamTypeClasses 和 FunctionalDependencies，下面的内容让我印象深刻：

{-# LANGUAGE MultiParamTypeClasses
           , FunctionalDependencies
           , TypeOperators #-}

import Data.Type.Equality

class C a b | a -> b

fob :: (C a b, C a b') => proxy a -> b :~: b'
fob _ = Refl

不幸的是，这不起作用； GHC 不会从该上下文中得出结论 b ~ b'。有什么方法可以使这项工作起作用，或者功能依赖性是否 "internally" 不可用？

Answer 1

我不认为这个事实（如 fob 的类型所述）是真的。由于 classes 类型的开放世界属性，您可以违反具有模块边界的 fundep。

下面的例子说明了这一点。这段代码只在 GHC 7.10.3 上测试过（fundeps 在旧版本中被大量破坏 - 不知道那时会发生什么）。假设您确实可以实现以下内容：

module A 
  (module A
  ,module Data.Type.Equality
  ,module Data.Proxy
  )where 

import Data.Type.Equality
import Data.Proxy 

class C a b | a -> b 

inj_C :: (C a b, C a b') => Proxy a -> b :~: b' 
inj_C = error "oops"

然后还有几个模块：

module C where 
import A

instance C () Int 

testC :: C () b => Int :~: b 
testC = inj_C (Proxy :: Proxy ())

和

module B where 
import A

instance C () Bool 

testB :: C () b => b :~: Bool 
testB = inj_C (Proxy :: Proxy ())

和

module D where 

import A 
import B
import C 

oops :: Int :~: Bool
oops = testB

oops_again :: Int :~: Bool 
oops_again = testC

Int :~: Bool显然不成立，因此自相矛盾，inj_C不存在。

我相信如果您不从定义它的模块中导出 class C，您仍然可以安全地使用 unsafeCoerce 编写 inj_C。我已经使用过这种技术，并且进行了广泛的尝试，但无法写出矛盾。不是说不可能，但至少是非常困难和罕见的边缘情况。

Answer 2

您无需求助于多个模块来欺骗功能依赖性检查器。这里有两个仍然使用 HEAD 构建的错误 fundeps 的例子。它们改编自 GHC 测试套件。

{-# LANGUAGE MultiParamTypeClasses, FunctionalDependencies,
             FlexibleInstances, FlexibleContexts,
             UndecidableInstances, DataKinds, PolyKinds,
             GADTs #-}

module M where


data K x a = K x

class Het a b | a -> b where
  het :: m (f c) -> a -> m b
instance Het t t where het = undefined

class GHet (a :: * -> *) (b :: * -> *) | a -> b
instance            GHet (K a) (K [a])
instance Het a b => GHet (K a) (K b)


data HBool = HFalse | HTrue

class TypeEq x y b | x y -> b
instance {-# OVERLAPS #-} (HTrue ~ b)  => TypeEq x x b
instance {-# OVERLAPS #-} (HFalse ~ b) => TypeEq x y b

fundep 检查器仍然比以前好得多！

我可以从函数依赖中魔术化类型相等吗？

Can I magic up type equality from a functional dependency?

haskell

typeclass