s'il vous plaît aidez-moi à comprendre le match de modèle en haskell. Je suis un peu confus

Question

si j'ai somthing comme ça:

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

alors x1,x2,x3 doit exister, oui?
ils ne peuvent pas être [], mais doivent (encore, DOIVENT) être avec une valeur, oui?
également, le xs peut être [] ou [a] ou [a,a,a] (etc '), oui?
(en [a] je veux dire que c'est une liste avec un nombre, et [a,a,a] est la liste de trois nombres).

aussi i ont une fonction qui définissent 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

si je retire le premier motif, que la fonction ressemblera à ceci:

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

et maintenant je vais écrire:

[] `myIsPrefixOf` []

Je vais avoir: Faux (ça devrait être vrai).
est parce que le premier motif a dans son élément latéral droit: (x:xs), et à cause de cela, x doit être avec une valeur, donc passer i à travers le premier motif, et obtenir au second motif:

list `myIsPrefixOf` []  = False

qui correspond, et retourne False.
ai-je raison? Si j'ai raison, alors la différence est que si j'écris (x:xs), DOIT être une valeur et NON [].
d'autre part, si j'écris list, il peut être match contre [] et [a] et [a,a,a] (etc), et à cause de cela, list du second motif, correspondra au premier [] dans mon entrée, et donc je vais avoir faux?
(comme précédemment, dans [a] je veux dire que c'est une liste avec un nombre, et [a,a,a] est la liste de trois nombres).

également, pour corriger cette situation, je dois remplacer:

[]  myIsPrefixOf (x:xs) = True 

avec qui:

[]  `myIsPrefixOf` list = True

et maintenant les expressions:

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

seront les deux agains match:

[] `myIsPrefixOf` list = True

J'espère avoir raison sur ces choses, et maintenant pour une autre question:
est ici la fonction fixe dès le départ (après application des modifications)

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

maintenant, si je retire le deuxième match de motif, que la fonction ressemblera à ceci:

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

et appel la fonction comme ça:

[1,2] `myIsPrefixOf` [1]

Je reçois une erreur disant qu'il n'y a pas de motifs exhaustifs dans la fonction.
Je veux voir si je comprends pourquoi cela se passe.
la fonction passer à travers le premier motif et le second arriver à une:

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

si:

[1,2] `myIsPrefixOf` [1]

et:
l == x.
ils ont tous deux 1, donc je correspondent à nouveau le second motif:

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

maintenant, l == 2, mais x == [] et parce que, l'expression: l == x renvoie la non-exhaustive modèle ...
est parce que j'essaie de vérifier l'égalité entre un nombre et une liste?
le paramètre d'égalité (==) devrait vérifier seulement les éléments qui sont dans le même type?
(à savoir: 'a' == 'b' ou 1 == 3) bien

, ce que je comprends tout droit? :-)
merci beaucoup :-).

Answer 1

Votre compréhension du premier problème est correct, mais votre compréhension du deuxième problème n'est pas.

Pour voir pourquoi, reculez un peu de la fonction actuelle et regardez les listes. Les listes ont deux constructeurs, [] et :. Une correspondance complète doit donc couvrir les deux cas.

Votre fonction possède deux arguments de liste, donc vous devez couvrir 2 * 2 == 4 cas. Ce sera toujours être le cas pour une fonction qui prend deux arguments de liste; Si vous laissez une combinaison, vous obtiendrez l'erreur "modèles non-exhaustifs" pour certaines entrées. Ce sont les cas que vous avez dans votre première version:

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

Lorsque vous évitez correspondance de motif sur les deux constructeurs de la liste, vous pouvez réduire les deux cas en un seul. C'est ce que vous avez fait dans votre première question:

[] `f` list = True 
... 

Ici vous ignoré les détails du second argument - il n'a pas d'importance constructeur liste est. L'effondrement comme ça fonctionne tant que la réponse pour les deux cas est la même, ce qui est dans ce cas.

---

Pour votre deuxième question, vous souhaitez supprimer le troisième cas. La seule façon d'éviter les « modèles non-exhaustive » erreur est de rendre le quatrième cas moins précis:

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

Mais alors vous êtes coincé, parce que vous ne pouvez pas obtenir au premier élément de xlist plus, parce que vous ne savez pas que ce n'est pas vide. Vous pouvez faire head xlist, mais cela va planter sur des listes vides. Donc, en fait, vous devez vérifier la liste vide d'abord:

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

Mais qui est si bavard que le match de modèle original est mieux.

---

La façon spécifique que vous êtes allé mal dans votre deuxième question dans l'exécution manuelle de isPrefixOf [1,2] [1].

la fonction passe à travers le premier motif et arriver à la seconde:

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

donc:

[1,2] `myIsPrefixOf` [1] 

et:

l == x. 

Bon jusqu'à présent .

ils ont tous deux 1, donc je correspondent à nouveau le second motif:

Attendez, attendez une minute pour comprendre toutes les valeurs ici. Nous savons déjà que l==x==1. Mais également ls==[2] et xs==[].

Maintenant, quand nous reportons, ls ne correspondra pas à la première configuration (ce n'est pas vide), mais xs ne correspond pas au deuxième motif (il est vide, et (x:xs) nécessite un objet :, non []). Ainsi, la fonction se bloque avec un «modèle non exhaustif».

Answer 2

Votre compréhension est la plupart du temps correcte, mais vous semblez avoir quelques problèmes. Quand vous avez une liste, disons list, que vous faites correspondre avec x:xs, alors les deux list et xs sont du type liste, mais x est du type de l'élément de la liste. Il n'est donc pas possible que x soit égal à [] sauf si vous avez une liste de listes, que ces exemples n'ont pas.

Ainsi, dans votre deuxième exemple, dans l'appel

[1,2] `myIsPrefixOf` [1] 

l'appel récursif après correspondant à la 1 s est

[2] `myIsPrefixOf` [] 

(qui est, le côté droit est pas []:[], qui serait le même que [[]], une liste d'un élément dont le seul élément est la liste vide) et vous n'avez pas un motif qui correspond au premier paramètre étant non vide et le second étant vide.

Answer 3

Cela semble être un malentendu commun pour les personnes apprenant Haskell. La construction : n'est pas une concaténation de liste. Par conséquent, x:xs ne correspond pas "une liste de choses nommées x suivie d'une liste de choses nommées xs". Au lieu de cela, pensez à : comme si elle s'appelait StartsAListThatContinues.

De même, la construction [] ne signifie pas «je m'en fous» ou «une liste, peu importe». Pensez-y comme si elle s'appelait NoMore.

Maintenant, imaginez que votre code d'origine était alors:

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 

Enfin, sachez qu'une liste peut être soit NoMore ou une structure StartsAListThatContinues. L'un ou l'autre, et c'est tout.

Dans ces conditions, peut-être il est clair que votre code peut être réduite (se souvenant que _ signifie "Je ne me soucie pas"):

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 

Et puis

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