Проблема с Eq в Haskell для сравнения списков

Я сам реализую списки в Haskell, но у меня возникла небольшая проблема при сравнении двух списков на равенство,

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 == l1, то вместо True печатается False. Что мне не хватает?


methods equality custom-data-type haskell algebraic-data-types
person Massimo2015MX    schedule 18.03.2021    source источник
comment
(1) Если вы возьмете два равных списка и удалите первый элемент только из одного из них, они перестанут быть равными. (2) В любом случае вам не нужно myElem для реализации (==); просто сравните заголовки списка непосредственно на каждом шаге.   -  person duplode    schedule 18.03.2021
comment
if A then B else False совпадает с A && B.   -  person Will Ness    schedule 18.03.2021
comment
И if A then True else B такое же, как A || B.   -  person molbdnilo    schedule 18.03.2021
comment
@molbdnilo, да. В то время я так далеко не дочитал. :)   -  person Will Ness    schedule 18.03.2021

Ответы (1)


arrow_upward
4
arrow_downward

Ваш equalHelp реализует предикат isSubset 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 и вместо этого сравнивать только заголовки двух списков аргументов на каждом шаге рекурсии для нормальной, так сказать, концепции равенства.

person Will Ness    schedule 18.03.2021