Что такое 'Сопоставление с образцом' на функциональных языках?
Я читаю о функциональном программировании, и я заметил, что Сопоставление с образцом упоминается во многих статьях как одна из базовых функций функциональных языков.
Может кто-то объяснять для разработчика Java/C ++/JavaScript что это означает?
8 ответов
Для понимания сопоставления с образцом необходимо пояснить три части:
- Алгебраические типы данных.
- Что такое сопоставление с образцом
- Почему это круто.
Вкратце об алгебраических типах данных
Функциональные языки, подобные 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 определяют простой простой класс, где x * y * z *. .. определяет конструктор и некоторые типы данных. Параметры конструктора не имеют имени, они идентифицируются по положению и типу данных.
Вы создаете экземпляры своего класса списка как такового:
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()))));
В двух словах о сопоставлении с образцом
Сопоставление с образцом - это разновидность проверки типов. Итак, допустим, мы создали объект стека, подобный приведенному выше, мы можем реализовать методы для просмотра и извлечения стека следующим образом:
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 - это переменные (эээ ... поскольку они неизменяемы, они на самом деле не «переменные», а «значения»;)). Если s имеет тип Cons , то мы собираемся извлечь его значения из конструктора и привязать их к переменным с именами hd и tl .
Сопоставление с образцом полезно, потому что оно позволяет нам разложить структуру данных по ее форме вместо ее содержимого . Итак, представьте, что мы определяем двоичное дерево следующим образом:
type 'a tree =
| Node of 'a tree * 'a * 'a tree
| Nil
Мы можем определить некоторые вращения дерева следующим образом:
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 rotateRight = function является синтаксическим сахаром для let rotateRight s = сопоставить s с ... .)
Таким образом, помимо привязки структуры данных к переменным, мы также можем углубиться в нее. Допустим, у нас есть узел , пусть x = Узел (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 #, используя шаблон посетитель , но это не так гибко, потому что вы не можете эффективно разложить сложные структуры данных. Более того, если вы используете сопоставление с образцом, компилятор сообщит вам, если вы пропустили регистр . Насколько это круто?
Подумайте, как бы вы реализовали аналогичные функции на C # или языках без сопоставления с образцом. Подумайте, как бы вы это сделали без тестов-тесты и приведения во время выполнения. Это конечно не сложно , просто громоздко и громоздко. И у вас нет проверки компилятора, чтобы убедиться, что вы охватили все случаи.
Таким образом, сопоставление с образцом помогает вам разлагать структуры данных и перемещаться по ним с помощью очень удобного компактного синтаксиса, оно позволяет компилятору хотя бы немного проверить логику вашего кода. Это действительно убойная функция.
Это означает, что вместо записи
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;
};
Многим людям легче освоить новую концепцию приведены примеры, поэтому приступим:
Допустим, у вас есть список из трех целых чисел, и вы хотите добавить первый и третий элементы. Без сопоставления с образцом вы могли бы сделать это следующим образом (примеры в 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 дается для несовпадающих списков.
До сих пор мы использовали сопоставление с образцом только для деструктуризации привязки.Кроме того, вы можете дать несколько определений одной и той же функции, где используется первое определение соответствия, таким образом, сопоставление с образцом немного похоже на «оператор переключения на стереоиде»:
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 типа Maybe, чтобы «развернуть» значение:
Prelude> case (Just 1) of (Just x) -> succ x; Nothing -> 0
2
Prelude> case Nothing of (Just x) -> succ x; Nothing -> 0
0
Конечно,это были просто игрушечные примеры, и я даже не пытался дать формальное или исчерпывающее объяснение, но их должно быть достаточно, чтобы понять основную концепцию.
Сопоставление с образцом - это когда интерпретатор вашего языка выбирает конкретную функцию на основе структуры и содержания аргументов, которые вы ему передаете.
Это не только функциональная языковая функция, она доступна для многих языков.
Впервые я столкнулся с этой идеей, когда выучил пролог, где это действительно центральное место в языке.
например.
последний ([LastItem], LastItem).
последний ([Head | Tail], LastItem): - последний (Tail, LastItem).
Приведенный выше код дает последний элемент списка. Входной аргумент является первым, а результат - вторым.
Если в списке только один элемент, интерпретатор выберет первую версию, а второй аргумент будет установлен равным первому, т.е. результату будет присвоено значение.
Если в списке есть и голова, и хвост, интерпретатор выберет вторую версию и выполнит рекурсию до тех пор, пока в списке не останется только один элемент.
Вам следует начать со страницы Википедии , которая дает довольно хорошее объяснение. Затем прочтите соответствующую главу викибука Haskell .
Это хорошее определение из приведенной выше вики-книги:
Таким образом, сопоставление с образцом - это способ присвоения имен вещам (или привязки этих имен к этим вещам) и {{ 1}} возможно разделение выражений на подвыражения одновременно (как мы сделали со списком в определении карты ).
Сопоставление с образцом позволяет сопоставить значение (или объект) с некоторыми образцами, чтобы выбрать ветвь кода. С точки зрения C ++ это может звучать немного похоже на оператор switch . В функциональных языках сопоставление с образцом может использоваться для сопоставления стандартных примитивных значений, таких как целые числа. Однако это более полезно для составных типов.
Во-первых, давайте продемонстрируем сопоставление с образцом для примитивных значений (используя расширенный псевдо-C ++ переключатель ):
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')
}
Второе использование касается функциональных типов данных, таких как кортежи (которые позволяют вы можете хранить несколько объектов в одном значении) и размеченные объединения , которые позволяют создавать тип, который может содержать один из нескольких вариантов. Это немного похоже на 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] и любым радиусом (значение радиуса будет присвоено в новую переменную радиус ).
Это может показаться немного непривычным с точки зрения C ++, но я надеюсь, что мой псевдо-C ++ прояснит объяснение.Функциональное программирование основано на совершенно иных концепциях, поэтому лучше понимать его на функциональном языке!
Сопоставление с образцом похоже на перегруженные методы на стероидах. Самый простой случай будет примерно таким же, как и в 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 он ожидает, что a будет массивом, он разделяет второй аргумент, ожидая объект с двумя props (prop1, prop2), и присваивает значения этих свойств переменным d и e, а затем ожидает третьего аргумент должен быть 35.
В отличие от JavaScript, языки с сопоставлением с образцом обычно позволяют использовать несколько функций с одним и тем же именем, но с разными образцами. В этом смысле это похоже на перегрузку метода. Я приведу пример на erlang:
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 или деструктурирующих утверждениях. JavaScript есть даже в версии 1.7 .
Краткий ответ: Сопоставление с образцом возникает из-за того, что функциональные языки обрабатывают знак равенства как утверждение эквивалентности вместо присвоения.
Длинный ответ: Сопоставление с образцом - это форма отправки, основанная на «форме» заданного значения. На функциональном языке типы данных, которые вы определяете, обычно называются дискриминируемыми объединениями или алгебраическими типами данных. Например, что такое (связанный) список? Связанный список Список вещей некоторого типа a - это либо пустой список Nil , либо некоторый элемент типа 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 , и если это не так, мы продолжаем проверку.