[Haskell-cafe] overlapping instances, selecting if type a does not belong to class?

[oleg at pobox.com]

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.