Пожалуйста, помогите мне понять соответствие шаблонов в haskell. Я немного запутался

Question

если у меня что-то подобное:

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

тогда x1,x2,x3 должно существовать, да?
они не могут быть [], но должны (опять же, ДОЛЖНЫ) иметь значение, да?
также, xs может быть [] или [a] или [a,a,a] (и т. д.), да?
(в [a] я имею в виду, что это список с одним номером, а [a,a,a] - это список из трех чисел).

также у меня есть функция, которая определяет 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

Если я удалю первый шаблон, функция будет выглядеть так:

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

и сейчас я напишу:

[] `myIsPrefixOf` [] 

я получу: False (должно быть True).
это потому, что первый шаблон имеет в своем правом элементе: (x:xs), и из-за этого x ДОЛЖЕН быть со значением, поэтому я прохожу через первый шаблон и перехожу ко второму шаблону:

list   `myIsPrefixOf`  []      = False

, которые совпадают, и возвращают False.
я прав?

если я прав, то разница в том, что если я напишу (x:xs), x ДОЛЖНО быть значением, а НЕ [].
с другой стороны, если я напишу list, он может совпадать с [] и [a] и [a,a,a] (и т. д.), и из-за этого list второго шаблона будет соответствовать первый [] в моем вводе, и поэтому я получу False?
(как и раньше, в [a] я имею в виду, что это список с одним номером, а [a,a,a] - это список из трех чисел).

также, чтобы исправить эту ситуацию, мне нужно заменить:

[]     <code>myIsPrefixOf</code>  (x:xs)  = True

с этим:

[]     `myIsPrefixOf`  list  = True

и теперь выражения:

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

будет совпадать против:

 [] `myIsPrefixOf` list = True

надеюсь, я прав в этих вещах, а теперь еще один вопрос:
здесь фиксированная функция с самого начала (после применения изменений)

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

Теперь, если я удалю второе сопоставление с образцом, функция будет выглядеть следующим образом:

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

и вызвать функцию следующим образом:

[1,2] `myIsPrefixOf` [1]

Я получаю сообщение об ошибке, согласно которому в функции нет исчерпывающих шаблонов.
я хочу посмотреть, понимаю ли я, почему это происходит.
функция проходит через первый шаблон и попадает во второй:

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

так:

[1,2] `myIsPrefixOf` [1]

и
l == x.
они оба 1, поэтому я снова сопоставляю второй шаблон:

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

сейчас l == 2, но x == [] и потому выражение: l == x возвращает неисчерпывающий шаблон ...
потому что я пытаюсь проверить равенство числа и списка?
параметр равенства (==) должен проверять только элементы одного типа?
(т.е.: 'a' == 'b' или 1 == 3)

ну, я все понимаю, хорошо? : -)
Большое спасибо: -).

Answer 1

Это, похоже, распространенное недоразумение для людей, изучающих Хаскель. Конструкция : не является конкатенацией списков. Следовательно, x:xs не соответствует «списку вещей с именем x, за которым следует список вещей с именем xs». Вместо этого думайте о :, как если бы он был назван StartsAListThatContinues.

Аналогично, конструкция [] не означает «мне все равно» или «какой-то список, что угодно». Думайте об этом, как будто это назвали NoMore.

Теперь представьте, что ваш оригинальный код был тогда:

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

Наконец, осознайте, что список может иметь структуру NoMore или StartsAListThatContinues. Один или другой, и это все, что может быть.

В этих условиях, возможно, понятно, как можно сократить ваш код (помня, что _ означает «мне все равно»):

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

А потом

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 2

Вы понимаете первую проблему правильно, но вы не понимаете вторую проблему.

Чтобы понять почему, немного отойдите от реальной функции и посмотрите на списки. Списки имеют два конструктора, [] и :. Таким образом, полное сопоставление с образцом должно охватывать оба случая.

Ваша функция имеет два аргумента списка, поэтому вам нужно охватить 2 * 2 == 4 случаев. Это будет всегда в случае функции, которая принимает два аргумента списка; если вы пропустите одну комбинацию, вы получите ошибку «неисчерпывающие шаблоны» для некоторых входных данных. Вот те случаи, которые вы имеете в своей первой версии:

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

Когда вы избегаете сопоставления с образцом в двух конструкторах списка, вы можете свернуть два случая в один. Вот что вы сделали в своем первом вопросе:

[] `f` list = True
...

Здесь вы игнорируете детали второго аргумента - не имеет значения, какой это конструктор списка. Подобное свертывание работает, пока ответ для обоих случаев одинаков, как и в этом случае.

---

По второму вопросу вы хотите отбросить третий случай. Единственный способ избежать ошибки «неисчерпывающих шаблонов» - сделать четвертый случай менее конкретным:

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

Но тогда вы застряли, потому что больше не можете получить первый элемент xlist, потому что не знаете, что он не пустой. Вы можете сделать head xlist, но это приведет к сбою в пустых списках. Так что на самом деле вы должны сначала проверить пустой список:

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

Но это настолько многословно, что оригинальное сопоставление с образцом лучше.

---

В вашем втором вопросе вы ошиблись, выполнив isPrefixOf [1,2] [1].

вручную.

функция проходит через первый шаблон и переходит ко второму:

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

так:

[1,2] `myIsPrefixOf` [1]

и

l == x.

Хорошо, пока.

они оба равны 1, поэтому я снова сопоставляю второй шаблон:

Подождите, подождите минуту, чтобы выяснить все значения здесь. Мы уже знаем, что l==x==1. Но также ls==[2] и xs==[].

Теперь, когда мы повторяем, ls не будет соответствовать первому шаблону (он не пустой), но xs не будет соответствовать второму шаблону (он пустой, а для (x:xs) требуется объект :, не []). Таким образом, функция падает с «неисчерпывающим шаблоном».

Answer 3

Ваше понимание в основном верно, но у вас, похоже, есть некоторые проблемы. Если у вас есть список, скажем, list, который соответствует x:xs, тогда и list, и xs относятся к типу списка, но x относится к типу элемента списка. Так что x не может равняться [], если у вас нет списка списков, которого нет в этих примерах.

Итак, во втором примере в вызове

[1,2] `myIsPrefixOf` [1]

рекурсивный вызов после сопоставления 1 s равен

[2] `myIsPrefixOf` []

(т. Е. Правая часть не является []:[], что будет аналогично [[]], списку из одного элемента, единственным элементом которого является пустой список), и у вас нет шаблона, соответствующего первый параметр не пустой, а второй пустой.