CODEWITHSUNDEEP
haskellmethodsequalityalgebraic-data-typescustom-data-type
Massimo2015MX
Massimo2015MX

Reputation: 65

Problem with Eq in Haskell for comparing Lists

I'm implementing Lists in Haskell by myself, but I had a little problem while comparing two Lists for equality,

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

For example, if I have

l1 = (Cons 1 (Cons 2 (Cons 3 (Cons 4 (Cons 5 Void)))))

And if I do l1 == l1, then instead of printing True, it prints False. What am I missing?

Upvotes: 3

Views: 368

Answers (1)

Will Ness
Will Ness

Reputation: 71099

Your equalHelp implements isSubset subset ofSet predicate -- almost, except for the fact that it always slides into the empty second list case and then fails.

Instead, stop your recursion on the singleton case:

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

Your second clause assumes a is a non-empty list, because of the preceding clause. But it is better when each clause's assumptions are clear in the open and the patterns are mutually exclusive (if making it so doesn't make our code overly verbose and thus less readable). Thus, we write it as

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

There's one error left intentionally here, a vestige of your code. One of the clauses is erroneous: an empty set is a subset of any set. Thus the two clauses dealing with an empty set as the first argument can be joined together into one clause.

We've also used the code simplifications

if A then True else False   ===   A
if A then B    else False   ===   A && B

in this re-write. There's also

if A then True else C       ===   A || C

which you can use to simplify your myElem definition.

Another way to rectify your code is to treat it as if defining equality of lists up to ordering of the elements. Removing the head element of the second argument as well on each recursive call as suggested in the comments won't do the trick as we need to remove the found element which might not be -- and likely is not -- the head element. This isn't likely to be very simple, nor efficient, especially if you would also opt to allow for multiplicities of elements. In that case, it is easiest to just define

equalUpToOrderingWithMults a b =
    isSubset a b  &&  isSubset b a

The most straightforward way is to just ditch the myElem call and instead compare only the head elements of the two argument lists at each step of the recursion for the "normal", so to speak, concept of equality.

Upvotes: 4

Related Questions