Neg (Mul (Mul (Var ”2”) (Lit 3)) (Add (Var ”1”) (Lit 2)))
110 | Глава 7: Функторы и монады: примеры
Теперь давайте создадим функцию для вычисления таких выражений. Она будет принимать выражение
и возвращать целое число.
eval :: Exp -> Int
eval (Lit n)
= n
eval (Neg n)
= negate $ eval n
eval (Add a b)
= eval a + eval b
eval (Mul a b)
= eval a * eval b
eval (Var name) = ???
Как быть с конструктором Var? Нам нужно откуда-то узнать какое значение связано с переменной. Функ-
ция eval должна также принимать набор значений для всех переменных, которые используются в выражении.
Этот набор значений мы будем называть окружением.
Обратите внимание на то, что в каждом составном конструкторе мы рекурсивно вызываем функцию eval,
мы словно обходим всё дерево выражения. Спускаемся вниз, до самых листьев в которых расположены либо
значения (Lit), либо переменные (Var). Нам было бы удобно иметь возможность пользоваться окружением
из любого узла дерева. В этом нам поможет тип Reader.
Представим что у нас есть значение типа Env и функция, которая позволяет читать значения переменных
по имени:
value :: Env -> String -> Int
Теперь определим функцию evaclass="underline"
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, поскольку имена многих