одновременно с вычислениями (не пользуясь функцией из модуля Debug.Trace). А в другом вариан-
те алгоритм останется прежним. Но теперь вместо решения найдите список первых приближений до
решения. А затем передайте его в отдельную функцию печати результатов.
В первом варианте алгоритм смешан с печатью. А во втором программа распадается на две части, часть
вычислений и часть вывода результатов на экран. Сравните два подхода.
• Напишите программу для угадывания чисел. Компьютер загадал число в заданном диапазоне и про-
сит вас угадать его. Если вы ошибаетесь он подсказывает: “холодно-горячо” или “больше-меньше”.
Программа принимает два аргумента, которые определяют диапазон возможных значений для неиз-
вестного числа.
• С помощью стандартных функций для генерации случайных чисел напишите программу, которая про-
водит состязание по игре в кости. Программа принимает аргументом суммарное число очков необходи-
мых для победы. Двое игроков бросают по очереди кости побеждает тот, кто первым наберёт заданную
сумму.
Сделайте так чтобы результаты выводились постепенно. С каждым нажатием на Enter вы подбрасы-
ваете кости (два шестигранных кубика). После каждого раунда программа выводит промежуточные
результаты.
• Напишите программу, которая принимает два аргумента: набор слов разделённых пробелами и файл.
А выводит она строки файла, в которых встречается данное слово.
Воспользуйтесь стандартными функциями из модуля Data.List
— разбиение строки на подстроки по переносам каретки
lines :: String -> [String]
— разбиение строки на подстроки по пробелам
words :: String -> [String]
— возвращает True только в том случае, если
— первый список полностью содержится во втором
isInfixOf :: Eq a => [a] -> [a] -> Bool
• Классы Functor и Applicative замкнуты относительно композиции. Это свойство говорит о том, что
композиция (аппликативных) функторов снова является (аппликативным) функтором. Докажите это!
Пусть дан тип, который описывает композицию двух типов:
newtype O f g a = O { unO :: f (g a) }
Определите экземпляры классов:
instance (Functor f, Functor g) => Functor (O f g) where …
instance (Applicative f, Applicative g) => Applicative (O f g) where …
Подсказка: если совсем не получается, ответ можно подсмотреть в библиотеке TypeCompose. Но пока мы
не знаем как устанавливать библиотеки и где они живут, всё-таки попытайтесь решить это упражнение
самостоятельно.
Упражнения | 141
Глава 9
Редукция выражений
В этой главе мы поговорим о том как вычисляются программы. В самом начале мы говорили о том, что
процесса вычисления значений нет. В том смысле, что у нас нет новых значений, у нас ничего не меняется,
мы лишь расшифровываем синонимы значений.
Вкратце вспомним то, что мы уже знаем о вычислениях. Сначала мы с помощью типов определяем мно-
жество всех возможных значений. Значения – это деревья в узлах которых записаны конструкторы, которые
мы определяем в типах. Так например мы можем определить тип:
data Nat = Zero | Succ Nat
Этим типом мы определяем множество допустимых значений. В данном случае это цепочки конструкто-
ров Succ, которые заканчиваются конструктором Zero:
Zero, Succ Zero, Succ (Succ Zero), …
Затем начинаем давать им новые имена, создавая константы (простые имена-синонимы)
zero
= Zero
one
= Succ zero
two
= Succ one
и функции (составные имена-синонимы):
foldNat :: a -> (a -> a) -> Nat -> a
foldNat z
s
Zero
= z
foldNat z
s
(Succ n)
= s (foldNat z s n)
add a = foldNat a
Succ
mul a = foldNat one (add a)
Затем мы передаём нашу программу на проверку компилятору. Мы просим у него проверить не создаём
ли мы случайно какие-нибудь бессмысленные выражения. Бессмысленные потому, что они пытаются создать
значение, которое не вписывается в наши типы. Например если мы где-нибудь попробуем составить выра-
жение:
add Zero mul
Компилятор напомнит нам о том, что мы пытаемся подставить функцию mul на место обычного значения
типа Nat. Тогда мы исправим выражение на:
add Zero two
Компилятор согласится. И передаст выражение вычислителю. И тут мы говорили, что вычислитель начи-
нает проводить расшифровку нашего описания. Он подставляет на место синонимов их определения, правые
части из уравнений. Этот процесс мы называли редукцией. Вычислитель видит два синонима и одно значение.
С какого синонима начать? С add или two?
142 | Глава 9: Редукция выражений
9.1 Стратегии вычислений
Этот вопрос приводит нас к понятию стратегии вычислений. Поскольку вычисляем мы только константы,
то наше выражение также можно представить в виде дерева. Только теперь у нас в узлах записаны не только
конструкторы, но и синонимы. Процесс редукции можно представить как процесс очистки такого дерева от
синонимов. Посмотрим на дерево нашего значения:
Оказывается у нас есть две возможности очистки синонимов.
Cнизу-вверх начинаем с листьев и убираем все синонимы в листьях дерева выражения. Как только в данном
узле и всех дочерних узлах остались одни конструкторы можно переходить на уровень выше. Так мы
поднимаемся выше и выше пока не дойдём до корня.
Cверху-вниз начинаем с корня, самого внешнего синонима и заменяем его на определение (с помощью урав-
нения на правую часть от знака равно), если на верху снова окажется синоним, мы опять заменим его
на определение и так пока на верху не появится конструктор, тогда мы спустимся в дочерние деревья
и будем повторять эту процедуру пока не дойдём до листьев дерева.
Посмотрим как каждая из стратегий будет редуцировать наше выражение. Начнём со стратегии от ли-
стьев к корню (снизу-вверх):
add Zero two
— видим два синонима add и two
— раскрываем two, ведь он находится ниже всех синонимов
=>
add Zero (Succ one)
— ниже появился ещё один синоним, раскроем и его
=>
add Zero (Succ (Succ zero))
— появился синоним zero раскроем его
=>
add Zero (Succ (Suсс Zero))
— все узлы ниже содержат конструкторы, поднимаемся вверх до синонима
— заменяем add на его правую часть
=>
foldNat Succ Zero (Succ (Succ Zero))
— самый нижний синоним foldNat, раскроем его
— сопоставление с образцом проходит во втором уравнении для foldNat
=>
Succ (foldNat Succ Zero (Succ Zero))
— снова раскрываем foldNat
=>
Succ (Succ (foldNat Zero Zero))
— снова раскрываем foldNat, но на этот раз нам подходит
— первое уравнение из определения foldNat
=>
Succ (Succ Zero)
— синонимов больше нет можно вернуть значение
— результат:
Succ (Succ Zero)
В этой стратегии для каждой функции мы сначала вычисляем до конца все аргументы, потом подставляем
расшифрованные значения в определение функции.
Теперь посмотрим на вычисление от корня к листьям (сверху-вниз):
add Zero two
— видим два синонима add и two, начинаем с того, что ближе всех к корню
=>
foldNat Succ Zero two
— теперь выше всех foldNat, раскроем его
Но для того чтобы раскрыть foldNat нам нужно узнать какое уравнение выбрать для этого нам нужно
понять какой конструктор находится в корне у второго аргумента, если это Zero, то мы выберем первое
уравнение, а если это Succ, то второе:
— в уравнении для foldNat видим декомпозицию по второму
— аргументу. Узнаем какой конструктор в корне у two
=>
foldNat Succ Zero (Succ one)
— Это Succ нам нужно второе уравнение:
