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

Ответ 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, за которым следуют некоторые другие элементы. В С# это может быть представлено следующим образом:

// 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.

Ответ 2

Как работает сопоставление шаблонов? То же, что и цикл for?

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

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

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

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

Ответ 4

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

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