Учебник по Haskell

Такие типы называют абстрактными синтаксическими деревьями (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”) (Lit 2)

*Exp> 3 * (n 1 + 2)

Mul (Lit 3) (Add (Var ”1”) (Lit 2))

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

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

Теперь определим функцию 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