Понимание соответствия шаблонов с оператором cons - PullRequest
Новая
       22

Понимание соответствия шаблонов с оператором cons

11 голосов
/ 17 мая 2010

В «Программировании F #» я наткнулся на сопоставление с шаблоном, как этот (немного упростил): 

let rec len list = 
  match list with
  | [] -> 0
  | [_] -> 1
  | head :: tail -> 1 + len tail;;

Практически я понимаю, что последний матч распознает заголовок и хвост списка. Концептуально я не понимаю, почему это работает. Насколько я понимаю, :: это оператор cons, который добавляет значение в заголовок списка, но мне не кажется, что он используется здесь как оператор. Должен ли я понимать это как «специальный синтаксис» для списков, где :: интерпретируется как оператор или «шаблон соответствия» в зависимости от контекста? Или эту же идею можно распространить на другие типы, кроме списков, с другими операторами?

Ответы [ 3 ]

13 голосов
/ 17 мая 2010

Это специальный синтаксис для списков. Таким образом, вы можете думать о типе list как о различаемом союзе: 

type list<'T> =         // '
    | Nil
    | Cons of 'T * list<'T>

за исключением того, что есть специальный синтаксис, который делает Nil быть [] и Cons(h,t) быть h::t. Тогда это просто нормальное сопоставление с образцом на дискриминированном объединении. Это помогает?

(возможно см. Также эту запись в блоге .)

10 голосов
/ 17 мая 2010

В дополнение к ответу Брайана, есть несколько моментов, на которые стоит обратить внимание. Синтаксис h::t может использоваться как оператор и как шаблон: 

let l = 1::2::[]                    // As an operator
match l with x::xs -> 1 | [] -> 0   // As a pattern

Это означает, что это немного особая конструкция, потому что другие операторы (например, +) не могут использоваться в качестве шаблонов (для разложения результата обратно на аргументы оператора) - очевидно, для + это было бы неоднозначно.

Также интересен шаблон [_], поскольку он является примером вложенного шаблона. Составляет:

  • _ - Подчеркнуть шаблон, который соответствует любому значению и не связывает никакие символы
  • [ <pattern> ] - Шаблон списка из одного элемента, который сопоставляет списки с одиночными элементами и сопоставляет элемент списка с вложенным <pattern>.

Вы также можете написать match 1::[] with | [x] -> x, который будет возвращать значение одного элемента (в данном случае 1).

2 голосов
/ 17 мая 2010

Используется в качестве средства форматирования или формально pattern, `список 'соответствует трем шаблонам:

[] означает, что список пуст

[_] означает, что список имеет один элемент, поскольку вам не важно, что это за элемент, поэтому просто поместите _ туда, вы также можете использовать [a].

head :: tail означает, что список состоит из двух частей: головы и хвоста.

Вы можете рассматривать сопоставление с образцом F # как мощную структуру if then else.

...