[Haskell] type class instance selection & search

Claus Reinke claus.reinke at talk21.com
Wed Aug 1 08:25:50 EDT 2007

|My understanding is that this sort of instance collection doesn't work together because instance 
selection is based only on the matching the head of an instance declaration (part after the "=>"). 
I'm wondering why not use the preconditions as well, via a Prolog-like, backward-chaining search for 
much more flexible instance selection?

>It certainly makes sense to do backward chaining, but I don't know any Haskell implementation 
>that's tried it.  It'd be more complicated in the presence of functional dependencies, since we 
>must "undo" any unifications done as a result of discarded searches, much like the "trail" in a 
>Prolog implementation.

there was some discussion of this on the haskell-prime list some time ago,
indicating that there is some room for exploration between the current
no-context and a full backtrack-over-all-contexts. in particular, since
type class semantics these days are based on constraint handling rules,
it would be useful to provide haskell-syntax access to chr guards.

one could then, as in chr, restrict the kind of type predicates permitted
in guards (no backtracking, no unification), and take guards into account
for instance selection, but still "ignore" the full context. that way, one
remains in a committed-choice language, with no unification before
commit, so no need to undo unifications (chr implementations tend to
provide 'unifiable' as well as 'unify', and the former may be used in guards).

in many of the cases i'd like to use the context for instance selection,
the decision comes down to a simple 'unifiable'/'not unifiable', which
could be handled via guards. that is why TypeCast is so central in
HList, or why a more cumbersome encoding via newtypes is often


More information about the Haskell mailing list