Понимание сопоставления с образцом требует объяснения трех частей:
- Алгебраические типы данных.
- Что такое сопоставление с образцом
- Почему это круто.
Алгебраические типы данных в двух словах
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()))));
Сопоставление узора в двух словах
Сопоставление с образцом - это разновидность типового тестирования. Допустим, мы создали объект стека, подобный приведенному выше, мы можем реализовать методы для просмотра и извлечения стека следующим образом:
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 = match s with ....)
Таким образом, помимо привязки структуры данных к переменным, мы также можем углубиться в нее. Допустим, у нас есть узел 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 #, используя шаблон посетителя , но это не так гибко, потому что вы не можете эффективно декомпозировать сложные структуры данных. Более того, если вы используете сопоставление с образцом, компилятор сообщит вам, если вы пропустили регистр . Насколько это круто?
Подумайте, как бы вы реализовали аналогичную функциональность в C # или языках без сопоставления с образцом. Подумайте, как бы вы сделали это без тестовых тестов и приведений во время выполнения. Это, конечно, не жесткий , просто громоздкий и громоздкий. И у вас нет проверки компилятором, чтобы убедиться, что вы рассмотрели каждый случай.
Таким образом, сопоставление с образцом помогает вам декомпозировать и перемещаться по структурам данных в очень удобном, компактном синтаксисе, это позволяет компилятору проверять логику вашего кода, по крайней мере, немного. Это действительно особенность убийцы.