определения типов очень важен. Впрочем сносить кварталы в Haskell одно удовольствие, посольку стоит
нам изменить какой-нибудь тип, например убрать какой-нибудь тип или изменить имя, компилятор тут же
подскажет нам какие функции стали бессмысленными. Более коварные изменения связаны с добавлением
конструктора-альтернативы. Например нам вдруг не понравился тип Bool и мы решили сделать его более
человечным. Мы решили добавить ещё одно значение:
data Bool = True | False | IDonTKnow
Это может привести к неполному рассмотрению альтернатив в case-выражениях и сопоставлениях с об-
разцом в аргументах функции. Такие ошибки крайн неприятны, поскольку они происходят на этапе выпол-
нения программы, когда новое значение IDonTKnow дойдёт до case. В этом случае нам на выручку может
прийти функция свёртки, если мы вместе с типом изменим и функцию свёртки, это скажется на всех функ-
циях, которые были определены через неё. Чем больше таких функций, тем больше ошибок мы поймаем.
214 | Глава 13: Поиграем
13.3 Упражнения
• Измените диалог с пользователем. Сделайте так чтобы у игры было главное меню, в котором игрок
выбирает разные побочные функции, вроде выхода, начать новую игру, подсказка и игровое меню, в
котором игрок только передвигает фишки. Когда игрок собирает игру он попадает в главное меню.
• Добавьте в игру подсчёт статистики. Если игрок дошёл до победной позиции он узнаёт за сколько ходов
ему удалось решить задачу. Также ведётся история предыдущих попыток, по которой пользователь
может следить как изменяются его результаты.
• Подумайте можно ли выделить интерфейс игры в отдельный класс так, чтобы модуль Loop не зависел
от конкретной реализации игры. Чтобы можно было, опираясь на абстрактные методы, вроде show для
Game, или реакции на ход, вести диалог с пользователем. Попробуйте переписать игру пятнашки с
помощью такого класса.
• Попробуйте написать другую игру, например игру раскладывания пасьянса, крестики-нолики или
шашки, не меняя модуля Loop. Так чтобы вы сделали необходимые экземпляры для классов из преды-
дущего упражнения, а всё остальное поведение следовало из них.
Упражнения | 215
Глава 14
Лямбда-исчисление
В этой главе мы узнаем о лямбда-исчислении. Лямбда-исчисление описывает понятие алгоритма. Ещё
до появления компьютеров в 30-е годы двадцатого века математиков интересовал вопрос о возможности со-
здания алгоритма, который мог бы на основе заданных аксиом дать ответ о том верно или нет некоторое
логическое высказывание. Например у нас есть базовые утверждения и логические связки такие как “и”,
“или”, “для любого из”, “существует один из”, с помощью которых мы можем строить из базовых высказы-
ваний составные. Некоторые из них окажутся ложными, а другие истинными. Нам интересно узнать какие.
Но для решения этой задачи прежде всего необходимо было понять а что же такое алгоритм?
Ответ на этот вопрос дали Алонсо Чёрч (Alonso Church) и Алан Тьюринг (Alan Turing). Чёрч разработал
лямбда-исчисление, а Тьюринг теорию машин Тьюринга. Оказалось, что задача автоматического определе-
ния истинности формул в общем случае не имеет решения.
В основе лямбда-исчисление лежит понятие функции. Мы можем составлять сложные функции из про-
стейших, а также подставлять в функции аргументы, которые могут быть как константами так и другими
функциями. Как только мы составили выражение мы можем передать его вычислителю. Он подставляет ар-
гументы в функции и возвращает такое выражение, в котором невозможно далее проводить подстановки
аргументов. Этот процесс проведения подстановок считается вычислением алгоритма.
В рамках теории машин Тьюринга алгоритм описывается по-другому. Машина Тьюринга имеет внут-
реннее состояние, Состояние содержит некоторое значение, которое изменяется по ходу работы машины.
Машина живёт не сама по себе, она читает ленту символов. Лента символов – это большая цепочка букв.
На каждую букву машина реагирует серией действий. Она может изменить значение состояния, обновить
букву в ленте или перейти к следующему или предыдущему символу. Есть состояния, которые обозначают
конец работы, они называются терминальными. Как только машина дойдёт до терминального состояния мы
считаем, что вычисление алгоритма закончилось. После этого мы можем считать результат из состояний
машины.
Функциональные языки программирования основаны на лямбда-исчислении. Поэтому мы будем гово-
рить именно об этом описании алгоритма.
14.1 Лямбда исчисление без типов
Составление термов
Можно считать, что лямбда исчисление это такой маленький язык программирования. В нём есть множе-
ство символов, которые считаются переменными, они что-то обозначают и неделимы. В лямбда-исчислении
программный код называется термом. Для написания программного кода у нас есть всего три правила:
• Переменные x, y, z … являются термами.
• Если M и N – термы, то ( MN) – терм.
• Если x – переменная, а M – терм, то ( ?x. M) – терм
В формальном описании добавляют ещё одно правило, оно говорит о том, что других термов нет. Первое
правило, говорит о том, что у нас есть алфавит символов, который что-то обозначает, эти символы явля-