значения (Lit), либо переменные (Var). Нам было бы удобно иметь возможность пользоваться окружением
из любого узла дерева. В этом нам поможет тип Reader.
Представим что у нас есть значение типа Env и функция, которая позволяет читать значения переменных
по имени:
value :: Env -> String -> Int
Теперь определим функцию eval:
eval :: Exp -> Reader Env Int
eval (Lit n)
= pure n
eval (Neg n)
= liftA
negate $ eval n
eval (Add a b)
= liftA2 (+) (eval a) (eval b)
eval (Mul a b)
= liftA2 (*) (eval a) (eval b)
eval (Var name) = Reader $ env -> value env name
Определение сильно изменилось, оно стало не таким наглядным. Теперь значение eval стало специаль-
ным, поэтому при рекурсивном вызове функции eval нам приходится поднимать в мир специальных функций
обычные функции вычитания, сложения и умножения. Мы можем записать это выражение
немного по другому:
eval :: Exp -> Reader Env Int
eval (Lit n)
= pure n
eval (Neg n)
= negateA $ eval n
eval (Add a b)
= eval a ‘addA‘ eval b
eval (Mul a b)
= eval a ‘mulA‘ eval b
eval (Var name) = Reader $ env -> value env name
addA
= liftA2 (+)
mulA
= liftA2 (*)
negateA
= liftA negate
Тип Map
Для того чтобы закончить определение функции eval нам нужно определить тип Env и функцию value.
Для этого мы воспользуемся типом Map, он предназначен для хранения значений по ключу.
Этот тип живёт в стандартном модуле Data.Map. Посмотрим на его описание:
data Map k a = ..
Первый параметр типа k это ключ, а второй это значение. Мы можем создать значение типа Map из списка
пар ключ значение с помощью функции fromList.
Посмотрим на основные функции:
— Создаём значения типа Map
— создаём
empty :: Map k a
— пустой Map
fromList :: Ord k => [(k, a)] -> Map k a
— по списку (ключ, значение)
— Узнаём значение по ключу
(! )
:: Ord k => Map k a -> k -> a
Отложенное вычисление выражений | 111
lookup
:: Ord k => k -> Map k a -> Maybe a
— Добавляем элементы
insert :: Ord k => k -> a -> Map k a -> Map k a
— Удаляем элементы
delete :: Ord k => k -> Map k a -> Map k a
Обратите внимание на ограничение Ord k в этих функциях, ключ должен быть экземпляром класса Ord.
Посмотрим как эти функции работают:
*Exp> :m +Data.Map
*Exp Data.Map> :m -Exp
Data.Map> let v = fromList [(1, ”Hello”), (2, ”Bye”)]
Data.Map> v ! 1
”Hello”
Data.Map> v ! 3
”*** Exception: Map.find: element not in the map
Data.Map> lookup 3 v
Nothing
Data.Map> let v1 = insert 3 ” Yo” v
Data.Map> v1 ! 3
” Yo”
Функция lookup является стабильным аналогом функции ! . В том смысле, что она определена с помощью
Maybe. Она не приведёт к падению программы, если для данного ключа не найдётся значение.
Теперь мы можем определить функцию value:
import qualified Data.Map as M(Map, lookup, fromList)
…
type Env = M.Map String Int
value :: Env -> String -> Int
value env name = maybe errorMsg $ M. lookup env name
where errorMsg = error $ ”value is undefined for ” ++ name
Обычно функции из модуля Data.Map включаются с директивой qualified, поскольку имена многих
функций из этого модуля совпадают с именами из модуля Prelude. Теперь все определения из модуля
Data.Map пишутся с приставкой M. .
Создадим вспомогательную функцию, которая упростит вычисление выражений:
runExp :: Exp -> [(String, Int)] -> Int
runExp a env = runReader (eval a) $ M. fromList env
Сохраним определение новых функций в модуле Exp. И посмотрим что у нас получилось:
*Exp> let env a b = [(”1”, a), (”2”, b)]
*Exp> let exp = 2 * (n 1 + n 2) — n 1
*Exp> runExp exp (env 1 2)
5
*Exp> runExp exp (env 10 5)
20
Так мы можем пользоваться функциями с окружением для того, чтобы читать значения из общего ис-
точника. Впрочем мы можем просто передавать окружение дополнительным аргументом и не пользоваться
монадами:
eval :: Env -> Exp -> Int
eval env x = case x of
Lit n
-> n
Neg n
-> negate $ eval’ n
Add a b
-> eval’ a + eval’ b
Mul a b
-> eval’ a + eval’ b
Var name
-> value env name
where eval’ = eval env
112 | Глава 7: Функторы и монады: примеры
7.4 Накопление результата
Рассмотрим по-подробнее тип Writer. Он выполняет задачу обратную к типу Reader. Когда мы пользова-
лись типом Reader, мы могли в любом месте функции извлекать данные из окружения. Теперь же мы будем
не извлекать данные из окружения, а записывать их.
Рассмотрим такую задачу нам нужно обойти дерево типа Exp и подсчитать все бинарные операции. Мы
прибавляем к накопителю результата единицу за каждый конструктор Add или Mul. Тип сообщений будет
числом. Нам нужно сделать экземпляр класса Monoid для чисел.
Напомню, что тип накопителя должен быть экземпляром класса Monoid:
class Monoid a where
mempty
:: a
mappend :: a -> a -> a
mconcat :: [a] -> a
mconcat = foldr mappend mempty
Но для чисел возможно несколько вариантов, которые удовлетворяют свойствам. Для сложения:
instance Num a => Monoid a where
mempty
= 0
mappend = (+)
И умножения:
instance Num a => Monoid a where
mempty
= 1
mappend = (*)
Для нашей задачи подойдёт первый вариант, но не исключена возможность того, что для другой зада-
чи нам понадобится второй. Но тогда мы уже не сможем определить такой экземпляр. Для решения этой