Сопоставление с образцом

В Ficus активно используется механизм сопоставления с образцом. Фактически, мы уже неоднократно сталкивались с его ограниченными формами в предыдущих разделах. Полноценная форма сопоставления реализуется с помощью оператора match, похожий на сильно расширенный оператор switch, присутствующий в классических языках вроде C/C++ и Java. Его синтаксис:

match expr {
| pattern1 => exprs1 // первая вертикальная черта после '{' необязательна
| pattern2 => exprs2
...
| patternN => exprsN
}

Таким образом, оператор берёт на входе выражение expr, вычисляет его и последовательно пытается сопоставить полученный результат с различными шаблонами (образцами). Каждый образец предваряется символом |. После нахождения совпадения выполняется соответствующая цепочка выражений (назовём её действием). Если ни один образец не подходит, выбрасывается исключение MatchError. Часто одинаковые действия соответствуют нескольким образцам, тогда их можно объединить. Проверка образцов осуществляется сверху вниз.

Образцы в Ficus можно представить как своего рода иерархические регулярные выражения, состоящие из двух компонентов (оба компонента необязательные):

первая часть описывает проверки, необходимые для успешного сопоставления значения с образцом.
вторая часть описывает захватываемые переменные, если сопоставление прошло успешно.

Формально образец может быть следующего вида:

Образец	Синтаксис	Захват переменных	Описание
Литерал	`число`, `строка`, `true`, `false`, `[]`	Нет	Используется простое сравнение значения или его части образцом.
Заглушка	`_`	Нет	Подходит любому значению и не захватывает никаких переменных. Чаще всего заглушка используется в случаях, когда нам не важна какая-то часть сложного образца или когда хотим задать последнюю позицию в операторе `match`, соответствующую случаю "остальное".
Идентификатор	`имя_переменной`	`имя_переменной`	Начинается с маленькой буквы или подчёркивания. Проверки отсутствуют, захваченное значение сохраняется под именем `имя_переменной` и доступно в действиях.
Кортеж	(`обр₁`, `обр₂`, …, `обр_N`)	Переменные из `обр_i`	Применяется к кортежам размера `N`, элементы которого проверяются соответствующими образцами. Совпадение считается успешным, если успешны все вложенные образцы.
Запись	{ поле₁=`обр₁`, …, поле_N=`обр_N` }	Переменные из `обр_i`	Значение должно быть записью, содержащим перечисленные поля. Не перечисленные поля записи не проверяются и не захватываются.
Список	`голова` :: `хвост`	`голова`, `хвост`	Значение должно быть списком. Если список пуст, сопоставление неудачно, иначе `голова` проверяется на соответствие головному образцу, а `хвост` – хвостовому образцу.
Захват	`образец as идентификатор`	`идентификатор`	Сначала проверяется `образец`, если сопоставление прошло успешно, захваченная часть сохраняется под именем `идентификатор`
Условие	`образец when условие`	переменные из `образец`	Сначала проверяется `образец`. Если сравнение успешно, проверяется `условие` (переменные могут захватываться). Соответствие признаётся удачным, если выполняется `условие`.
Вариант	`Имя(обр₁`, …, `обр_N)`	Переменные из `обр_i`	`Имя` начинается с заглавной буквы, количество образцов должно соответствовать количеству параметров конструктора варианта. В случае единственного параметра, если образец – `литерал`, `_` или `идентификатор`, круглые скобки можно опустить.
Альтернатива	`обр₁ \| обр₂ \|` … `\| обр_N`	нет	Сопоставление успешно, если сопоставление хотя бы одиного из образцов прошло успешно. Текущая версия компилятора Ficus не разрешает захват переменных в альтернативных образцах.

Примеры

Литерал, Заглушка

val a = ...
match a {
  | 5 => println("пять")
  | _ => println("не пять")
}

Идентификатор

val a = 1 :: 2 :: 3 :: []
  match a {
    | b => println(f"Список целиком: {b}")
  }

