Как сопоставление с образцом выполняет незаметную работу в F#?
Я абсолютно плохо знаком с F# (и функциональное программирование в целом), но я вижу сопоставление с образцом, используемое везде в примере кода. Я задаюсь вопросом, например, как сопоставление с образцом на самом деле работает? Например, я воображаю это работающий то же для цикла на других языках и проверяющий на соответствия на каждом объекте в наборе. Это, вероятно, совсем не корректно, как это на самом деле выполняет незаметную работу?
4 ответа
Это зависит от того, какое сопоставление шаблонов вы имеете в виду - это довольно мощная конструкция, которую можно использовать самыми разными способами. Тем не менее, я попытаюсь объяснить, как работает сопоставление шаблонов в списках. Вы можете написать, например, такие шаблоны:
match l with
| [1; 2; 3] -> // specific list of 3 elements
| 1::rest -> // list starting with 1 followed by more elements
| x::xs -> // non-empty list with element 'x' followed by a list
| [] -> // empty list (no elements)
Список F# на самом деле является дискриминированным объединением, содержащим два случая - [] представляющий пустой список или x::xs, представляющий список с первым элементом x, за которым следуют некоторые другие элементы. На языке C# это можно представить следующим образом:
// Represents any list
abstract class List<T> { }
// Case '[]' representing an empty list
class EmptyList<T> : List<T> { }
// Case 'x::xs' representing list with element followed by other list
class ConsList<T> : List<T> {
public T Value { get; set; }
public List<T> Rest { get; set; }
}
Приведенные выше шаблоны будут скомпилированы в следующие (я использую псевдокод для упрощения):
if (l is ConsList) && (l.Value == 1) &&
(l.Rest is ConsList) && (l.Rest.Value == 2) &&
(l.Rest.Rest is ConsList) && (l.Rest.Rest.Value == 3) &&
(l.Rest.Rest.Rest is EmptyList) then
// specific list of 3 elements
else if (l is ConsList) && (l.Value == 1) then
var rest = l.Rest;
// list starting with 1 followed by more elements
else if (l is ConsList) then
var x = l.Value, xs = l.Rest;
// non-empty list with element 'x' followed by a list
else if (l is EmptyList) then
// empty list (no elements)
Как видите, здесь нет циклов. При обработке списков в F# для реализации циклов используется рекурсия, но сопоставление шаблонов используется для отдельных элементов (ConsList), которые вместе составляют весь список.
Шаблонное соответствие в списках - это частный случай дискриминированного объединения, который обсуждается в sepp2k. Существуют и другие конструкции, которые могут появиться при согласовании шаблонов, но по существу все они компилируются с помощью некоторого (сложного) оператора if.
Как на самом деле работает сопоставление по образцу? Так же, как цикл
for?
Он настолько далек от цикла for, насколько вы можете себе представить: вместо цикла соответствие шаблону компилируется в эффективный автомат. Существует два стиля автоматов, которые я называю "дерево решений" и "французский стиль". Каждый стиль предлагает различные преимущества: дерево решений проверяет минимальное количество значений, необходимых для принятия решения, но наивная реализация может потребовать экспоненциального пространства кода в худшем случае. Французский стиль предлагает другой компромисс между временем и пространством, с хорошими, но не оптимальными гарантиями для обоих вариантов.
Но абсолютно окончательной работой по этой проблеме является превосходная статья Люка Марангета "Compiling Pattern Matching to Good Decisions Trees" с семинара по ML 2008 года. Статья Люка в основном показывает, как получить лучшее из двух миров. Если вы хотите получить более доступное для любителя изложение, я смиренно рекомендую свое собственное предложение When Do Match-Compilation Heuristics Matter?
Написание компилятора паттерн-матчей - это просто и весело!
Нет, он не зацикливается. Если у вас есть совпадение шаблонов, как здесь
match x with
| Foo a b -> a + b
| Bar c -> c
это сводится к примерно такому псевдокоду:
if (x is a Foo)
let a = (first element of x) in
let b = (second element of x) in
a+b
else if (x is a Bar)
let c = (first element of x) in
c
Если Foo и Bar являются конструкторами алгебраического типа данных (т.е. типа, определенного как type FooBar = Foo int int | Bar int), то операции x is a Foo и x is a Bar являются простыми сравнениями. Если они определяются активным шаблоном, то операции определяются этим шаблоном.
Если вы скомпилируете свой код F # в .exe, посмотрите с помощью Reflector , и вы увидите, что C # "эквивалент" кода F #.
Я использовал этот метод, чтобы немного изучить примеры F #.