缺少 type class 回溯是否有解决方法？

Question

在this talk around the 1:20 mark中，Edward Kmett提到在Haskell中缺少"type class backtracking"。考虑在列表上实现的 "set equality"（忽略顺序和多重性）的问题：

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

根据类型 classes 的性质，如果我们只有 Eq a，我无法提供低效的 O(n²) 比较，但如果我们可以有效地比较 O(n log n) 中的列表有 Ord a.

我确实理解为什么这样的设施会有问题。同时，爱德华说 "tricks you could play" 提到了实例类型族。

因此我的问题是，实现相同效果的解决方法是什么：

提供了一个（低效的）默认实现
如果用户可以提供一些关于该类型的额外信息，我们"unlock"一个更有效的实现

此解决方法不一定需要使用类型classes。

Edit：有些人建议只提供 equals 和 efficientEquals 作为两种不同的方法。总的来说，我同意这是更 Haskell 惯用的方法。但是，我不相信这总是可能的。例如，如果上面的 equals 方法本身是类型 class:

的一部分会怎样？

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

假设这个 class 是由其他人提供的，所以我不能简单地向类型 class 添加一个新函数。我现在想为 [] 定义实例。我知道 [] 总是可以提供 equals 的实现，无论 a 有什么限制，但如果有关 [=20 的更多信息，我不能告诉我的实例使用更高效的版本=]可用。

也许我可以将列表包装在一个新类型中并用一些额外的类型信息标记它？

Answer 1

在您编辑的场景中，您可以使用 GADT 作为 Ord 约束的证明：

{-# 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

为了好玩，这里使用了我在评论中提到的 OverlappingInstances 技巧。有很多方法可以做这种事情：

{-# 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"

缺少 type class 回溯是否有解决方法？

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

haskell

typeclass