overlapping pattern matching instances: help needed

Submitted by metaperl on Thu, 10/06/2005 - 2:21am.

I am being told that I have overlapping pattern matches. I'm pretty sure it has to do with the otherwise clause and the following subString (x:xs) [] clause, but I don't know how to fix it

prefix [] ys = True
prefix xs [] = False
prefix [x] [y] = (x == y)
prefix (x:xs) (y:ys) = (x == y) && prefix xs ys

subString xs ys
| prefix xs ys = True
| otherwise = subString xs ys'
where ys' = tail ys
subString (x:xs) [] = False

Submitted by jgoerzen on Thu, 10/06/2005 - 6:58am.

The problem is with these two lines:

subString xs ys
subString (x:xs) [] = False

The first line will match any parameters whatsoever, including empty lists. It's perfectly valid for xs and ys to both be empty. Probably you want to put that second one up above.

Incidentally, I would find it clearer to write this as:

prefix []     _      = True
prefix _      []     = False
prefix [x]    [y]    = (x == y)
prefix (x:xs) (y:ys) = (x == y) && prefix xs ys

subString _      []      = False
subString xs     ys
          | prefix xs ys     = True
          | otherwise        = subString xs (drop ys)

The underscore serves as a wildcard and emphasizes the point that you don't care what is at that spot.

Submitted by dtlin on Fri, 10/07/2005 - 12:59pm.

Shorter and more obvious.  In my opinion.

prefix (x:xs) (y:ys) | x == y = prefix xs ys
prefix [] _ = True
prefix _ _ = False

subString xs ys | prefix xs ys = True
subString xs (_:ys) = subString xs ys
subString _ _ = False

At least, it's ordered in the way I'd expect.

Anyways, metaperl, a demonstration of what jgoerzen said:
subString xs ys
| prefix xs ys = True
| otherwise = subString xs ys'
where ys' = tail ys
{- subString (x:xs) []
== subString (x:xs) ys' where ys' = tail []
== fail "can't take tail of empty list" -}
subString (x:xs) [] = False -- this is never reached

Overlapping pattern matches are a warning, not an error, but usually means there's something wrong.

Also,
prefix [] ys = True
prefix xs [] = False
-- prefix [x] [y] = (x == y) -- doesn't need to exist
prefix (x:xs) (y:ys) = (x == y) && prefix xs ys
{- prefix [x] [y]
== prefix (x:[]) (y:[])
== (x == y) && prefix [] []
== (x == y) && True
== (x == y) -}

but that's not a problem, really.  If prefix [x] [y] came after prefix (x:xs) (y:ys), then you'd get overlapping pattern matches there, too.

Submitted by lightstep on Fri, 10/07/2005 - 4:08pm.

Using the library functions

The subString function doesn't have to be specified by pattern matching, with or without guards. The function checks whether xs is a prefix of ys, or of any of the tails of ys.

This is encoded by the Standard Prelude functions List.tails and Prelude.any. The actual code for subString would be:

subString xs ys = any (prefix xs) (tails ys)

Of course, if you already import List, you might as well use isPrefixOf for prefix.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.