please help me understand the pattern match in haskell. i'm a little confused.

Question

if i have somthing like that:

func (x1:x2:x3:xs) = xs

then x1,x2,x3 must exist, yes?
they can't be [], but must(again, MUST) be with a value, yes?
also, the xs can be [] or [a] or [a,a,a] (etc'), yes?
(in [a] i mean that it's a list with one number, and [a,a,a] is list of three numbers).

also i have function that define isPrefixOf:

myIsPrefixOf :: (Eq a) => [a] -> [a] -> Bool
[]     `myIsPrefixOf`  []      = True
[]     `myIsPrefixOf`  (x:xs)  = True
list   `myIsPrefixOf`  []      = False
(l:ls) `myIsPrefixOf`  (x:xs)  = if l == x then ls `myIsPrefixOf` xs
                                 else False

if i remove the first pattern, that the function will look like this:

myIsPrefixOf :: (Eq a) => [a] -> [a] -> Bool
[]     `myIsPrefixOf`  (x:xs)  = True
list   `myIsPrefixOf`  []      = False
(l:ls) `myIsPrefixOf`  (x:xs)  = if l == x then ls `myIsPrefixOf` xs
                                 else False

and now i will write:

[] `myIsPrefixOf` [] 

i will get: False(it should be True).
is it because that the first pattern has in his right side element: (x:xs), and because of that, x MUST be with a value, therefore i pass through the first pattern, and get to the second pattern:

list   `myIsPrefixOf`  []      = False

which match, and return False.
am i right?

if i'm right, then the difference is that if i write (x:xs), x MUST be a value and NOT [].
on the other hand, if i write list, it can be match against [] and [a] and [a,a,a] (etc'), and because of that, list of the second pattern, will match to the the first [] in my input, and therefore i'll get False ?
(as before, in [a] i mean that it's a list with one number, and [a,a,a] is list of three numbers).

also, to correct this situation, i need to replace:

[]     myIsPrefixOf  (x:xs)  = True

with that:

[]     `myIsPrefixOf`  list  = True

and now the expressions:

[] `myIsPrefixOf` []
[] `myIsPrefixOf` [1,2,3]

will both match agains:

 [] `myIsPrefixOf` list = True

hope i'm right on those things, and now for another question:
here is the fixed function from the start(after applying the changes)

myIsPrefixOf :: (Eq a) => [a] -> [a] -> Bool
[]     `myIsPrefixOf`  list  = True
list   `myIsPrefixOf`  []      = False
(l:ls) `myIsPrefixOf`  (x:xs)  = if l == x then ls `myIsPrefixOf` xs
                                 else False

now, if i remove the second pattern match, that the function will look like this:

myIsPrefixOf :: (Eq a) => [a] -> [a] -> Bool
[]     `myIsPrefixOf`  list  = True
(l:ls) `myIsPrefixOf`  (x:xs)  = if l == x then ls `myIsPrefixOf` xs
                                 else False

and call the function like that:

[1,2] `myIsPrefixOf` [1]

i get an error that said there is no exhaustive patterns in the function.
i want to see if i understand why it is happening.
the function pass through the first pattern and get to the second one:

(l:ls) `myIsPrefixOf` (x:xs) = if l == x then ls `myIsPrefixOf` xs
                               else False

so:

[1,2] `myIsPrefixOf` [1]

and:
l == x.
they both 1, so i match again the second pattern:

(2:[]) `myIsPrefixOf` ([]:[])

now, l == 2, but x == [] and because that, the expression: l == x returns the no-exhaustive pattern...
is it because i'm trying to check for equality between a number and a list?
the equality parameter (==) should check only elements that are in the same type?
(i.e. : 'a' == 'b' or 1 == 3)

well, do i understand it all right? :-)
thanks a lot :-).

Answer 1

Your understanding is mostly correct, but you do seem to have some problems. When you have a list, say list, that you're matching with x:xs, then both list and xs are of list type, but x is of the element type of the list. So it is not possible for x to equal [] unless you have a list of lists, which these examples don't have.

So, in your second example, in the call

[1,2] `myIsPrefixOf` [1]

the recursive call after matching the 1s is

[2] `myIsPrefixOf` []

(that is, the right-hand side is not []:[], which would be the same as [[]], a one element list whose only element is the empty list) and you don't have a pattern that matches with the first parameter being non-empty and the second being empty.

Answer 2

This seems to be a common misunderstanding for people learning Haskell. The : construct is not list concatenation. Hence, x:xs doesn't match "a list of things named x followed by a list of things named xs". Instead, think of : as if it were named StartsAListThatContinues.

Similarly, The [] construct doesn't mean "I don't care" or "some list, whatever". Think of it as if it were named NoMore.

Now, imagine your original code was then:

myIsPrefixOf :: (Eq a) => [a] -> [a] -> Bool
NoMore                            `myIsPrefixOf`  NoMore                             = True
NoMore                            `myIsPrefixOf`  (x `StartsAListThatContinues` xs)  = True
list                              `myIsPrefixOf`  NoMore                             = False
(l `StartsAListThatContinues` ls) `myIsPrefixOf`  (x `StartsAListThatContinues` xs)  = if l == x then ls `myIsPrefixOf` xs

Finally, realize that a list can either be NoMore or a StartsAListThatContinues structure. One or the the other, and that's all it can be.

Under these conditions, perhaps it is clear how your code can be reduced (remembering that _ means "I don't care"):

myIsPrefixOf :: (Eq a) => [a] -> [a] -> Bool
NoMore                            `myIsPrefixOf`  _                                  = True
list                              `myIsPrefixOf`  NoMore                             = False
(l `StartsAListThatContinues` ls) `myIsPrefixOf`  (x `StartsAListThatContinues` xs)  = if l == x then ls `myIsPrefixOf` xs

And then

myIsPrefixOf :: (Eq a) => [a] -> [a] -> Bool
NoMore                            `myIsPrefixOf`  _                                  = True
_                                 `myIsPrefixOf`  NoMore                             = False
(l `StartsAListThatContinues` ls) `myIsPrefixOf`  (x `StartsAListThatContinues` xs)  = if l == x then ls `myIsPrefixOf` xs

Answer 3

Your understanding of the first problem is correct, but your understanding of the second problem is not.

To see why, step back from actual function a bit and look at lists. Lists have two constructors, [] and :. So a complete pattern match needs to cover both cases.

Your function has two list arguments, so you need to cover 2 * 2 == 4 cases. This will always be the case for a function that takes two list arguments; if you leave one combination out, you will get the "non-exhaustive patterns" error for some inputs. Those are the cases you have in your first version:

[] `f` [] = True
[] `f` (x:xs) = True
(l:ls) `f` [] = False
(l:ls) `f` (x:xs) = ...

When you avoid pattern matching on the two list constructors, you can collapse two cases into one. That's what you did in your first question:

[] `f` list = True
...

Here you are ignored the details of the second argument--it doesn't matter which list constructor it is. Collapsing it like this works as long as the answer for both cases is the same, which it is in this case.

---

For your second question, you want to drop the third case. The only way to avoid the "non-exhaustive patterns" error is to make the fourth case less specific:

(l:ls) `f` xlist = ...

But then you're stuck, because you can't get at the first element of xlist anymore, because you don't know that it's not empty. You could do head xlist, but that'll crash on empty lists. So actually you have to check for the empty list first:

(l:ls) `f` xlist = if null xlist then False 
                   else if l == head xlist then ls `myIsPrefixOf` tail xlist
                   else False

But that's so verbose that the original pattern match is better.

---

The specific way that you went wrong in your second question is in the manual execution of isPrefixOf [1,2] [1].

the function pass through the first pattern and get to the second one:

(l:ls) `myIsPrefixOf` (x:xs) = if l == x then ls `myIsPrefixOf` xs
                               else False

so:

[1,2] `myIsPrefixOf` [1]

and:

l == x.

Good so far.

they both 1, so i match again the second pattern:

Wait, hold on a minute to figure out all the values here. We already know that l==x==1. But also ls==[2] and xs==[].

Now when we recur, ls won't match the first pattern (it's not empty), but xs won't match the second pattern (it's empty, and (x:xs) requires a : object, not []). So the function crashes with 'non-exhaustive pattern'.