[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. Прошу прощения за то, что не во всех примерах кода стоят правильные кавычки. Это злую шутку сыграл либо хабрапарсер, либо средство подсветки кода.