提问人：Massimo2015MX 提问时间：3/18/2021 最后编辑：Will NessMassimo2015MX 更新时间：3/19/2021 访问量：290
Haskell中用于比较列表的Eq问题
Problem with Eq in Haskell for comparing Lists
问：
我自己在Haskell中实现了Lists，但是在比较两个List是否相等时遇到了一个小问题，
data List a = Void | Cons a (List a) -- deriving (Show, Eq)
instance (Eq a) => Eq (List a) where
(==) a b = equalHelp a b
equalHelp :: (Eq a) => List a -> List a -> Bool
equalHelp Void Void = True
equalHelp a Void = False
equalHelp Void b = False
equalHelp (Cons a b) l = if (myElem a l) then (equalHelp b l) else False
myElem :: (Eq a) => a -> List a -> Bool
myElem a Void = False
myElem a (Cons c d) = if (a == c) then True
else myElem a d
例如，如果我有
l1 = (Cons 1 (Cons 2 (Cons 3 (Cons 4 (Cons 5 Void)))))
如果我这样做，那么它不会打印，而是打印。
我错过了什么？l1 == l1TrueFalse
答：
4赞
Will Ness
3/18/2021
#1
你的实现谓词 -- 几乎，除了它总是滑入空的第二个列表情况然后失败的事实。equalHelpisSubset subset ofSet
相反，请停止对单例情况的递归：
isSubset :: (Eq a) => List a -> List a -> Bool
isSubset Void Void = True
isSubset a Void = False
isSubset Void b = False
isSubset (Cons a Void) l = if (myElem a l) then True else False
isSubset (Cons a b) l = if (myElem a l) then (isSubset b l) else False
由于前面的子句，第二个子句假定是一个非空列表。但是，当每个子句的假设都是公开的，并且模式是相互排斥的时，情况会更好（如果这样做不会使我们的代码过于冗长，从而降低可读性）。因此，我们将其写为a
isSubset :: (Eq a) => List a -> List a -> Bool
isSubset Void Void = True
isSubset (Cons _ _) Void = False
isSubset Void (Cons _ _) = False
isSubset (Cons a Void) l = myElem a l
isSubset (Cons a b) l = myElem a l && isSubset b l
这里故意留下了一个错误，这是代码的残留物。其中一个子句是错误的：空集是任何集的子集。因此，将空集作为第一个参数的两个子句可以连接成一个子句。
我们还使用了代码简化
if A then True else False === A
if A then B else False === A && B
在这次重写中。还有
if A then True else C === A || C
您可以使用它来简化您的定义。myElem
纠正代码的另一种方法是将其视为定义列表的相等性，直至元素的排序。按照注释中的建议，在每次递归调用中也删除第二个参数的 head 元素不会奏效，因为我们需要删除找到的元素，它可能不是 - 也可能不是 - head 元素。这不太可能非常简单，也不太可能有效，特别是如果您还选择允许元素的多样性。在这种情况下，最简单的定义
equalUpToOrderingWithMults a b =
isSubset a b && isSubset b a
最直接的方法是放弃调用，而是在递归的每个步骤中只比较两个参数列表的头元素，以获得“正常”的，可以说是相等的概念。myElem
评论
myElem(==)if A then B else False与 相同。A && Bif A then True else BA || B