Haskell: Recursion with a polymorphic equality function

Question

Ok so we have not learned polymorphic functions yet, but we still have to write this code.

Given:
nameEQ (a,_) (b,_) = a == b
numberEQ (_,a) (_,b) = a == b
intEQ a b = a == b
member :: (a -> a -> Bool) -> a -> [a] -> Bool

I added:

member eq x ys | length ys < 1 = False
               | head(ys) == x = True
            | otherwise = member(x,tail(ys))

but i get errors about not being the correct type as well as some other stuff. We have to see if an element exists in from some type. So we have those 2 types above. Some examples given:

phoneDB = [("Jenny","867-5309"), ("Alice","555-1212"), ("Bob","621-6613")]

> member nameEQ ("Alice","") phoneDB
True
> member nameEQ ("Jenny","") phoneDB
True
> member nameEQ ("Erica","") phoneDB
False
> member numberEQ ("","867-5309") phoneDB
True
> member numberEQ ("","111-2222") phoneDB
False
> member intEQ 4 [1,2,3,4]
True
> member intEQ 4 [1,2,3,5]
False 

not exactly sure what i need to do here. Any help or documentation on this would be great. Thanks!

Answer 1

Various things (I'm not going to write out the full answer as this is homework):

1. length ys < 1 can be more simply expressed as null ys
2. You don't need brackets around function arguments. head(ys) is more commonly written as head ys
3. You can, if you want, turn the top case and the other two into pattern matches rather than guards. member eq x [] = ... will match the empty case, member eq x (y:ys) = ... will match the non-empty case.
4. You are using == for comparison. But you're meant to use the eq function you're given instead.
5. You are bracketing the arguments to member as if this was Java or similar. In Haskell, arguments are separated by spaces, so member(x,(tail(ys)) should be member x (tail ys).

Answer 2

Those errors you gloss over "about not being the correct type as well as some other stuff" are important. They tell you what's wrong.

For example, the first time I threw your code into ghc I got:

Couldn't match expected type `a -> a -> Bool'
       against inferred type `(a1, [a1])'
In the first argument of `member', namely `(x, tail (ys))'
In the expression: member (x, tail (ys))
In the definition of `member':
    member eq x ys
             | length ys < 1 = False
             | head (ys) == x = True
             | otherwise = member (x, tail (ys))

Well, when I look at it that's straightforward - you've typed

member(x,tail(ys))

When you clearly meant:

member x (tail ys)

Commas mean something in Haskell you didn't intend there.

Once I made that change it complained again that you'd left off the eq argument to member.

The error after that is tougher if you haven't learned about Haskell typeclasses yet, but suffice it to say that you need to use the passed-in eq function for comparing, not ==.

Answer 3

Since the parameters a in member :: (a -> a -> Bool) -> a -> [a] -> Bool don't derive Eq, you can't use == to compare them, but instead have to use the given function eq.

Therefore your code might look like this:

member :: (a -> a -> Bool) -> a -> [a] -> Bool
member eq x ys
 | length ys < 1 = False
 | eq x (head ys) = True
 | otherwise = member eq x (tail ys)

Only problem with this is, that length still requires to evaluate the entire List, so you could reach a a better performance writing:

member' :: (a -> a -> Bool) -> a -> [a] -> Bool
member' eq x (y:ys)
 | eq x y = True
 | otherwise = member' eq x ys
member' _ _ [] = False

With the use of any you can simplify it even more:

member'' :: (a -> a -> Bool) -> a -> [a] -> Bool
member'' f a = any (f a)