Что такое «Match Matching» в функциональных языках?

Question

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

Может кто-нибудь объяснить разработчику Java/C++/JavaScript, что это значит?

Answer 1

Понимание шаблону требует объяснений трех частей:

1. Алгебраических типов данных.
2. Что соответствует шаблону
3. Почему это потрясающе.

Алгебраические типы данных в ореховой скорлупе

ML-как функциональные языки позволяют определять простые типы данных, называемые «непересекающиеся объединения» или «алгебраические типы данных». Эти структуры данных являются простыми контейнерами и могут быть рекурсивно определены. Например:

type 'a list = 
    | Nil 
    | Cons of 'a * 'a list 

определяет структуру данных, подобную стеку.Думайте об этом как эквивалент этой C#:

public abstract class List<T> 
{ 
    public class Nil : List<T> { } 
    public class Cons : List<T> 
    { 
     public readonly T Item1; 
     public readonly List<T> Item2; 
     public Cons(T item1, List<T> item2) 
     { 
      this.Item1 = item1; 
      this.Item2 = item2; 
     } 
    } 
} 

Таким образом, идентификаторы Cons и Nil определяют простой простой класс, где of x * y * z * ... определяет конструктор и некоторые типы данных. Параметры конструктора не обозначены, они идентифицируются по положению и типу данных.

создаются экземпляры вашего a list класса как таковые:

let x = Cons(1, Cons(2, Cons(3, Cons(4, Nil)))) 

Что такое же, как:

Stack<int> x = new Cons(1, new Cons(2, new Cons(3, new Cons(4, new Nil())))); 

сопоставление с образцом в миниатюре

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

let peek s = 
    match s with 
    | Cons(hd, tl) -> hd 
    | Nil -> failwith "Empty stack" 

let pop s = 
    match s with 
    | Cons(hd, tl) -> tl 
    | Nil -> failwith "Empty stack" 

методы являются эквивалентом (хотя и не реализован как таковой) к следующему C#:

public static T Peek<T>(Stack<T> s) 
{ 
    if (s is Stack<T>.Cons) 
    { 
     T hd = ((Stack<T>.Cons)s).Item1; 
     Stack<T> tl = ((Stack<T>.Cons)s).Item2; 
     return hd; 
    } 
    else if (s is Stack<T>.Nil) 
     throw new Exception("Empty stack"); 
    else 
     throw new MatchFailureException(); 
} 

public static Stack<T> Pop<T>(Stack<T> s) 
{ 
    if (s is Stack<T>.Cons) 
    { 
     T hd = ((Stack<T>.Cons)s).Item1; 
     Stack<T> tl = ((Stack<T>.Cons)s).Item2; 
     return tl; 
    } 
    else if (s is Stack<T>.Nil) 
     throw new Exception("Empty stack"); 
    else 
     throw new MatchFailureException(); 
} 

(почти всегда, ML языки реализовать шаблон без времени выполнения типовых тестов или слепков, так что C# коды несколько обманчивы. Давай деталь реализации отмахнуться с некоторыми ручными махнув пожалуйста :))

разложения структуры данных в скорлупе

Хорошо, давайте вернемся к методу пряток:

let peek s = 
    match s with 
    | Cons(hd, tl) -> hd 
    | Nil -> failwith "Empty stack" 

Уловка понимание, что идентификаторы hd и tl являются переменными (errm ... так как они «неизменяемы, они не являются« переменными », а« значениями »;)). Если s имеет тип Cons, то мы собираемся вытащить его значения из конструктора и привязать их к переменным с именем hd и tl.

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

type 'a tree = 
    | Node of 'a tree * 'a * 'a tree 
    | Nil 

Мы можем определить некоторые tree rotations следующим образом: (. let rotateRight = function конструктор синтаксисом для let rotateRight s = match s with ...)

let rotateLeft = function 
    | Node(a, p, Node(b, q, c)) -> Node(Node(a, p, b), q, c) 
    | x -> x 

let rotateRight = function 
    | Node(Node(a, p, b), q, c) -> Node(a, p, Node(b, q, c)) 
    | x -> x 

Таким образом, в Помимо привязки структуры данных к переменным, мы также можем развернуть ее. Допустим, у нас есть узел let x = Node(Nil, 1, Nil). Если мы позвоним rotateLeft x, мы протестируем x против первого шаблона, который не соответствует, потому что правый ребенок имеет тип Nil вместо Node. Он перейдет к следующему шаблону, x -> x, который будет соответствовать любому входу и вернуть его без изменений.

