没有类型类的回溯，有解决办法吗？
没有类型类的回溯，有解决办法吗？
提问于 2015-02-17 21:01:48
在在1点20分左右的时候中，Edward提到Haskell中缺少“类型类回溯”。考虑清单上执行的“集合相等”问题(忽略了顺序和多重性)：
equals :: [a] -> [a] -> Bool根据类型类的性质，如果我们只有Eq a，则不能提供低效的O(n平方)比较，但如果有Ord a，则可以有效地比较O(N log )中的列表。
我确实明白为什么这样的设施会有问题。同时，爱德华说有一些“你可以玩的把戏”，比如提到类型的家庭。
因此，我的问题是，怎样才能达到同样的效果：
- 提供了(低效)默认实现。
- 如果用户能够提供有关该类型的其他信息，我们将“解锁”一个更有效的实现。
此解决方案不一定需要使用类型类。
编辑：有些人建议简单地将equals和efficientEquals作为两种不同的方法提供。总的来说，我同意这是更Haskell-惯用的方法。然而，我不相信这总是可能的。例如，如果上面的equals方法本身是类型类的一部分，该怎么办：
class SetLike s where
equals :: Eq a => s a -> s a -> Bool假设这个类是由其他人提供的，所以我不能简单地向类型类型添加一个新函数。现在我要定义[]的实例。我知道[]总是可以提供equals的实现，不管a上有什么约束，但是如果有更多关于a的信息，我不能告诉我的实例使用更高效的版本。
也许我可以将列表包装在一个newtype中，并使用一些附加的类型信息标记它？
回答 1
Stack Overflow用户
回答已采纳
发布于 2015-02-18 17:55:47
在编辑的场景中，可以使用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"页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/28571035
复制相关文章
相似问题
腾讯云开发者
