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

Question

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

Я пытался найти простое объяснение, но я не нашел его.

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

Answer 1

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

Сравнить:

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

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

Обратите внимание, что " n ≥ 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

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

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

• «Алгебраический тип данных», в дополнение к первоклассным функциям, является важной идеей в статически типизированном функциональном языке, таком как 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

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

Answer 3

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

data SomeData = Foo Int Int
              | Bar String
              | Baz

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

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

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

Answer 4

В функциональном языке сопоставление с образцом включает проверку аргумента в отношении различных форм. Простой пример включает в себя рекурсивно определенные операции над списками. Я буду использовать 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

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

Answer 5

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

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

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