Учебник по Haskell

a = Or’

[a]

data And’ a = And’ [a]

data Not’ a = Not’

a

data Lit

= True’ | False’

type CNF = Or’ (And’ (Not’ Lit))

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

нужно найти первый элемент, который вернёт True). Затем идёт список выражений, разделённых And

(опять же его не надо вычислять целиком, нам нужно найти первое выражение, которое вернёт False).

В самом конце стоят отрицания.

В нашем случае приведение к КНФ состоит из двух этапов:

– Сначала построим выражение, в котором все конструкторы Or и And стоят ближе к корню чем

конструктор Not. Для этого необходимо воспользоваться такими правилами:

-- удаление двойного отрицания

Not (Not a)

==> a

-- правила де Моргана

Not (And a b) ==> Or

(Not a) (Not b)

Not (Or

a b) ==> And (Not a) (Not b)

124 | Глава 7: Функторы и монады: примеры

– Делаем так чтобы все конструкторы Or были бы ближе к корню чем конструкторы And. Для этого

мы воспользуемся правилом дистрибутивности:

And a (Or b c)

==> Or (And a b) (And a c)

При этом мы будем учитывать коммутативность And и Or:

And a b

== And b a

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

transparency). Это свойство говорит о том, что мы свободно можем заменить в тексте программы любой

синоним на его определение и это никак не скажется на результате.

Функция является чистой, если её выход зависит только от её входов. В любой момент выполнения про-

граммы для одних и тех же входов будет один и тот же выход. Это свойство очень ценно. Оно облегчает

понимание поведения функции. Оно говорит о том, что функция может зависеть от других функций толь-

ко явно. Если мы видим, что другая функция используется в данной функции, то она используется в этой

функции. У нас нет таинственных глобальных переменных, в которые мы можем записывать данные из од-

ной функции и читать их с помощью другой. Мы вообще не можем ничего записывать и ничего читать. Мы