Учебник по Haskell

• Набейте руку в профилировании, пусть это станет привычкой. Вы долго писали большую программу и

теперь вы можете узнать много подробностей из её жизни, что происходит с ней во время вычисления

кода. Вернитесь к прошлой главе и попрофилируйте разные примеры. В конце главы мы рассматрива-

ли пример с поиском корней, там мы создавали большой список промежуточных результатов и в нём

искали решение. Я говорил, что такие алгоритмы очень эффективны при ленивой стратегии вычис-

лений, но так ли это? Будьте критичны, не верьте на слово, ведь теперь у вас есть инструменты для

проверки моих туманных гипотез.

• Откройте документацию к 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 стремящемся к нулю. Если предел