问题描述:

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:

with that:`[]`

`myIsPrefixOf`

(x:xs) = True

`[] `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 :-).

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'.

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
```

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 `1`

s 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.