Is there a workaround for the lack of type class backtracking?

Question

In this talk around the 1:20 mark, 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:

equals :: [a] -> [a] -> Bool

By the nature of type classes I cannot provide an inefficient O(n²) comparison if all we have is Eq a but efficiently compare the lists in O(n log n) if we have Ord a.

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.

Hence my question is, what would be a workaround to achieve the same effect:

• an (inefficient) default implementation is provided
• if the user can provide some additional information about the type, we "unlock" a more efficient implementation

This workaround does not necessarily need to use type classes.

Edit: Some people suggested simply providing equals and efficientEquals 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:

class SetLike s where
    equals :: Eq a => s a -> s a -> Bool

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 []. I know that [] can always provide an implementation of equals no matter what constraints there are on a but I cannot tell my instance to use the more efficient version if more information about a is available.

Maybe I could wrap the list in a newtype and tag it with some additional type information?

Answer 1

In the scenario from your edit, you could use a GADT as proof of your Ord constraint:

{-# LANGUAGE GADTs #-}

import Data.List

class SetLike s where
    equals :: Eq a => s a -> s a -> Bool

data OrdList a where
    OrdList :: Ord a=> [a] -> OrdList a

instance SetLike OrdList where
    equals (OrdList a) (OrdList b) = sort a == sort b

And for fun here's something that uses makes use of the OverlappingInstances trick I mention in my comment. There are lots of ways to do this sort of thing:

{-# LANGUAGE DefaultSignatures, OverlappingInstances, UndecidableInstances, MultiParamTypeClasses, FlexibleInstances #-}

import Data.List

class Equals a where
    equals :: [a] -> [a] -> Bool

    default equals :: Ord a=> [a] -> [a] -> Bool
    equals as bs = sort as == sort bs

instance Equals Int
instance Equals Integer
instance Equals Char
-- etc.

instance (Eq a)=> Equals a where
    equals = error "slow version"