[Haskell-cafe] overlapping instances,
selecting if type a does not belong to class?
oleg at pobox.com
oleg at pobox.com
Mon Feb 26 19:45:57 EST 2007
Marc Weber wrote:
> class (HList c) => HListAppendArbitrary a b c | a b -> c where
> hAppendArbitrary :: a -> b -> c
>
> -- instance HList + HList (1)
> instance (HList a, HList b, HAppend a b c, HList c)
> => HListAppendArbitrary a b c where
> hAppendArbitrary a b = hAppend a b
>
> -- overlapping instance HList + value (2)
> instance (HList a, HList c)
> => HListAppendArbitrary a b c where
> hAppendArbitrary a b = HCons b a
In Haskell, instances are selected based on the _type_ (rather than
class) and only the instance head is considered in the process. The
instance constraints are checked only _after_ the instance has been
selected, but not during the process. In the above example, if we
disregard the instance constraints, the instances become
instance ListAppendArbitrary a b c
instance ListAppendArbitrary a b c
they are indeed the same: hence the typechecker complaint.
That said, it is quite possible in Haskell to achieve genuine
class-based dispatch, with backtracking if necessary:
http://pobox.com/~oleg/ftp/Haskell/poly2.txt
However, it seems that your particular problem can be solved with
simpler means:
> instance (HList a) => HListAppendArbitrary a HNil a where
> hAppendArbitrary a _ = a
> instance (HList a, HList b, HList c)
> => HListAppendArbitrary a (HCons b d) c where
> hAppendArbitrary a b = hAppend a b -- or use HCons with recursion
>
> -- overlapping instance HList + value (2)
> instance (HList a, HList c)
> => HListAppendArbitrary a b c where
> hAppendArbitrary a b = HCons b a
Besides, the constraint |HList a| is equivalent to |a| being either
HNil or HCons x y. Using the structural induction is always
preferable.
Incidentally, the code in your previous messages contained
-fallow-incoherent-instances. I'd like to caution against using this
extension. It makes GHC commit to a general instance even if more
specific exist (and could be selected if more type information becomes
available). Therefore, enabling this extension may lead to surprises.
Sometimes this extension is indeed necessary and essential, when we
wish to compare type variables for identity. These cases are rare
however.
More information about the Haskell-Cafe
mailing list