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

Question

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

Answer 1

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

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 2

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

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

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

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

Answer 3

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

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

Answer 4

Нет, это не зацикливание. Если у вас есть образец соответствия, как это

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