haskell implementation of "zip" strange error

Question

I have the following implementation of the zip function in haskell

myzip (a:b) (z:g)
    | b == [] = []
    | g == [] = []
    | otherwise = (a,z) : myzip b g

When I load it into ghci, I get the following error

No instance for (Eq b)
  arising from a use of `=='
In the expression: g == []
In a stmt of a pattern guard for
               an equation for `myzip':
  g == []
In an equation for `myzip':
    myzip (a : b) (z : g)
      | b == [] = []
      | g == [] = []
      | otherwise = (a, z) : myzip b g

Failed, modules loaded: none.

I'm really not sure why this isn't working. Can anybody offer me any help?

Answer 1

Actually the function you've given in the question compiles fine. You would get the error you've quoted if what you had was instead:

myzip :: [a] -> [b] -> [(a, b)]
myzip (a:b) (z:g)
    | b == [] = []
    | g == [] = []
    | otherwise = (a, z) : myzip b g

With an explicit type signature saying that myzip works on list of any types a and b. But you've used b == [] and g == []. The equality operator isn't defined on any type, only on types which are a member of the Eq type class, so the code you've written doesn't match the type you gave.

This is what the error message says pretty straightforwardly, but if you're just learning and haven't gotten up to type classes yet, then it's a bit unclear.

If you change the type signature for myzip to say that a and b need to be members of the Eq type class, then the code you gave will work:

myzip :: (Eq a, Eq b) => [a] -> [b] -> [(a, b)]

Or if you leave the type signature off entirely (as you did in the question), GHC actually infers this type from the fact that you used the == operator, and the code simply compiles as-is.

However, checking whether a list is empty can be done without using the == operator, so you can write myzip so that it really does operate on any types a and b. One way is to use the null function:

myzip :: [a] -> [b] -> [(a, b)]
myzip (a:b) (z:g)
    | null b = []
    | null g = []
    | otherwise = (a, z) : myzip b g

But a much more common way is to simply use multiple equations to define myzip, with base cases matching against the pattern [] and a main case that gets to assume that the lists are non-empty:

myzip :: [a] -> [b] -> [(a, b)]
myzip (a:[]) _ = []
myzip _ (z:[]) = []
myzip (a:b) (z:g) = (a, z) : myzip b g

Note that this style has also made it obvious that there's a bug in your implementation. You're throwing away the last a or z, and there's no case for when the lists are completely empty!

When your equation said myzip (a:b) (z:g) and then checked b and g against the empty list, it was actually checking the wrong thing too late. You don't need to check if b is [], you need to check whether the whole list was empty. But you'd already assumed it wasn't empty and decomposed it into a:b. This results in your code (a) returning the wrong result, because it discards the last pair of elements it should be zipping and (b) producing an error when one of the arguments is the empty list.

Recursion on lists normally looks more like this:

myzip :: [a] -> [b] -> [(a, b)]
myzip [] _ = []
myzip _ [] = []
myzip (a:b) (z:g) = (a, z) : myzip b g

This behaves correctly.