Or
a b
== Or
b a
• Когда вы закончите определение функции:
transform :: Log -> CNF
Напишите функцию, которая будет сравнивать вычисление исходного выражения напрямую и вычис-
ление через КНФ. Эта функция будет принимать исходное значение типа Log и будет возвращать два
числа, число операций необходимых для вычисления выражения:
evalCount :: Log -> (Int, Int)
evalCount a = (evalCountLog a, evalCountCNF a)
evalCountLog :: Log -> Int
evalCountLog a = ...
evalCountCNF :: Log -> Int
evalCountCNF a = ...
При написании этих функций воспользуйтесь функциями-накопителями.
• В модуле Data.Monoid определён специальный тип с помощью которого можно накапливать функции.
Только функции должны быть специального типа. Они должны принимать и возвращать значения од-
ного типа. Такие функции называют эндоморфизмами.
Посмотрим на их определение:
newtype Endo a = Endo { appEndo :: a -> a }
instance Monoid (Endo a) where
mempty = Endo id
Endo f ‘mappend‘ Endo g = Endo (f . g)
В качестве нейтрального элемента выступает функция тождества, а функцией объединения значений
является функция композиции. Попробуйте переписать примеры из главы накопление чисел с помощью
этого типа.
• Реализуйте с помощью монады ST какой-нибудь алгоритм в императивном стиле. Например алгоритм
поиска корней уравнения методом деления пополам. Если функция f непрерывна и в двух точках a и b
( a < b) значения функции имеют разные знаки, то это говорит о том, что где-то на отрезке [ a, b] урав-
нение f( x) = 0 имеет решение. Мы можем найти его так. Посмотрим какой знак у значения функции в
середине отрезка. Если значение равно нулю, то нам повезло и мы нашли решение, если нет, то из двух
концов отрезка выбрем тот, у которого знак значения функции f отличается от знака значения в сере-
дине отрезка. Далее повторим эту процедуру на новом отрезке. И так пока мы не найдём корень или
отрезок не стянется в точку. Внутри функции выделите память под концы отрезка и последовательно
изменяйте их внутри типа ST.
Упражнения | 125
Глава 8
IO
Пока мы не написали ещё ни одной программы, которой можно было бы пользоваться вне интерпретато-
ра. Предполагается, что программа как-то взаимодействует с пользователем (ожидает ввода с клавиатуры)
и изменяет состояние компьютера (выводит сообщения на экран, записывает данные в файлы). Но пока что
мы не знаем как взаимодействовать с окружающим миром.
Самое время узнать! Сначала мы посмотрим какие проблемы связаны с реализацией взаимодействия с
пользователем. Как эти проблемы решаются в Haskell. Потом мы научимся решать несколько типичных задач,
связанных с вводом/выводом.
8.1 Чистота и побочные эффекты
Когда мы определяем новые функции или константы мы лишь даём новые имена комбинациям значений.
В этом смысле у нас ничего не изменяется. По-другому это называется функциональной чистотой (referential