Кортеж

val a = (1, 2, 3)
  match a {
    | (b, c, _) => println(f"Части кортежа: {b}, {c}")
  }

Запись

type rect_t = { x: int; y: int; width: int; height: int }
val r = rect_t { x=10, y=5, width=30, height=60 }

match r {
  | { x = v } => println(f"Поле x записи равно {v}")
}

Список

// Первый образец сработает для 
// val a = 1 :: 2 :: 3 :: []
val a = 1 :: []
match a {
  | h :: h1 :: t => println(f"Голова: {h}, второй элемент {h1}, хвост: {t}")
  | h :: t => println(f"Голова: {h}, хвост: {t}") 
  | []     => println("Пустой список")
}

Захват

type pt = { x: int; y: int }

val l = pt {x = 10, y = 20 } :: []

match l {
    | {x = v} as h :: t => println(f"Значение поля x в голове списка: {v}, голова: {h}")
}

Условие

type rect_t = { x: int; y: int; width: int; height: int }
val r = rect_t { x=10, y=5, width=30, height=60 }

match r {
  | { x = v } when v > 15 => println(f"Поле x записи равно {v}")
  | _ => println("Условие не сработало")
}

Вариант, Альтернатива

type v = | A | B: int | C: (int, int)

val u = B(5)

match u {
  | A => println("Вариант A")
  | B v => println(f"Вариант B, значение {v}")
  | C(v, _) => println(f"Вариант C, значение {v}")
}

Приведённые описания позволяют составить представление о возможностях оператора match. Он способен заменить конструкцию switch в C и даёт гораздо больше возможностей. Посмотрим несколько примеров, демонстрирующих применение операторов для обработки списков:

