Образцы и клозы

Необходимо отметить, что в нотации абстрактного функционального языка, который ис­пользовался до сих пор для написания примеров функций, можно было бы использовать та­кую конструкцию, как if-then-else. Например, при описании функции Append (см. при­мер 2.3), её тело можно было бы записать следующим образом:

Append (L₁, L₂) = if (L₁ == []) then L₂

else head (L₁) : Append (tail (L₁), L₂)

Однако данная запись чревата непониманием и трудным разбором. Поэтому даже в примере 2.3 была использована нотация, которая поддерживает так называемые "образцы".

Определение:

Образцом называется выражение, построенное с помощью операций конструирования дан­ных, которое используется для сопоставления с данными. Переменные обозначаются про­писными буквами, константы — строчными.

Примеры образцов:

5 — просто числовая константа
X — просто переменная
X : (Y : Z) — пара
[X, Y] — список

К образцам предъявляется одно требование, которое должно выполняться бес­пре­ко­с­лов­но, иначе сопоставление с образцами будет выполнено неверно. Требование это звучит сле­дующим образом: при сопоставлении образца с данными получение значений переменных дол­жно происходить единственным образом. Т.е., например, выражение (1 + X Þ 5) мож­но использовать как образец, т.к. получение значения переменной X происходит единственным об­разом (X = 4), а выражение (X + Y Þ 5) использовать в качестве образца нельзя, ибо получить значения переменных X и Y можно различным образом.

Кроме образцов в функциональном программировании вводится такое понятие, как "клоз" (от англ. "clause"). По определению клозы выглядят так:

def f p₁, ..., p_n = expr

где:

def и = — константы абстрактного языка
f — имя определяемой функции
p_i — последовательность образцов (при этом n ³ 0)
expr — выражение

Таким образом, определение функции в функциональном программировании есть прос­то последовательность клозов (возможно состоящая из одного элемента). Для того чтобы уп­ростить запись определений функций, далее слово def будет опускаться.

Пример 3.2. Образцы и клозы в функции Length.

Length ([]) = 0

Length (H:T) = 1 + Length (T)

Пусть вызов функции Length произведен с параметром [a, b, c]. В этом случае начнет свою работу механизм сопоставления с образцом. Последовательно перебираются все кло­зы и делаются попытки сопоставления. В данном случае удачное сопоставление будет толь­ко во втором клозе (т.к. список [a, b, c] не пуст).

Интерпретация вызова функции заключается в нахождении первого по порядку сверху вниз образца, успешно сопоставимого с фактическим параметром. Значения переменных об­разца, получаемые в результате сопоставления, подставляются в правую часть клоза (вы­ражение expr), вычисленное значение которой в данном контексте объявляется зна­че­ни­ем вызова функции.