[Haskell] type class instance selection & search

[Andrzej Jaworski]

Simon Peyton-Jones <simonpj at microsoft.com> wrote:

> 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.

Perhaps linear logic search could make this easier. LolliMon http://www.cs.cmu.edu/~fp/lollimon
shows how it can be done; additional ideas like memory management and concurrency might avail form
this too. I believe that it is high time to revisit logic and Haskell is an excellent ground for
this (e.g. multicore is essentially signal processing that can be elegantly solved probably only by
multivalued logic).

> To be honest I can't see myself trying this anytime soon.  Because of the unification part, it'd
> be a significant structural change.  And one would > need to dig into the theory to make sure that
> the algorithm was both sound and complete (finds all solutions).

Not much of help but a refreshing read: http://www.cs.cmu.edu/~fp/papers/tocl07.pdf

Regards,

-Andrzej