Haskell类型类的基础知识和"无法从上下文(〜)中推断出(〜)"错误

Question

我对Haskell比较陌生,我相信我误解了关于类型类的基本内容.假设我想创建一个类型类'T',实现由四个代数类型'A,B,C和D'支持的n-ary树,其结构最大深度为4.这似乎是一个愚蠢的例子,但我认为这最能说明我的观点.

module Test where

class T t0 where
    parent :: T t1 => t0 -> Maybe t1
    children :: T t1 => t0 -> [t1]

data A = A [B]
instance T A where
    parent (A _) = Nothing
    children (A bs) = bs

data B = B A [C]
instance T B where
    parent (B a _) = Just a
    children (B _ cs) = cs

data C = C B [D]
instance T C where
    parent (C b _) = Just b
    children (C _ ds) = ds

data D = D C
instance T D where
    parent (D c) = Just c
    children (D _) = []

我想编写通用的父和子函数,但GHC没有任何函数.

Test.hs:10:27:
    Could not deduce (t1 ~ B)
    from the context (T t1)
      bound by the type signature for children :: T t1 => A -> [t1]
      at Test.hs:10:9-28
      `t1' is a rigid type variable bound by
           the type signature for children :: T t1 => A -> [t1]
           at Test.hs:10:9
    Expected type: [t1]
      Actual type: [B]
    In the expression: bs
    In an equation for `children': children (A bs) = bs
    In the instance declaration for `T A'

Test.hs:14:31:
    Could not deduce (t1 ~ A)
    from the context (T t1)
      bound by the type signature for parent :: T t1 => B -> Maybe t1
      at Test.hs:14:9-31
      `t1' is a rigid type variable bound by
           the type signature for parent :: T t1 => B -> Maybe t1
           at Test.hs:14:9
    In the first argument of `Just', namely `a'
    In the expression: Just a
    In an equation for `parent': parent (B a _) = Just a

Test.hs:15:29:
    Could not deduce (t1 ~ C)
    from the context (T t1)
      bound by the type signature for children :: T t1 => B -> [t1]
      at Test.hs:15:9-30
      `t1' is a rigid type variable bound by
           the type signature for children :: T t1 => B -> [t1]
           at Test.hs:15:9
    Expected type: [t1]
      Actual type: [C]
    In the expression: cs
    In an equation for `children': children (B _ cs) = cs
    In the instance declaration for `T B'

Test.hs:19:31:
    Could not deduce (t1 ~ B)
    from the context (T t1)
      bound by the type signature for parent :: T t1 => C -> Maybe t1
      at Test.hs:19:9-31
      `t1' is a rigid type variable bound by
           the type signature for parent :: T t1 => C -> Maybe t1
           at Test.hs:19:9
    In the first argument of `Just', namely `b'
    In the expression: Just b
    In an equation for `parent': parent (C b _) = Just bv

我(我想)理解类型类完全不像Java接口,因为类级函数必须适用于所提供类型变量的任何可能值; 调用者不是"决定"类型.我不明白为什么GHC不能推断(t1~_),因为替换t1的类型总是'T'的实例.我看到实例声明之间存在一种循环依赖关系,例如A的实例声明取决于B的有效性,这取决于A和C,等等,但我觉得GHC足够聪明,可以解决这个问题.我只是遗漏了一些东西.每当我想要类型类中的函数接受类中的一个类型但返回另一个类型时,我似乎总是会得到这个错误...有没有办法用类型类完成这个？

我看到这里有许多类似措辞的问题,但我还没有找到一个与我的问题相符的问题(据我所知).

提前致谢.

Answer 1

你已经正确地理解了这个问题:这些签名确实意味着

parent :: forall t1 . T t1 => t0 -> Maybe t1

而是你在协变的OO语言中所拥有的,

parent :: exists t1 . T t1 => t0 -> Maybe t1

这类东西的两种常用解决方案是使用类似的句法扩展

• TypeFamilies

  class T t0 where
    type Child t0 :: *
    parent :: Child t0 -> Maybe t0
    children :: t0 -> [Child t 0]
  
  instance T A where
    type Child A = B
    parent (A _) = Nothing
  
  ...
  

• 要么 MultiparamTypeClasses

  class T child t0 where
    parent :: child -> Maybe t0
    children :: t0 -> [child]
  
  instance T A B where
  ...
  

请注意,在这两种情况下,D都不会有实例.

至于哪些扩展"更好" - 你无法真正回答这个问题.MultiparamTypeClasses本身通常太"弱",因为你需要手动修复所有涉及的类型,但可以通过添加一个来解除FunctionalDependency.在特殊情况下class T child t0 | t0 -> child,这在很大程度上等同于TypeFamilies解决方案.但在你的情况下,class T child t0 | t0 -> child, child -> t0也是可能的.

有关详细信息,请考虑Haskell Wiki.