.NET
April 2010 4

[F#] сопоставление образцов

Как и во многих других функциональных языках программирования, в F# поддерживается сопоставление образцов (pattern matching). Те, кто не знаком с ФП, могут представить себе его, как значительно улучшенный вариант switch.


Сразу к коду.

let rec factorial n =
  match n with
  | 0 | 1 -> 1
  | _ -> n * factorial(n - 1)

В этом коде определяется рекурсивная функция факториала. Как видим, весьма похоже на switch.

Пары, тройки и т.д.


let (+) vec multiplier =
  match vec with x, y ->
    x * multiplier, y * multiplier

Здесь элемент сопоставляется с парой значений (touple). Соответственно x принимает значение первого элемента пары, y — второго. Обратите внимание, что x и y — это новые описатели значений. Если ранее в программе было описано другое значение с именем x, то оно скроется вновь введённым до конца ветви. Чтобы не вводить нового описания, нужно использовать символ подчёркивания, как это было сделано в первом примере кода. Он может встречаться в образце сколько угодно раз и по сути является заполнителем места.

Списки



let rec sum = function
  | [] -> 0
  | head :: tail ->
    head + sum tail

Эта сокращённая запись эквивалентна

let rec sum value =
  match value with
  | [] -> 0
  | head :: tail ->
    head + sum tail

c той лишь разницей, что не вводится описатель с именем value.

Первый образец, [], соответствует пустому списку. Второй образец описывает список как две части, голову (первый элемент) и хвост (список изо всех остальных элементов). Имена на месте head и tail можно выбирать произвольно. Их область видимости — до конца ветви.

Можно отделять сразу несколько элементов из начала списка. el1 :: _ :: el3 :: tail

Несколько значений


При сопоставлении образцов можно не только разбивать пару на её составляющие, но и работать собственно с парой значений.

match host, port with
| «microsoft.com»80 -> Allow
| «warezzz.ws»80 -> Deny
| _ -> Forward

Сопоставление образцов может использоваться для определения типов (динамического).

match obj with
| :? String as str -> «String!»
| :? Int32 as integer -> «Int!»
| _ -> «What is it?»

Дополнительные условия


let rec hasNegative = function
  | [] -> false
  | head :: tail when head < 0 -> true
  | _ :: tail -> hasNegative tail

Хочу заметить, что сопоставление образцов происходит последовательно и поэтому если один из образцов подошёл, то последующие уже не сопоставляются. Благодаря этому не нужно писать when head >= 0 в последней ветке.

Active Patterns


Вероятно, эта возможность уникальна для F#. Нам даётся возможность определять собственные методы сопоставления. Рассмотрим на простом примере.

let (|Odd|Even|) = function
  | x when x % 2 = 0 -> Even
  | _ -> Odd

match 10 with
| Odd -> «o-O»
| Even -> ":)"

Метод сопоставления по сути является специальным образом определённой функцией. Имени у неё нет, но зато определяется сразу пара образцов — Odd и Even.

Помимо простого выбора можно организовать произвольный. Для этого используются частичные методы сопоставления.

let (|Prime|_|) value =
    let composite = List.exists (fun n -> value % n = 0) [2 .. int (Math.Sqrt(value))]
    if not composite then Some(value)
    else None

match n with
| Prime x -> sprintf «input %d is prime!» x
| x -> sprintf «this value is not special»

Это был довольно простой пример. Давайте рассмотрим более сложный.

type StackItem =
  | Int of Int32
  | String of String

let (|Add|_|) = function
  | OpCode.Add, Int(a) :: Int(b) :: stackRest ->
    Some(Int(a + b) :: stackRest)
  | OpCode.Add, String(a) :: String(b) :: stackRest ->
    Some(String(a + b) :: stackRest)
  | OpCode.Add, _ ->
    InvalidProgramException(«invalid add args») |> raise
  | _ -> None

let (|Sub|_|) = function
  | OpCode.Add, Int(a) :: Int(b) :: stackRest ->
    Some(Int(a - b) :: stackRest)
  | OpCode.Add, _ ->
    InvalidProgramException(«invalid sub args») |> raise
  | _ -> None

let compute opcode currentStack =
  match opcode, currentStack with
  | Add(newStack) | Sub(newStack) -> newStack
  | _ -> InvalidProgramException(sprintf «invalid opcode %A» opcode)


В частичном методе сопоставления используется специальный тип option (аналог Nullable), описанный прмерно так:
type Option 'a =
  | None
  | Some of 'a

Соответственно, чтобы указать, что объект не соответствует образцу, возвращается None. В данном случае мы также возвращаем результат применения образца как параметр Some и затем используем его (newStack).

Итоги


Как видим, сопоставление образцов — довольно полезная штука. Они — чуть ли не единственная причина, по которой я выбираю F# вместо C# (очень удобно использовать их при трансляции, см. пример кода со стековой машиной). Множество вариантов использования, компактность кода, расширяемость за счёт своих методов сопоставления — всё это делает сопоставление образцов в F# весьма и весьма привлекательным.

P.S. Прошу прощения за то, что не во всех примерах кода стоят правильные кавычки. Это злую шутку сыграл либо хабрапарсер, либо средство подсветки кода.
+6
2.6k 9
Comments 22
Top of the day