Для сравнения, мы бы написать методы выше в C#, как:

public abstract class Tree<T> 
{ 
    public abstract U Match<U>(Func<U> nilFunc, Func<Tree<T>, T, Tree<T>, U> nodeFunc); 

    public class Nil : Tree<T> 
    { 
     public override U Match<U>(Func<U> nilFunc, Func<Tree<T>, T, Tree<T>, U> nodeFunc) 
     { 
      return nilFunc(); 
     } 
    } 

    public class Node : Tree<T> 
    { 
     readonly Tree<T> Left; 
     readonly T Value; 
     readonly Tree<T> Right; 

     public Node(Tree<T> left, T value, Tree<T> right) 
     { 
      this.Left = left; 
      this.Value = value; 
      this.Right = right; 
     } 

     public override U Match<U>(Func<U> nilFunc, Func<Tree<T>, T, Tree<T>, U> nodeFunc) 
     { 
      return nodeFunc(Left, Value, Right); 
     } 
    } 

    public static Tree<T> RotateLeft(Tree<T> t) 
    { 
     return t.Match(
      () => t, 
      (l, x, r) => r.Match(
       () => t, 
       (rl, rx, rr) => new Node(new Node(l, x, rl), rx, rr)))); 
    } 

    public static Tree<T> RotateRight(Tree<T> t) 
    { 
     return t.Match(
      () => t, 
      (l, x, r) => l.Match(
       () => t, 
       (ll, lx, lr) => new Node(ll, lx, new Node(lr, x, r)))); 
    } 
} 

Для серьезно.

соответствие шаблона является удивительным

Вы можете реализовать что-то подобное к шаблону в C# с использованием visitor pattern, но не столь гибким, потому что вы не можете эффективно разлагать сложные структуры данных. Более того, если вы используете сопоставление с образцом, компилятор скажет вам, если вы упустили случай. Как это здорово?

Подумайте, как реализовать аналогичную функциональность на C# или языках без соответствия шаблону. Подумайте о том, как вы это сделаете без тестовых тестов и бросков во время выполнения. Его, конечно, не твердый, просто громоздкий и громоздкий. И у вас нет проверки компилятора, чтобы убедиться, что вы охватили все случаи.

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

Answer 2

Вам следует начать с Wikipedia page, который дает довольно хорошее объяснение. Затем прочитайте соответствующую главу Haskell wikibook.

Это хорошее определение из приведенного выше wikibook:

Так соответствующий шаблон является способ присвоения имен к вещам (или связывания эти имена для этих вещей), и возможно разрушение выражений в подвыражения в то же время (как это было со списком в определении карты ).

Answer 3

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

Это не только функция функционального языка, но и для разных языков.

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

например.

последний ([LastItem], LastItem).

последний ([Head | Tail], LastItem): - last (Tail, LastItem).

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

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

Если в списке есть как голова, так и хвост, интерпретатор выбирает вторую версию и рекурсирует, пока в списке не останется только один элемент.

Answer 4

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

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

Prelude> let is = [1,2,3] 
Prelude> head is + is !! 2 
4 

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

addFirstAndThird is = 
    let first = head is 
     third = is !! 3 
    in first + third 

Это извлечение значений из структуры данных - это то, что соответствует шаблону.Вы в основном «зеркало» структура чего-то, что дает переменные для связывания для интересных мест:

addFirstAndThird [first,_,third] = first + third 

При вызове этой функции с [1,2,3] в качестве аргумента, [1,2,3 ] будет унифицирован [сначала, _, третий], привязанный сначала к 1, третья-3 и отбрасывая 2 (_ - это место для вещей, которые вам не нужны).

Теперь, если вы только хотели, чтобы соответствовать списки с 2 в качестве второго элемента, вы можете сделать это следующим образом:

addFirstAndThird [first,2,third] = first + third 

Это будет работать только для списков с 2 в качестве второго элемента и бросить исключение в противном случае, поскольку определение для addFirstAndThird не задано для несоответствующих списков.

До сих пор мы использовали сопоставление образцов только для привязки деструктурирования. Выше этого, вы можете дать несколько определений одного и ту же функцию, где используются первое определение соответствия, таким образом, сопоставление с образцом немного напоминает «распределительное заявление на stereoids»:

