Сопоставление с образцом Haskell - что это?

Pattern matching is, по крайней мере, в Haskell, глубоко связано с концепцией алгебраических типов данных . Когда вы объявляете тип данных следующим образом:

data SomeData = Foo Int Int
              | Bar String
              | Baz

...он определяет Foo, Bar, и Baz как конструкторы- не путать с "конструкторами" в ООП - что строит значение SomeData из других значений.

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

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

В функциональном языке сопоставление с образцом включает проверку аргумента на соответствие различным формам. Простой пример включает рекурсивно определенные операции со списками. Я буду использовать OCaml для объяснения сопоставления с образцом, поскольку это мой предпочтительный функциональный язык, но концепции одинаковы в F # и Haskell, AFAIK.

Вот определение функции для вычисления длины списка lst . В OCaml список рекурсивно определяется как пустой список [] или структура h :: t , где h - это элемент типа a ( a - любой желаемый тип, например целое число или даже другой список), t - список (отсюда рекурсивное определение) и :: `- оператор cons, который создает новый список из элемента и списка.

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

let rec len lst =
  match lst with
    [] -> 0
  | h :: t -> 1 + len t

rec - это модификатор, который сообщает OCaml, что функция будет вызывать себя рекурсивно. Не беспокойтесь об этой части. Оператор match - это то, на чем мы сосредоточены.OCaml проверит lst по двум шаблонам - пустой список или h :: t - и вернет другое значение в зависимости от этого. Поскольку мы знаем, что каждый список будет соответствовать одному из этих шаблонов, мы можем быть уверены, что наша функция вернется безопасно.

Обратите внимание, что хотя эти два шаблона обрабатывают все списки, вы не ограничены ими. Шаблон вроде h1 :: h2 :: t (соответствует всем спискам длиной 2 или более) также допустим.

Конечно, использование шаблонов не ограничивается рекурсивно определенными структурами данных или рекурсивными функциями. Вот (надуманная) функция, которая сообщает вам, является ли число 1 или 2:

let is_one_or_two num =
  match num with
    1 -> true
  | 2 -> true
  | _ -> false

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

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

В F# вы можете использовать оператор cons :: для добавления элемента в начало списка типа so:

let a = 1 :: [2;3]
//val a : int list = [1; 2; 3]

Аналогично вы можете использовать тот же оператор для разбиения списка типа so:

let a = [1;2;3];;
match a with
    | [a;b] -> printfn "List contains 2 elements" //will match a list with 2 elements
    | a::tail -> printfn "Head is %d" a //will match a list with 2 or more elements
    | [] -> printfn "List is empty" //will match an empty list

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

• "Конструкция устранения" означает "как потреблять или использовать значение"

• "Алгебраический тип данных", в дополнение к первоклассным функциям, является большой идеей в статически типизированном функциональном языке, таком как Clean, F#, Haskell или ML

Идея алгебраических типов данных заключается в том, что вы определяете тип вещи, и вы говорите все способы, которыми вы можете сделать эту вещь. В качестве примера, давайте определим "Sequence of String" как алгебраический тип данных, с тремя способами его сделать:

data StringSeq = Empty                    -- the empty sequence
               | Cat StringSeq StringSeq  -- two sequences in succession
               | Single String            -- a sequence holding a single element

Теперь с этим определением есть много чего не так, но в качестве примера это интересно, потому что оно обеспечивает константное конкатенирование последовательностей произвольной длины. (Есть и другие способы добиться этого.) Декларация вводит Empty, Cat и Single, которые являются всеми существующими способами создания последовательностей. (Это делает каждую из них введением - способом создания вещей.)

• Вы можете создать пустую последовательность без каких-либо других значений.
• Чтобы сделать последовательность с Cat, вам понадобятся две другие последовательности.
• Для создания последовательности с Single вам нужен элемент (в данном случае строка)

Вот вам и кульминационная строка: конструкция устранения, подгонка по шаблону, дает вам возможность внимательно изучить последовательность и задать ей вопрос из какого конструктора вы были сделаны?. Так как вы должны быть готовы к любому ответу, вы предоставляете по крайней мере одну альтернативу для каждого конструктора. Вот функция длины:

slen :: StringSeq -> Int
slen s = case s of Empty -> 0
                   Cat s s' -> slen s + slen s'
                   Single _ -> 1

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

slen Empty = 0
slen (Cat s s') = slen s + slen s'
slen (Single _) = 1

С этим синтаксическим сахарчиком вычисление путем сравнения по шаблону во многом похоже на определение по уравнениям. (Комитет Хаскелла сделал это специально.) И как вы можете видеть в других ответах, можно специализироваться либо на уравнении, либо на альтернативе в выражении в падеже , накладывая на него пощечину. Я не могу придумать правдоподобного защитника для примера последовательности, а примеров в других ответах много, поэтому оставлю его там.