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?

This is quite interesting and I don't know the answer to this. But a quick and dirty solution would be to define a different function like efficientEquals :: (Ord a) => [a] -> [a] -> Bool and equals :: (Eq a) => [a] -> [a] -> Bool. — Shoe
Please make it clear that we are talking about comparing lists disregarding order (and possibly multiplicity as well). Clearly (==) does not require O(n^2) on lists. — chi
There are some techniques using OverlappingInstances, or closed type families that can be used to get something like what you're looking for in some cases (though not really here; unless you're okay with, say, enumerating/duplicating all types with Ord instances you care about). See the "advanced overlap" wiki page. The "extra method trick" might also be relevant here. — jberryman
The main problem here is that Eq is a superclass of Ord. So every Ord type is also an Eq type, which means you want your Eq case to be selected only for cases where there Ord a does not hold. The type class system in Haskell is strongly designed to make sure it never commits to the negative of a constraint; this property is at the heart of a lot of the consistency guarantees it provides, because with separate compilation of modules GHC can never tell the difference between "no instance exists" and "no instance is in scope". — Ben
I can think of ways you could come up with an equals that works with both Eq and Ord instances, but I can't think of any way that wouldn't just complain about ambiguous type variables when called on things are instances of Ord. You'd end up having to manually say (equals :: Ord a => [a] -> [a] -> Bool) xs ys at every call site. And if you're willing to manually declare which version of equals you want to call, they might as well have different names so it's easier to do so. — Ben

jberryman jberryman · Accepted Answer · 2015-02-18T17:55:47

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"

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

1 Answers