addFirstAndThird [first,2,third] = first + third 
addFirstAndThird _ = 0 

addFirstAndThird счастливо добавить первый и третий элемент списка с 2 в качестве второго элемента, а в противном случае «проваливаться» и «вернуться» 0. Эта функция «переключения типа» не может быть использован только в определениях функций, например:

Prelude> case [1,3,3] of [a,2,c] -> a+c; _ -> 0 
0 
Prelude> case [1,2,3] of [a,2,c] -> a+c; _ -> 0 
4 

Далее , он не ограничивается списками, но может использоваться и с другими типами, например, для сопоставления конструкторам Just и Nothing из Может типа для того, чтобы «Unwrap» значение:

Prelude> case (Just 1) of (Just x) -> succ x; Nothing -> 0 
2 
Prelude> case Nothing of (Just x) -> succ x; Nothing -> 0 
0 

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

Answer 5

Это означает, что вместо того, чтобы писать

double f(int x, int y) { 
    if (y == 0) { 
    if (x == 0) 
     return NaN; 
    else if (x > 0) 
     return Infinity; 
    else 
     return -Infinity; 
    } else 
    return (double)x/y; 
} 

Вы можете написать

f(0, 0) = NaN; 
f(x, 0) | x > 0 = Infinity; 
     | else = -Infinity; 
f(x, y) = (double)x/y; 

---

Эй, C++ поддерживает шаблону тоже.

static const int PositiveInfinity = -1; 
static const int NegativeInfinity = -2; 
static const int NaN = -3; 

template <int x, int y> struct Divide { 
    enum { value = x/y }; 
}; 
template <bool x_gt_0> struct aux { enum { value = PositiveInfinity }; }; 
template <> struct aux<false> { enum { value = NegativeInfinity }; }; 
template <int x> struct Divide<x, 0> { 
    enum { value = aux<(x>0)>::value }; 
}; 
template <> struct Divide<0, 0> { 
    enum { value = NaN }; 
}; 

#include <cstdio> 

int main() { 
    printf("%d %d %d %d\n", Divide<7,2>::value, Divide<1,0>::value, Divide<0,0>::value, Divide<-1,0>::value); 
    return 0; 
}; 

Answer 6

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

Длинного ответ: соответствия шаблона является формой отправки на основе “ ” формы стоимости, что это дано. На функциональном языке типы данных, которые вы определяете, обычно называются дискриминированными союзами или алгебраическими типами данных. Например, что такое (связанный) список? Связанный список List вещей определенного типа a является либо пустым списком Nil, либо каким-либо элементом типа aCons ed на List a (список a).В Haskell (функциональный язык я знаком с), мы пишем эту

data List a = Nil 
      | Cons a (List a) 

Все дискриминационные союзы определяются следующим образом: один типа имеет фиксированное количество различных способов для его создания; создатели, такие как Nil и Cons здесь, называются конструкторами. Это означает, что значение типа List a могло быть создано с двумя разными конструкторами —, оно могло иметь две разные формы. Предположим, мы хотим написать функцию head, чтобы получить первый элемент списка. В Haskell, мы должны написать это как

-- `head` is a function from a `List a` to an `a`. 
head :: List a -> a 
-- An empty list has no first item, so we raise an error. 
head Nil  = error "empty list" 
-- If we are given a `Cons`, we only want the first part; that's the list's head. 
head (Cons h _) = h 

Поскольку List a значения могут быть двух различных типов, нам нужно обрабатывать каждый из них по отдельности; это соответствие шаблонов. В head x, если x соответствует рисунку Nil, тогда мы запускаем первый случай; если он соответствует шаблону Cons h _, мы запускаем второй.

Краткое объяснение: Я думаю, что одним из лучших способов думать об этом поведении является изменение того, как вы думаете о знаке равенства. В фигурных скобках, в общем, = обозначает назначение: a = b означает “ a в b. ” Во многих функциональных языках, однако, = означает утверждение о равенстве: let Cons a (Cons b Nil) = frob xутверждает, что вещь слева, Cons a (Cons b Nil), эквивалентна предмету справа, frob x; кроме того, все переменные, используемые слева, становятся видимыми. Это также то, что происходит с аргументами функции: мы утверждаем, что первый аргумент выглядит как Nil, и если это не так, мы продолжаем проверять.

