缺少类型类回溯是否有解决方法？

Question

在围绕1:20标记的讨论中,Edward Kmett提到Haskell缺乏"类型回溯".考虑在列表上实现的"集合相等"(其中顺序和多重性被忽略)的问题:

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

根据类型类的性质,我不能提供低效的O(n²)比较,如果我们只有,Eq a但如果有的话,有效地比较O(n log n)中的列表Ord a.

我确实理解为什么这样的设施会有问题.与此同时,爱德华说,有一些"你可以玩的技巧",例如提到类型家庭.

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

• 提供(低效的)默认实现
• 如果用户可以提供有关类型的一些其他信息,我们将"解锁"更有效的实现

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

编辑:一些人认为简单地提供equals和efficientEquals为两个不同的方法.总的来说,我同意这是更多Haskell惯用法.但是,我不相信这总是可行的.例如,如果上面的equals方法本身是类型类的一部分,那该怎么办:

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

假设此类已由其他人提供,因此我不能简单地向类型类添加新函数.我现在想要定义实例[].我知道无论有什么约束,都[]可以提供实现,但如果有更多信息可用,我无法告诉我的实例使用更高效的版本.equalsaa

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

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"