Совместимость шаблонов Haskell - что это?

Question

Что такое сопоставление шаблонов в Haskell и как оно связано с защищенными уравнениями?

Я пробовал искать простое объяснение, но я его не нашел.

EDIT: Кто-то помечен как домашнее задание. Я больше не хожу в школу, я просто изучаю Хаскелл, и я пытаюсь понять эту концепцию. Чистый из интереса.

Answer 1

В двух словах шаблоны похожи на определение кусочных функций в математике. Вы можете указать разные тела функций для разных аргументов, используя шаблоны. Когда вы вызываете функцию, соответствующий орган выбирается путем сравнения фактических аргументов с различными шаблонами аргументов. Прочтите A Gentle Introduction to Haskell для получения дополнительной информации.

Сравнить:

с эквивалентным Haskell:

fib 0 = 1 
fib 1 = 1 
fib n | n >= 2 
     = fib (n-1) + fib (n-2) 

Обратите внимание на "п ≥ 2" в функции кусочно становится охранник в версии Haskell, но другие два условия - это просто шаблоны. Шаблоны - это условия, в которых тестируются значения и структура, такие как x:xs, (x, y, z), или Just x. В кусочном определении условия, основанные на = или ∈ отношениях (в основном, условия, которые говорят что-то ", являются« чем-то другим), становятся образцами. Охранники допускают более общие условия. Мы могли бы переписать fib использовать охранников:

fib n | n == 0 = 1 
     | n == 1 = 1 
     | n >= 2 = fib (n-1) + fib (n-2) 

Answer 2

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

Вот определение функции для вычисления длины списка lst. В OCaml «список» is defined recursively as the empty list [] , or the structure h :: t , where h is an element of type a ( a being any type we want, such as an integer or even another list), t is a list (hence the recursive definition), and :: `- это оператор 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 

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

Answer 3

Соответствие шаблону, по крайней мере, в Haskell, глубоко связано с концепцией algebraic data types. При объявлении типа данных, как это:

data SomeData = Foo Int Int 
       | Bar String 
       | Baz 

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

соответствие шаблона является больше ничего, чем делать это в обратном --a шаблон будет «деконструкция» в SomeData значении в его составные части (на самом деле, я считаю, что сопоставление с образцом является только способа извлечения значений в Haskell).

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

Answer 4

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

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

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

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

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 

Answer 5

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

• «Устранение построить» означает «как потреблять или использовать значение»

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

идея алгебраических типов данных что вы определяете тип вещи, и вы говорите все способы, которыми вы можете это сделать. В качестве примера, давайте определим «Последовательность строки» в виде алгебраического типа данных, с тремя способами, чтобы сделать это:

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 

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