Why am I getting "Non-exhaustive patterns in function..." when I invoke my Haskell substring function?

Question

I'm working my way through the book The Haskell Road to Logic, Maths and Programming. (I'm only mid-way through chapter 1, but I'm enjoying it so far and intend to continue.) I've read through the section 1.5 "Playing the Haskell Game" which "consists of a number of further examples to get you acquainted with [Haskell]". So far I've learned about functions, type declarations, guarded equations, a little about list pattern matching, and where & let.

I'm stuck on exercise 1.17, which asks us to write a function substring :: String -> String -> Bool where:

1. if xs is a prefix of ys, xs is a substring of ys
2. if ys equals y:ys' and xs is a substring of ys', xs is a substring of ys
3. nothing else is a substring of ys

I used the prefix function provided in a previous example:

prefix :: String -> String -> Bool
prefix [] ys = True
prefix (x:xs) [] = False
prefix (x:xs) (y:ys) = (x==y) && prefix xs ys

And then tried:

substring :: String -> String -> Bool
subsstring xs [] = False
substring xs (y:ys) | prefix xs (y:ys) = True
                    | substring xs ys  = True
                    | otherwise        = False

...and may other permutations of this.

When I run substring "abc" "xxxabcyyy" I get True, but when I run substring "abc" "xxxabyyy" I get "*** Exception: substring.hs:(3,0)-(5,45): Non-exhaustive patterns in function substring". I can't figure out why. I don't understand how there could be non-exhaustive patterns when I use "otherwise".

BTW, the book has not yet covered if-then-else. I'd prefer to keep that out of my solution, for now.

Tessietessier

Answer 1

You have a typo in the function name:

subsstring xs [] = False

Because of the typo this declares a new function subsstring, not a case of the substring function.

The substring function itself then doesn't have any case that would match a second parameter of [].

Rawhide

I can't decide whether to be embarrassed that I wasted your time with a typo, or pleased that my solution worked except for the typo. Thanks. – Tessietessier

This is interesting. You can have one of the most sophisticated type-system around, a simple typo cannot be caught by it. – Preparative

that's what warnings are for. – Bacchanalia

@gawi: It's not a bug, it's a feature! Although you get some warnings if you compile with -Wall. – Birthwort

I've added a related question: #3804984 – Preparative