Fundamentals of Haskell Type Classes and “could not deduce (~) from the context (~)” error

Question

I'm relatively new to Haskell, and I believe I'm misunderstanding something fundamental about type classes. Suppose I'd like to create a type class 'T' implementing n-ary trees supported by four algebraic types 'A, B, C, and D' whose structure imposes a maximum depth of four. This seems like a silly example but I think it best illustrates my point.

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 _) = []

I'd like to write generic parent and children functions, but GHC isn't having any of it.

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

I (think I) understand that type classes aren't at all like Java interfaces, in that the class-level functions must work for any possible value of the provided type variables; the caller isn't "deciding" the type. I don't understand why GHC can't deduce (t1 ~ _), because the type substituted for t1 is always an instance of 'T'. I see that there's a sort of circular dependency among the instance declarations, e.g. A's instance declaration depends on B's being valid, which depends on A's and C's, and so on, but I feel as though GHC is smart enough to figure that out and I'm simply missing something. I always seem to get this error whenever I'd like a function in a type class to accept one type in the class but return another... Is there a way to accomplish this with type classes?

I see that there are many similarly-worded questions here, but I have yet to find one that matches my problem(as far as I can tell).

Thanks in advance.

leftaroundabout leftaroundabout · Accepted Answer · 2014-01-06T23:54:56

You've correctly understood the problem: these signatures really mean

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

rather that what you'd have in a covariant OO language,

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

The two usual solutions for such kind of stuff are to use the similar syntactic extensions

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

...

or MultiparamTypeClasses

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

instance T A B where
...

Note that in both cases, D won't have an instance.

As to which of these extensions is "better" – you can't really answer that. MultiparamTypeClasses by itself is often too "weak" in that you need to fix all the involved types manually, but that can be lifted through adding a FunctionalDependency. In a special case of class T child t0 | t0 -> child, that's then largely equivalent to the TypeFamilies solution. But in your case, class T child t0 | t0 -> child, child -> t0 would also be possible.

Consider the Haskell Wiki for details.

Fundamentals of Haskell Type Classes and “could not deduce (~) from the context (~)” error

2 Answers