2. Функции Haskell

Декларации функций

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

inc(x) = x + 1, x ∈ Z
соответствует такая декларация на языке Haskell (имена функций и их аргументов должны начинаться со строчной буквы): 
inc :: Int -> Int
inc x = x + 1

Здесь первая строка объявляет, что inc — это одноместная функция, отображающая множество целых чисел Int в него же, а вторая строка содержит определение этого отображения. Такая декларация аналогична декларации функций в императивных языках; ср. с определением той же функции на языке C: 

int inc(int x) {
  return x + 1;
}

Очень важно помнить, что символ = обозначает определение функции, а не операцию присваивания (ее в Haskell'е просто нет). В частности, строки

n :: Int
n = 1
определяют не переменную (их в Haskell'е тоже нет!), а нульместную функцию n, которая возвращает целое значение 1.

Отсюда вытекает два важных следствия:

1. Определенную один раз функцию переопределить в той же программе нельзя (как и в императивных языках). Иными словами, в языке Haskell отсутствуют побочные эффекты; для получения нового значения мы вынуждены всякий раз создавать новую функцию. (Строго говоря, вычисление функций все же может иметь один побочный эффект — зацикливание.)

2. Расположение деклараций функций в программе не имеет никакого значения. Вычисление значения функции производится только в тот момент, когда оно действительно потребовалось (такой порядок вычислений называется ленивым или отложенным). Например, мы можем безболезненно написать:

div0 :: Int
div0 = 1 / 0

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

Нестрогость функций

Определим функцию bot так:

bot = bot

Очевидно, что при вычислении функции bot произойдет зацикливание программы. Поскольку каждая функция в Haskell'е должна иметь значение, подобным функциям приписано абстрактное значение _|_, читается «дно» (bottom). Все функции, в процессе вычисления которых произошла фатальная ошибка, также возвращают значение _|_ (например, приведенная только что функция div0).

В функциональном программировании функция f называется строгой, если значение f bot равно _|_. Иными словами, строгая функция, примененная к зацикливающейся функции, также должна зациклиться. В большинстве языков программирования все функции являются строгими; Haskell в этом смысле является исключением.

Пусть функция const1 определена так:

const1 x = 1

Тогда const1 bot вернет значение 1. Здесь опять-таки срабатывает ленивая модель вычислений: поскольку значение const1 не зависит от значения ее аргумента, этот аргумент не вычисляется.

Коль скоро в Haskell'е зацикливание и возникновение фатальной ошибки семантически эквивалентны, нетрудно догадаться, что const1 div0 также вернет значение 1.

Каррированные функции

Из приведенного определения функции inc видно, что аргументы функций не заключаются в круглые скобки, в отличие от привычной математической нотации. Такая запись называется каррированной (curried, вот и обещанное упоминание фамилии Хаскелла Карри).

Все каррированные функции являются одноместными, т. е. функциями одного аргумента. При этом считается, что n-местная функция

y = f(x1, …, xn), x1 ∈ A1, …, xn ∈ An, y ∈ B
имеет тип A1 -> (A2 ->(… (An -> B) … )), а ее значение вычисляется как ( … ((f x1) x2) ... ) xn в каррированной записи.

В качестве примера приведем функцию, вычисляющую сумму двух целых чисел:

add :: Int -> Int -> Int
add x y = x + y

Строгая запись этой декларации согласно приведенному выше правилу должна была бы иметь такой вид:

add :: Int -> (Int -> Int)
(add x) y = x + y

Однако, мы можем опустить скобки в обеих строках благодаря принятому в языке Haskell правилу: описания типов имеют правую ассоциативность, а описания функций — левую ассоциативность.

Теперь мы можем с помощью функции add написать определение новой функции, эквивалентной функции inc:

inc' :: Int -> Int
inc' x = add 1 x
или еще короче: 
inc' = add 1

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

add (x, y) = x + y
но такая функция по-прежнему будет иметь только один аргумент — пару чисел (x, y), а ее типом будет (Int, Int) -> Int.

Haskell содержит две встроенные функции curry и uncurry, которые соответственно выполняют «каррирование» и «декаррирование» подобных функций, например:

add :: (Int, Int) -> Int
add (x, y) = x + y

inc x = curry add x 1

sub :: Int -> Int -> Int
sub x y = x - y

dec x = uncurry sub (x, 1)

(Писать определения типов для функций inc и dec здесь необязательно, поскольку они однозначно определяются компилятором по типам остальных функций).

λ-нотация

Алонзо Чёрч ввел систему обозначений, не требующую присваивать функциям имена, которая известна как λ-нотация. В этой системе λx[e] обозначает функцию от переменной x, которая каждому значению x сопоставляет значение выражения e. λ-нотация естественно распространяется и на функции с несколькими аргументами. Например, следующим функциям в обычных обозначениях

f(x) = x2 + 2x + 1
g(x, y) = x + y
h(x, y, z) = x2 + y2 + z2
соответствуют в λ-нотации такие функции:
λx[x2 + 2x + 1]
λyλx[x + y]
λzλyλx[x2 + y2 + z2]

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

inc x = x + 1
add x y = x + y
являются сокращенной записью внутреннего представления 
inc = \x   -> x + 1
add = \x y -> x + y

(Здесь обратная косая черта имитирует символ λ.)

Использование λ-нотации в большинстве случаев только затрудняет чтение программы. Однако, мы увидим далее, что у нее есть одно практическое применение: определение локальных анонимных функций внутри других функций.