Unknown - haskell-notes

([( Sleep, Level10),( Work, Level0),( Work, Level1),( Work, Level0),

( Sleep, Level0)],( Sleep, Level0))

Конечные автоматы | 109

Первое значение в списке является стартовым состоянием, которое мы задали. После этого колонки вклю-

чаются и мы видим, что уровень громкости переключился на ноль. Затем мы увеличиваем громкость, сбав-

ляем её и выключаем. Попытка изменить громкость выключенных колонок не проходит. Это видно по по-

следнему элементу списка и итоговому состоянию колонок, которое находится во втором элементе пары.

Предположим, что колонки работают с самого начала, тогда первым действием мы выключаем их. По-

смотрим, что случится дальше:

*FSM>runState res ( Work, Level10)

([( Work, Level10),( Sleep, Level0),( Sleep, Level0),( Sleep, Level0),

( Work, Level0)],( Work, Level1))

Дальше мы пытаемся изменить громкость но у нас ничего не выходит.

7.3 Отложенное вычисление выражений

В этом примере мы будем выполнять арифметические операции на целых числах. Мы будем их скла-

дывать, вычитать и умножать. Но вместо того, чтобы сразу вычислять выражения мы будем составлять их

описание. Мы будем кодировать операции конструкторами.

data Exp

= Var String

| Lit Int

| Neg Exp

| Add Exp Exp

| Mul Exp Exp

deriving( Show, Eq)

У нас есть тип Exp, который может быть либо переменной Varс данным строчным именем, либо целочис-

ленной константой Lit, либо одной из трёх операций: вычитанием ( Neg), сложением ( Add) или умножением

( Mul).

Такие типы называют абстрактными синтаксическими деревьями (abstract syntax tree, AST). Они содержат

описание выражений. Теперь вместо того чтобы сразу проводить вычисления мы будем собирать выражения

в значении типа Exp. Сделаем экземпляр для Num:

instance Num Exp where

negate

= Neg

( +)

= Add

( *)

= Mul

fromInteger = Lit .fromInteger

abs

=undefined

signum

=undefined

Также определим вспомогательные функции для обозначения переменных:

var :: String -> Exp

var = Var

n :: Int -> Exp

n =var .show

Функция var составляет переменную с данным именем, а функция n составляет переменную, у которой

имя является целым числом. Сохраним эти определения в модуле Exp. Теперь у нас всё готово для составле-

ния выражений:

*Exp>n 1

Var”1”

*Exp>n 1 +2

Add( Var”1”) ( Lit2)

*Exp>3 *(n 1 +2)

Mul( Lit3) ( Add( Var”1”) ( Lit2))

*Exp> -n 2 *3 *(n 1 +2)

Neg( Mul( Mul( Var”2”) ( Lit3)) ( Add( Var”1”) ( Lit2)))

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

Теперь давайте создадим функцию для вычисления таких выражений. Она будет принимать выражение

и возвращать целое число.

eval :: Exp -> Int

eval ( Litn)

=n

eval ( Negn)

=negate $eval n

eval ( Adda b)

=eval a +eval b

eval ( Mula b)

=eval a *eval b

eval ( Varname) = ???

Как быть с конструктором Var? Нам нужно откуда-то узнать какое значение связано с переменной. Функ-

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

Этот набор значений мы будем называть окружением.

Обратите внимание на то, что в каждом составном конструкторе мы рекурсивно вызываем функцию eval,

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

значения ( Lit), либо переменные ( Var). Нам было бы удобно иметь возможность пользоваться окружением

из любого узла дерева. В этом нам поможет тип Reader.

Представим что у нас есть значение типа Envи функция, которая позволяет читать значения переменных

по имени:

value :: Env -> String -> Int

Теперь определим функцию eval:

eval :: Exp -> Reader Env Int

eval ( Litn)

=pure n

eval ( Negn)

=liftA

negate $eval n