title: Is there a workaround for the lack of type class backtracking?
body: <p>In <a href="https://www.youtube.com/watch?feature=player_detailpage&amp;v=hIZxTQP1ifo#t=4830" rel="nofollow">this talk around the 1:20 mark</a>, Edward Kmett mentions the lack of "type class backtracking" in Haskell. Consider the problem of "set equality" (where order and multiplicity are disregarded) implemented on lists:</p>
  
  <pre><code>equals :: [a] -&gt; [a] -&gt; Bool
  </code></pre>
  
  <p>By the nature of type classes I cannot provide an inefficient O(n²) comparison if all we have is <code>Eq a</code> but efficiently compare the lists in O(n log n) if we have <code>Ord a</code>.</p>
  
  <p>I did understand why such a facility would be problematic. At the same time, Edward says that there are "tricks you could play" mentioning for instance type families.</p>
  
  <p>Hence my question is, what would be a workaround to achieve the same effect:</p>
  
  <ul>
  <li>an (inefficient) default implementation is provided</li>
  <li>if the user can provide some additional information about the type, we "unlock" a more efficient implementation</li>
  </ul>
  
  <p>This workaround does not necessarily need to use type classes.</p>
  
  <p><strong>Edit</strong>: Some people suggested simply providing <code>equals</code> and <code>efficientEquals</code> as two distinct methods. In general I agree that this is the more Haskell-idiomatic approach. However, I am not convinced that this is always possible. For instance, what if the equals method above is itself part of a type class:</p>
  
  <pre><code>class SetLike s where
      equals :: Eq a =&gt; s a -&gt; s a -&gt; Bool
  </code></pre>
  
  <p>Assume that this class has been provided by someone else so I cannot simply add a new function to the typeclass. I now want to define the instance for <code>[]</code>. I know that <code>[]</code> can always provide an implementation of <code>equals</code> no matter what constraints there are on <code>a</code> but I cannot tell my instance to use the more efficient version if more information about <code>a</code> is available.</p>
  
  <p>Maybe I could wrap the list in a newtype and tag it with some additional type information?</p>