Как сопоставление с образцом работает за кулисами в F #?

Question

Я совершенно новичок в F # (и функциональном программировании в целом), но я вижу, что сопоставление с образцом используется везде в примере кода. Мне интересно, например, как на самом деле работает сопоставление с образцом? Например, я представляю, что он работает так же, как цикл for на других языках и проверяет совпадения для каждого элемента в коллекции. Это, вероятно, далеко не правильно, как это на самом деле работает за кулисами?

Answer 1

Как на самом деле работает сопоставление с образцом? Так же, как for петля?

Это примерно так же далеко от цикла for, как вы можете себе представить: вместо цикла, шаблонное сопоставление компилируется в эффективный автомат . Есть два стиля автоматов, которые я называю «дерево решений» и «французский стиль». Каждый стиль предлагает свои преимущества: дерево решений проверяет минимальное число , необходимое для принятия решения, но в наивной реализации в худшем случае может потребоваться экспоненциальное пространство кода. Французский стиль предлагает другой компромисс между временем и пространством, с хорошими, но не оптимальными гарантиями для обоих.

Но абсолютно окончательной работой над этой проблемой является превосходная статья Люка Маранджета "Составление шаблонов, соответствующих деревьям хороших решений" из семинара ML ML 2008 года. Статья Люка в основном показывает, как получить лучшее из обоих миров. Если вы хотите лечение, которое может быть немного более доступным для любителя, я смиренно рекомендую мое собственное предложение Когда имеет значение Эвристика Матч-Компиляции?

Написание компилятора сопоставления с образцом легко и весело!

Answer 2

Это зависит от того, какой тип сопоставления вы имеете в виду - это довольно мощная конструкция, и ее можно использовать самыми разными способами. Однако я попытаюсь объяснить, как сопоставление с образцом работает со списками. Вы можете написать, например, эти шаблоны:

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.

Answer 3

Нет, это не цикл. Если у вас есть совпадение с шаблоном, как это

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 являются простыми сравнениями. Если они определены активным шаблоном , операции определяются этим шаблоном.

Answer 4

Если вы скомпилируете свой код F # в файл .exe, посмотрите на Reflector , и вы увидите, что такое эквивалент C # кода F #.

Я использовал этоспособ взглянуть на примеры F # совсем немного.