fun list_rev_pm(l: 't list): 't list
{
    fun rev_(l_in: 't list, l_out: 't list): 't list =
        match l_in {
        | x :: rest => rev_(rest, (x :: l_out))
        | [] => l_out
        }
    rev_(l, [])
}

fun list_foldl_pm(f: ('t, 'res)->'res, res0: 'res, l: 't list): 'res =
    match l {
    | x :: rest => list_foldl_case(f, f(x, res0), rest)
    | _ => res0
    }

Предыдущая реализация для наглядности:

fun list_foldl(f: ('t, 'res)->'res, res0: 'res, l: 't list): 'res =
    if l.empty() {res0} else {list_foldl(f, f(l.hd(), res0), l.tl())}

Видим, что с помощью сопоставления с образцом и оператора :: удалось избавиться от методов empty(), hd() и tl()!

Все, что нам требуется для обработки списков, это сопоставление с образцом и оператор ::.

В самом деле, если вы посмотрите в исходный код модуля List, то увидите следующие (ну или очень похожие определения):

fun hd(l: 't list): 't =
    match l { | a :: rest => a | _ => throw NullListError }

fun tl(l: 't list): 't list =
    match l { | a :: rest => rest | _ => throw NullListError }

fun empty(l: 't list): bool =
    match l { | [] => true | _ => false }

И последнее замечание касается сортировки списков. Нам дан список элементов и функция поэлементного сравнения, нужно получить сортированный список.

Очевидно, что эта задача не решается с помощью хвостовой рекурсии, так как наилучший алгоритм сортировки работает за O(N log N). Как решить эту задачу?

Возможны два подхода:

элементы списка перемещаются в массив, после чего применяется стандартный императивный алгоритм сортировки. Это ровно то, что сделано в текущей реализации, поскольку такой метод самый эффективный.
чисто функциональная сортировка слиянием с временной сложностью O(N log N). Вот как это работает:
- используется вспомогательная функция merge, сливающая два упорядоченных списка в один. Это простая функция с хвостовой рекурсией.
- исходный список длиной N превращается в N отдельных списков, каждый из которых содержит один элемент.
- выполняется log⁡(N) проходов по этому списку списков. На каждом проходе последовательно берутся два соседних списка и сливаются в один. Итоговая сложность прохода – O(N), после каждого прохода длина списка уменьшается вдвое, а длина каждой последовательности удваивается. В конце мы получаем сортированный список.

Приведём полную реализацию алгоритма сортировки слиянием для списков:

/* 
  mergeSort: процедура сортировки методом слияния, работающая за O(N log N).
  Создаётся список списков, после чего эти списки сливаются до тех пор, 
  пока не останется один список.
*/
fun mergeSort(l: 't list, lt: ('t,'t)->bool): 't list =
    match l {
    | [] => []
    | l =>
        // Функция сливает два сортированых списка в один.
        // Используется сокращенный синтаксис функции для случая,
        // когда перебираются параметры функции сопоставляются 
        // с образцом.
        fun merge(_: 't list, _: 't list): 't list
        {
            | ((a :: at) as l, (b :: bt) as r) =>
                if lt(a, b) {
                  a :: merge(at, r)
                } else {
                  b :: merge(l, bt)
                }
            | (l, []) => l
            | ([], r) => r
        }

        // scan проходит по списку [:: l0, l1, l2, ... ] сортированых 
        // списков, сливает пары списков: l0 с l1, l2 с l3 и т.д.,
        // так что после этого прохода мы получаем (N+1)/2 списков вместо N.
        fun scan(_: 't list list): 't list list
        {
            | a :: b :: rest => merge(a, b) :: scan(rest)
            | l => l
        }

        // Повторятся сканирование, пока не останется ровно один список.
        fun loop(_: 't list list): 't list
        {
            | a :: [] => a
            | l => loop(scan(l))
        }

        // Начинаем со списка одноэлементных списков
        loop([:: for a <- l { [:: a] }])
    }


val a = 3 :: 4 :: 5 :: 6 :: 2 :: 1 :: []

@inline fun less(a: int, b: int): bool = a < b

println(mergeSort(a, less))

Замечания по реализации:

внутри действия оператора match можно разместить большое количество дополнительного кода. Здесь показано создание трёх вложенных функций, помогающих структурировать решение и облегчить чтение кода.
если тело функции сводится к оператору match, принимающему все параметры функции, то можно сократить написание и исключить явное использование ключевого слова match.

fun foo(args) {
  | <cases>
}

вместо

fun foo(args) =
match args {
  | <cases>
}

в функциональных программах, особенно при обработке символических данных, операторы match и рекурсия тесно связаны.
ранее рекомендовалось использовать хвостовую рекурсию. В данной реализации функции merge и scan не используют хвостовую рекурсию, так как аналогичные функции с хвостовой рекурсией порождают обращённые списки, а многократное обращение нежелательно (растет потребление ресурсов). Здесь предпочтение отдаётся избыточному созданию узлов списка взамен увеличения потребления пространства стека.

Образцы для захвата

Фактически оператор match – не единственное место, где применяется сопоставление с образцом. Ранее уже встречались ограниченные формы образцов, используемые в других частях кода. Ограниченность здесь подразумевает отсутствие проверок, иными словами, такие образцы служат только для захвата значений. Ниже приведены примеры:

// распаковываем кватернион с помощью сопоставления с образцом
val (x, y, z, _) = q

// ошибка: левая сторона определения значения должна быть образцом и не 
// содержать литералы
val (1., y, z, _) = q

// захватываем границы рамки и статус отслеживания объекта
val { box, tracked } = obj

// ошибка: левая сторона определения значения должна быть образцом и не 
// содержать литералы
val { label=("car", _), box, tracked=true } = obj

// распаковываем пиксели при переборе изображения
val gray = [for (r, g, b) <- img {
        sat_uint8(round(r*0.299 + g*0.587 + b*0.114))
}]

// перспективная проекция трёхмерной точки на плоскость
fun normalize((x, y, z): (float*3)) = (x/z, y/z)

Образцы для захвата можно использовать в разных местах:

формальные параметры функций
левая часть определения значений и переменных
переменные цикла.