Haskell - Pattern match(es) are overlapped

Question

test :: String -> String -> Int

test' x y n = n
test' "" (y:ys) n = error "error"
test' (x:xs) "" n = error "error"
test' (x:xs) (y:ys) n =
        if      x == y
        then    test'  xs ys n
        else    test'  xs ys (n+1)
test a b = test' a b 0

When I compile this, I get this output:

Warning: Pattern match(es) are overlapped

And the answer is always "0", which is not what I intended. What is the problem with the code and how to fix it?

Answer 1

test' x y n = n will match for every call, the other patterns won't be considered. I think this case should be test' "" "" n = n. You get the same result if you move your original line at the end (when all other cases fail), but then you should write test' _ _ n = n which shows that you deliberately ignore some of the arguments.

[Edit]

A shorter solution would be:

test a b | length a == length b = sum $ map fromEnum $ zipWith (/=) a b
         | otherwise = error "error" 

The zipWith expression generates a list of Bool which is True for every difference. The function fromEnum maps False to 0 and True to 1.

Answer 2

The patterns are tried in order. The first of your patterns for test' always matches, so that case is always used. The first case should probably be

test' "" "" n = n

instead.