Unknown - haskell-notes

( True‘ And‘ True‘ And‘ False) ‘ Or‘ True

Как бы мы не шли от корня к листу сначала нам будут встречаться только операции Or, затем только

операции And, затем только Not.

КНФ замечательна тем, что её вычисление может пройти досрочно. КНФ можно представить так:

data Or’

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( Nota)

==>a

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

Not( Anda b) ==> Or

( Nota) ( Notb)

Not( Or

a b) ==> And( Nota) ( Notb)

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

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

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

Anda ( Orb c)

==> Or( Anda b) ( Anda c)

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

Anda b

== Andb 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 Endoa = Endo{ appEndo ::a ->a }

instance Monoid( Endoa) where

mempty = Endoid

Endof ‘mappend‘ Endog = Endo(f .g)

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

является функция композиции. Попробуйте переписать примеры из главы накопление чисел с помощью

этого типа.

• Реализуйте с помощью монады STкакой-нибудь алгоритм в императивном стиле. Например алгоритм

поиска корней уравнения методом деления пополам. Если функция f непрерывна и в двух точках a и b

( a < b ) значения функции имеют разные знаки, то это говорит о том, что где-то на отрезке [ a, b ] урав-

нение f ( x ) = 0 имеет решение. Мы можем найти его так. Посмотрим какой знак у значения функции в

середине отрезка. Если значение равно нулю, то нам повезло и мы нашли решение, если нет, то из двух

концов отрезка выбрем тот, у которого знак значения функции f отличается от знака значения в сере-

дине отрезка. Далее повторим эту процедуру на новом отрезке. И так пока мы не найдём корень или

отрезок не стянется в точку. Внутри функции выделите память под концы отрезка и последовательно

изменяйте их внутри типа ST.

Упражнения | 125

Глава 8

IO

Пока мы не написали ещё ни одной программы, которой можно было бы пользоваться вне интерпретато-

ра. Предполагается, что программа как-то взаимодействует с пользователем (ожидает ввода с клавиатуры)

и изменяет состояние компьютера (выводит сообщения на экран, записывает данные в файлы). Но пока что