• Откройте документацию к GHC. Пролистайте её. Проникнитесь уважением к разработчикам GHC. Най-
дите исходники GHC и почитайте их. Посмотрите на Haskell-код, написанный профессионалами. Вы-
берите функцию наугад и попытайтесь понять как она строит свой результат.
Упражнения | 179
• Откройте документацию вновь. Нас интересует глава Profiling. Найдите в разделе профилирование
кучи как выполняется retainer profiling. Это специальный тип профилирования направленный на по-
иск данных, которые удерживают в памяти другие данные (типичный сценарий для утечек памяти).
Разберитесь с этим типом профилирования (флаг hr).
• Постройте систему правил, которая выполняет слияние для списков List, определённых в примере для
прагмы RULES. Сравните показатели производительности с правилами и без (для этого скомпилируйте
дважды с флагом O и без) на тестовом выражении:
main = print $ sumL $
mapL (x -> x — 1000) $ mapL (+100) $ mapL (*2) $ genL 0 1e6
Функция sumL находит сумму элементов в списке, функция genL генерирует список чисел с единичным
шагом от первого аргумента до второго.
Подсказка: вам нужно воспользоваться такими свойствами (не забудьте о фазах компиляции)
mapL f (mapL g xs)
= …
foldrL cons nil (mapL f xs)
= …
• Откройте исходный код Prelude и присмотритесь к различным прагмам. Попытайтесь понять почему
они там используются.
180 | Глава 10: Реализация Haskell в GHC
Глава 11
Ленивые чудеса
В прошлой главе мы узнали, что такое ленивые вычисления. В этой главе мы посмотрим чем они хо-
роши. С ними можно делать невозможные вещи. Обращаться к ещё не вычисленным значениям, работать с
бесконечными данными.
Мы пишем программу, чтобы решить какую-нибудь сложную задачу. Часто так бывает, что сложная задача
оказывается сложной до тех пор пока её не удаётся разбить на отдельные независимые подзадачи. Мы решаем
задачи по-меньше, потом собираем из них решения, из этих решений собираем другие решения и вот уже
готова программа. Но мы решаем задачу не на листочке, нам необходимо объяснить её компьютеру. И тот
язык, на котором мы пишем программу, оказывает сильное влияние на то как мы будем решать задачу. Мы не
можем разбить программу на независимые подзадачи, если в том языке на котором мы собираемся объяснять
задачу компьютеру нет средств для того, чтобы собрать эти решения вместе.
Об этом говорит Джон Хьюз (John Huges) в статье “Why functional programming matters”. Он приводит та-
кую метафору. Если мы делаем стул и у нас нет хорошего клея. Единственное что нам остаётся это вырезать
из дерева стул целиком. Это невероятно трудная задача. Гораздо проще сделать отдельные части и потом
собрать вместе. Функциональные языки программирования предоставляют два новых вида “клея”. Это функ-
ции высшего порядка и ленивые вычисления. В статье можно найти много примеров. Некоторые из них мы
рассмотрим в этой главе.
С функциями высших порядков мы уже знакомы, они позволяют склеивать небольшие решения. С их
помощью мы можем параметризовать функцию другой функцией (поведением). Они дают нам возможность
выделять сложные закономерности и собирать их в функции. Ленивые вычисления же предназначены для
склеивания больших программ. Они синхронизируют выполнение подзадач, избавляя нас от необходимости
выполнять это вручную.
Эта идея разбиения программы на независимые части приводит нас к понятию модульности. Когда мы
решаем задачу мы пытаемся разложить её на простейшие составляющие. При этом часто оказывается, что
эти составляющие применимы не только для нашей задачи, но и для многих других. Мы получаем целый
букет решений, там где искали одно.
11.1 Численные методы
Рассмотрим несколько численных методов. Все эти методы построены на понятии сходимости. У нас есть
последовательность решений и она сходится к одному решению, но мы не знаем когда. Мы только знаем,
что промежуточные решения будут всё ближе и ближе к итоговому.
Поскольку у нас ленивый язык мы сначала построим все возможные решения, а затем выберем итоговое.
Так же как мы делали это в прошлой главе, когда искали корни уравнения методом неподвижной точки. Эти
примеры взяты из статьи “Why functional programming matters” Джона Хьюза.
Дифференцирование
Найдём производную функции в точке. Посмотрим на математическое определение производной:
f ( x + h) ? f ( x)
f ( x) = lim
h> 0
h
Производная это предел последовательности таких отношений, при h стремящемся к нулю. Если предел
сходится, то производная определена. Для того чтобы решить эту задачу мы начнём с небольшого значе-
ния h и будем постепенно уменьшать его, вычисляя промежуточные значения производной. Как только они
перестанут сильно изменяться мы будем считать, что мы нашли предел последовательности
Этот процесс напоминает то, что мы делали при поиске корня уравнения методом неподвижной точки.
Мы можем взять из того решения функцию определения сходимости последовательности:
| 181
converge :: (Ord a, Num a) => a -> [a] -> a
converge eps (a:b:xs)
| abs (a — b) <= eps
= a
| otherwise
= converge eps (b:xs)
Теперь осталось только создать последовательность значений производных. Напишем функцию, которая
вычисляет промежуточные решения:
easydiff :: Fractional a => (a -> a) -> a -> a -> a
easydiff f x h = (f (x + h) — f x) / h
Мы возьмём начальное значение шага и будем последовательно уменьшать его вдвое:
halves = iterate (/2)
Соберём все части вместе:
diff :: (Ord a, Fractional a) => a -> a -> (a -> a) -> a -> a
diff h0 eps f x = converge eps $ map (easydiff f x) $ iterate (/2) h0
where easydiff f x h = (f (x + h) — f x) / h
Сохраним эти определения в отдельном модуле и найдём производную какой-нибудь функции. Проте-
стируем решение на экспоненте. Известно, что производная экспоненты равна самой себе:
*Numeric> let exp’ = diff 1 1e-5 exp
*Numeric> let test x = abs $ exp x — exp’ x
*Numeric> test 2
1.4093421286887065e-5
*Numeric> test 5
1.767240203776055e-5
Интегрирование
Теперь давайте поинтегрируем функции одного аргумента. Интеграл это площадь кривой под графиком
функции. Если бы кривая была прямой, то мы могли бы вычислить интеграл по формуле трапеций:
easyintegrate :: Fractional a => (a -> a) -> a -> a -> a
easyintegrate f a b = (f a + f b) * (b — a) / 2
Но мы хотим интегрировать не только прямые линии. Мы представим, что функция является ломаной
прямой линией. Мы посчитаем интеграл на каждом из участков и сложим ответы. При этом чем ближе точки
друг к другу, тем точнее можно представить функцию в виде ломаной прямой линии, тем точнее будет
значение интеграла.
Проблема в том, что мы не знаем заранее насколько близки должны быть точки друг к другу. Это зависит
от функции, которую мы хотим проинтегрировать. Но мы можем построить последовательность решений.
На каждом шаге мы будем приближать функцию ломаной прямой, и на каждом шаге число изломов будет
расти вдвое. Как только решение перестанет меняться мы вернём ответ.
Построим последовательность решений:
integrate :: Fractional a => (a -> a) -> a -> a -> [a]
integrate f a b = easyintegrate f a b :
zipWith (+) (integrate a mid) (integrate mid b)
where mid = (a + b)/2
Первое решение является площадью под прямой, которая соединяет концы отрезка. Потом мы делим от-
