Подсказка: вам нужно воспользоваться такими свойствами (не забудьте о фазах компиляции)
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 стремящемся к нулю. Если предел