scratch

§ How GHC Does Typeclass Resolution

created 2021-10-31 · last edited 2021-11-01
  • As told to me by davean:
  • Its like 5 steps
  • Find all instances I that match the target constraint; that is, the target constraint is a substitution instance of I. These instance declarations are the candidates.
  • If no candidates remain, the search fails. Eliminate any candidate IX
  • for which there is another candidate IY such that both of the following hold: IY is strictly more specific than IX. That is, IY is a substitution instance of IX but not vice versa. Either IX is overlappable, or IY is overlapping. (This “either/or” design, rather than a “both/and” design, allow a client to deliberately override an instance from a library, without requiring a change to the library.)
  • If all the remaining candidates are incoherent, the search succeeds, returning an arbitrary surviving candidate.
  • If more than one non-incoherent candidate remains, the search fails.
  • Otherwise there is exactly one non-incoherent candidate; call it the “prime candidate”.
  • Now find all instances, or in-scope given constraints, that unify with the target constraint, but do not match it. Such non-candidate instances might match when the target constraint is further instantiated. If all of them are incoherent top-level instances, the search succeeds, returning the prime candidate. Otherwise the search fails.
  • GHC manual
❦
Newer ৪ Blog ৪ Older