Полезные хитрости языка

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

Ленивые вычисления и строгие функции

Haskell – крайне ленивый язык. Идея ленивости, на самом деле, очень проста: никакое выражение не будет вычисляться, пока его результат не понадобится. Более того, мы видели, что вычисление рекурсивных функций, если его производить руками, превращается в последовательное раскрытие одних выражений во вторые, вторых в третьи, и так далее. Часто бывает так, что уже частично раскрытого выражения достаточно для того, чтобы функция могла вернуть результат – в таком случае, выражение так и не будет вычислено до конца.

Классический пример – функция const:

const :: a -> b -> a

const x _ = x

Обратили внимание, что функция не использует свой второй параметр вообще? Работает она так:

const "hello" 1 → "hello"

const "hello" False → "hello"

const "hello" (1/0) → "hello"

Обратили внимание на последний вызов? В качестве второго параметра мы передаем ошибочное, нетерминальное выражение – а функция все равно возвращает правильный результат. Если бы мы работали с обычными неленивыми, строгими функциями, то передавая в функцию нетерминальное выражение, мы бы получали в ответ тоже нетерминальное выражение.

Немного занудства, позволите? Если обозначать ошибочное, нетерминальное (вычисление которого никогда не закончится) выражение как bot, то строгие функции – это те, которые всегда сами сразу виснут или выкидывают ошибку, если им такое значение передать. То есть для строгих функций, f(...,bot,...) → bot. Для нестрогих, соответственно, это может быть так, а может быть и не так.

Haskell – язык ленивый. Он не станет вычислять значение выражения (1/0) в надежде, что оно никогда не понадобится – и в данном случае его лень оказывается оправданной. А функции Haskell, соответственно – нестрогими. Конечно, если бы нетерминальное значение передавалось в качестве первого параметра – мы получили бы ошибку:

const (1/0) "hello" → Program error: {primDivDouble 1.0 0.0}

Однако и в этом случае ошибки можно избежать – достаточно просто не требовать выводить значение функции const на экран, и вообще, не требовать использовать его как-либо:

length [const (1/0) "hello"] → 1

В данном случае, функции length не требуется вычислять значение функции const. От функции length только требуют выяснить, сколько значений находится в переданном ей списке – а это значение одно: const (1/0) "hello", вне зависимости от того, вернет эта функция одно значение, список значений или что-либо еще. А значит, функция length не будет вычислять результат этого выражения.

Бесконечные списки

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

Помните арифметические последовательности? Выражение [1..] означало бесконечный список натуральных чисел, но что это за зверь, и откуда он взялся – было совершенно не понятно. А вот посмотрите на функцию repeat:

repeat :: a -> [a]

repeat x = x : repeat x

Вот что будет, если попробовать вычислить ее значение и вывести на экран:

repeat 1 →

1 : repeat 1 →

1 : (1 : repeat 1) →

1 : (1 : (1 : repeat 1)) → ...

В общем, вы поняли – функция никогда не завершится. И вы будете смотреть на появляющиеся на экране единички, которые никогда не кончатся. Но ведь не обязательно выводить результат этой функции на экран? Можно спросить у нее, например, первый элемент, или первые несколько элементов:

head (repeat 1) → 1

take 5 (repeat 1) → [1,1,1,1,1]

Вот, например, полезная функция: replicate, дублирующая заданное значение заданное количество раз. Как можно ее реализовать?

replicate :: Int -> a -> [a]

replicate 0 _ = []

replicate n x = x : replicate (n-1) x

А можно и воспользоваться функцией repeat:

replicate :: Int -> a -> [a]

replicate n x = take n (repeat x)

А как получить тот самый список натуральных чисел?

naturals = naturalsFrom 1

naturalsFrom n = n : naturalsFrom (n+1)

Большая часть списочных функций, которые мы с вами писали, будет работать не только с обычными, но и с бесконечными списками. Но некоторые, разумеется, не будут – такие как length и last – и вполне понятно, почему.

Еще точнее: какие-то функции, если им передать бесконечный список, вернут конечный результат (например, head). Другие, если им передать бесконечный список, вернут тоже бесконечный список, с которым вполне можно работать, если не вычислять его целиком (например, drop). А третьи, если им передать бесконечный список, вообще ничего не вернут и зависнут (например, last). Обдумайте разницу.