Answer 7

Соответствие шаблону позволяет сопоставить значение (или объект) с некоторыми шаблонами, чтобы выбрать ветвь кода. С точки зрения C++ это может показаться немного похожим на инструкцию switch. В функциональных языках сопоставление образцов может использоваться для сопоставления по стандартным примитивным значениям, таким как целые числа. Однако он более полезен для составленных типов.

Во-первых, давайте демонстрировать соответствие модели на примитивные значения (с использованием расширенных псевдо-C++ switch):

switch(num) { 
    case 1: 
    // runs this when num == 1 
    case n when n > 10: 
    // runs this when num > 10 
    case _: 
    // runs this for all other cases (underscore means 'match all') 
} 

The scond использование сделок с функциональными типами данных, такие как кортежи (которые позволяют хранить несколько объектов в одном значении) и дискриминационные союзы, которые позволяют создавать тип, который может содержать один из нескольких вариантов. Это звучит немного как enum, за исключением того, что каждая метка также может нести некоторые значения. В синтаксисе псевдо-C++:

enum Shape { 
    Rectangle of { int left, int top, int width, int height } 
    Circle of { int x, int y, int radius } 
} 

Значение типа Shape теперь может содержать либо Rectangle со всеми координатами или Circle с центром и радиусом. Поиск по шаблону позволяет писать функции для работы с Shape типа:

switch(shape) { 
    case Rectangle(l, t, w, h): 
    // declares variables l, t, w, h and assigns properties 
    // of the rectangle value to the new variables 
    case Circle(x, y, r): 
    // this branch is run for circles (properties are assigned to variables) 
} 

Наконец, вы можете также использовать вложенные шаблоны, которые сочетают обе особенности.Например, вы можете использовать Circle(0, 0, radius) для соответствия всем формам, имеющим центр в точке [0, 0], и иметь любой радиус (значение радиуса будет присвоено новой переменной radius).

Это может показаться немного незнакомым с точки зрения C++, но я надеюсь, что мой псевдо-C++ упростит объяснение. Функциональное программирование основано на совершенно разных понятиях, поэтому оно имеет смысл в функциональном языке!

Answer 8

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

Шаблоны просто идут дальше и могут разрушить аргументы, переданные еще дальше. Он также может потенциально использовать защитные устройства для фактического соответствия на основе значения аргумента. Чтобы продемонстрировать, я буду притворяться, что JavaScript имеет соответствие шаблону.

function foo(a,b,c){} //no pattern matching, just a list of arguments 

function foo2([a],{prop1:d,prop2:e}, 35){} //invented pattern matching in JavaScript 

В foo2, он ожидает, что массив, он распадается вторым аргументом, ожидая объект с двумя опорами (prop1, prop2) и присваивает значения этих свойств к переменному г и д, а затем ожидает, что третий аргумент будет равен 35.

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

fibo(0) -> 0 ; 
fibo(1) -> 1 ; 
fibo(N) when N > 0 -> fibo(N-1) + fibo(N-2) . 

Размытие ваши глаза немного, и вы можете себе представить это в JavaScript. Что-то вроде этого, может быть:

function fibo(0){return 0;} 
function fibo(1){return 1;} 
function fibo(N) when N > 0 {return fibo(N-1) + fibo(N-2);} 

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

Помимо перегрузки функций, как показано здесь, этот же принцип можно применять и в других местах, таких как case case или destructuring assingments. JavaScript even has this in 1.7.

Answer 9

Вот очень короткий пример, который показывает шаблон, соответствующий полезность:

Допустим, вы хотите отсортировать вверх элемент в списке:

["Venice","Paris","New York","Amsterdam"] 

к (я сортируется до «Нью-Йорк «)

["Venice","New York","Paris","Amsterdam"] 

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

function up(city, cities){ 
    for(var i = 0; i < cities.length; i++){ 
     if(cities[i] === city && i > 0){ 
      var prev = cities[i-1]; 
      cities[i-1] = city; 
      cities[i] = prev; 
     } 
    } 
    return cities; 
} 

В функциональном языке вы бы вместо того, чтобы писать:

let up list value = 
    match list with 
     | [] -> [] 
     | previous::current::tail when current = value -> current::previous::tail 
     | current::tail -> current::(up tail value) 

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

Я написал более подробное сообщение в блоге об этом here.