As @stephen tetley
has already pointed out when GHC tries to match instance declaration it considers only instance head (the stuff after =>) completely ignoring instance context (stuff before =>), once the unambiguous instance is found it tries to match instance context. Your first problematic example clearly has duplication in instance head but it can easily be fixed by replacing two conflicting instances with one more general instance:
instance (Greaterthan a b r) => Greaterthan (Succ a) (Succ b) r
The second example though is much harder one. I suspect that to make it work in Haskell we need a type-level function which could produce two different result depending on whether a specific instance is defined or not for a particular type arguments (i.e. if there is an instance Child Name1 Name2
- recursively do something with Name2
otherwise return BFalse
). I am not sure if it is possible to code this with GHC types (I suspect it is not).
However, I can propose a "solution" which works for slightly different type of input: instead of implying absence of parent->child
relation (when no instance is defined for such pair) we could explicitly encode all existing relationship using type-level lists. Then we can define Descend
type-level function although it have to rely on much-dreaded OverlappingInstances extension:
{-# LANGUAGE MultiParamTypeClasses, FunctionalDependencies,
FlexibleInstances, FlexibleContexts, TypeOperators,
UndecidableInstances, OverlappingInstances #-}
data Anne
data Bridget
data Caroline
data Donna
data Emily
data Fred
data George
-- Type-level list
data Nil
infixr 5 :::
data x ::: xs
-- `bs` are children of `a`
class Children a bs | a -> bs
instance Children Anne (Bridget ::: Nil)
instance Children Bridget (Caroline ::: Donna ::: Nil)
instance Children Caroline (Emily ::: Nil)
-- Note that we have to specify children list for everyone
-- (`Nil` instead of missing instance declaration)
instance Children Donna Nil
instance Children Emily Nil
instance Children Fred (George ::: Nil)
instance Children George Nil
-- `or` operation for type-level booleans
class OR a b bool | a b -> bool
instance OR BTrue b BTrue
instance OR BFalse BTrue BTrue
instance OR BFalse BFalse BFalse
-- Is `a` a descendant of `b`?
class Descend a b bool | a b -> bool
instance (Children b cs, PathExists cs a r) => Descend a b r
-- auxiliary function which checks if there is a transitive relation
-- to `to` using all possible paths passing `children`
class PathExists children to bool | children to -> bool
instance PathExists Nil a BFalse
instance PathExists (c ::: cs) c BTrue
instance (PathExists cs a r1, Children c cs1, PathExists cs1 a r2, OR r1 r2 r)
=> PathExists (c ::: cs) a r
-- Some tests
instance Show BTrue where
show _ = "BTrue"
instance Show BFalse where
show _ = "BFalse"
t1 :: Descend Donna Anne r => r
t1 = undefined -- outputs `BTrue`
t2 :: Descend Fred Anne r => r
t2 = undefined -- outputs `BFalse`
OverlappingInstances
is necessary here since 2nd and 3rd instances of PathExists
can both match the case when children
is not empty list but GHC can determine more specific one in our case depending whether the head of the list is equal to to
argument (and if it is it means we have found the path i.e. descendant).