  Elaboration-based type class resolution, as found in languages like Haskell,
Mercury and PureScript, is generally nondeterministic: there can be multiple
ways to satisfy a wanted constraint in terms of global instances and locally
given constraints. Coherence is the key property that keeps this sane; it
guarantees that, despite the nondeterminism, programs still behave predictably.
Even though elaboration-based resolution is generally assumed coherent, as far
as we know, there is no formal proof of this property in the presence of
sources of nondeterminism, like superclasses and flexible contexts.
  This paper provides a formal proof to remedy the situation. The proof is
non-trivial because the semantics elaborates resolution into a target language
where different elaborations can be distinguished by contexts that do not have
a source language counterpart. Inspired by the notion of full abstraction, we
present a two-step strategy that first elaborates nondeterministically into an
intermediate language that preserves contextual equivalence, and then
deterministically elaborates from there into the target language. We use an
approach based on logical relations to establish contextual equivalence and
thus coherence for the first step of elaboration, while the second step's
determinism straightforwardly preserves this coherence property.
