Lazy crazy

Поговорим о Хаскеле... Первая вещь, которая отличает_от и поражает воображение, это до невозможности ленивые вычисления. Хаскел никогда ничего не вычисляет, пока оно не понадобится.

Например, можно сказать [1..], и Хаскел бросится печатать бесконечный список чисел. Но если попросить take 5 [1..], то ответом будет [1,2,3,4,5], то есть будут вычислены только те элементы, которые нужны. Не впечатляет? Идём дальше.

Классическая задача — числа Фибоначчи. Классическая же рекурсивная реализация, понятная без каких-либо тайных знаний_о:

fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

Говорим fib 10, получаем 55, всё честно.

А если хочется список чисел? Первая мысль императивного программиста: какой длины объявлять массив? Вот в этом месте требуется смена парадигмы. В Хаскеле нет проблем (почти) работать с бесконечными списками.

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

Говорим take 11 fibs, получаем [0,1,1,2,3,5,8,13,21,34,55]. Говорим fibs!!10, получаем 55.

Тут уже требуется пара пояснений. Функция tail возвращает весь список, кроме головы: tail [1,2,3] даёт [2,3]. Функция zipWith «сшивает» два списка с помощью функции-параметра, например zipWith (+) [10,20,30] [1,2,3] даст [11,22,33], а zipWith (-) [10,20,30] [1,2,3] даст [9,18,27].

То есть вот что происходит. Сначала в fibs нам известны первые два элемента. А затем происходит рекурсивное (потенциально бесконечное!) сложение списка самого с собой, сдвинутым на одну позицию влево, как-то так:

[0,1,…
+
[1,…
=
[1,…

[0,1,1,…
+
[1,1,…
=
[1,2,…

[0,1,1,2,…
+
[1,1,2,…
=
[1,2,3,…

Ну и так далее, алгоритм O(n) — понятно, не самый быстрый, но для упражнения сойдёт. Суть же в том, что благодаря ленивости вычислений нам не надо заботиться о максимальном размере списка: сколько понадобится, столько и будет, но не больше! По-моему, красиво.