в конструкции другого языка. Такие программы называются предметно-ориентированными языками програм-
мирования (domain specific languages). Мы кодируем в типе Exp некоторую область и затем надстраиваем
над типом Exp разные полезные функции. На самом последнем этапе функция eval переводит всё дерево
выражения в значение или код другого языка.
Отметим, что не так давно было предложено другое решение этой задачи. Мы можем закодировать типы
функций в классе:
class E exp where
true
:: exp Bool
false
:: exp Bool
iff
:: exp Bool -> exp a -> exp a -> exp a
val
:: Int -> exp Int
add
:: exp Int -> exp Int -> exp Int
mul
:: exp Int -> exp Int -> exp Int
Преимуществом такого подхода является модульность. Мы можем спокойно разделить выражение на две
составляющие части:
class (Log exp, Arith exp) => E exp
class Log exp where
true
:: exp Bool
false
:: exp Bool
iff
:: exp Bool -> exp a -> exp a -> exp a
class Arith exp where
val
:: Int -> exp Int
add
:: exp Int -> exp Int -> exp Int
mul
:: exp Int -> exp Int -> exp Int
Интерпретация дерева выражения в этом подходе заключается в создании экземпляра класса. Например
создадим класс-вычислитель Eval:
newtype Eval a = Eval { runEval :: a }
instance Log Eval where
256 | Глава 17: Дополнительные возможности
true
= Eval True
false
= Eval False
iff p t e = if runEval p then t else e
instance Arith Eval where
val
= Eval
add a b = Eval $ runEval a + runEval b
mul a b = Eval $ runEval a * runEval b
instance E Eval
Теперь проведём такую же сессию вычисления значений, но давайте теперь сначала определим их в тексте
программы:
notE :: Log exp => exp Bool -> exp Bool
notE x = iff x true false
squareE :: Arith exp => exp Int -> exp Int
squareE x = mul x x
e1 :: E exp => exp Int
e1 = squareE $ iff (notE true) (val 1) (val 2)
e2 :: E exp => exp Bool
e2 = notE true
Загрузим в интерпретатор:
*Exp> :r
[1 of 1] Compiling Exp
( Exp. hs, interpreted )
Ok, modules loaded: Exp.
*Exp> runEval e1
4
*Exp> runEval e2
False
Получились такие же результаты и в этом случае нам не нужно подключать никаких расширений. Теперь
создадим тип-принтер, он будет распечатывать выражение:
newtype Print a = Print { runPrint :: String }
instance Log Print where
true
= Print ”True”
false
= Print ”False”
iff p t e = Print $ ”if (” ++ runPrint p ++ ”) {”
++ runPrint t ++ ”}”
++ ”{” ++ runPrint e ++ ”}”
instance Arith Print where
val n
= Print $ show n
add a b = Print $ ”(” ++ runPrint a ++ ”)+(” ++ runPrint b ++ ”)”
mul a b = Print $ ”(” ++ runPrint a ++ ”)*(” ++ runPrint b ++ ”)”
Теперь распечатаем предыдущие выражения:
*Exp> :r
[1 of 1] Compiling Exp
( Exp. hs, interpreted )
Ok, modules loaded: Exp.
*Exp> runPrint e1
”(if (if (True) {False}{True}) {1}{2})*(if (if (True) {False}{True}) {1}{2})”
*Exp> runPrint e2
”if (True) {False}{True}”
При таком подходе нам не пришлось ничего менять в выражениях, мы просто заменили тип выражения
и оно автоматически подстроилось под нужный результат. Подробнее об этом подходе можно почитать на
сайте http://okmij.org/ftp/tagless-final/course/course.html или в статье Жака Каре (Jacques Carette), Олега Киселёва (Oleg Kiselyov) и Чунг-Че Шена (Chung-chieh Shan) Finally Tagless, Partially Evaluated.
Расширения | 257
Семейства типов
Семейства типов позволяют выражать зависимости типов. Например представим, что класс определяет
не только методы, но и типы. Причём новые типы зависят от конкретного экземпляра класса. Посмотрим,
например, на определение линейного пространства из библиотеки vector—space:
class AdditiveGroup v where
zeroV
:: v
(^+^)
:: v -> v -> v
negateV :: v -> v
class AdditiveGroup v => VectorSpace v where
type Scalar v
:: *
(*^)
:: Scalar v -> v -> v
Линейное пространство это математическая структура, объектами которой являются вектора и скаля-
ры. Для векторов определена операция сложения, а для скаляров операции сложения и умножения. Кроме
того определена операция умножения вектора на скаляр. При этом должны выполнятся определённые свой-
ства. Мы не будем подробно на них останавливаться, вкратце заметим, что эти свойства говорят о том, что
мы действительно пользуемся операциями сложения и умножения. В классе VectorSpace мы видим новую
конструкцию, объявление типа. Мы говорим, что есть производный тип, который следует из v. Далее через
двойное двоеточие мы указываем его вид. В данном случае это простой тип без параметров.
Вид (kind) это тип типа. Простой тип без параметра обозначается звёздочкой. Тип с параметром обозна-
чается как функция * -> *. Если бы тип принимал два параметра, то он обозначался бы * -> * -> *. Также
параметры могут быть не простыми типами а типами с параметрами, например тип, который обозначает
композицию типов:
newtype O f g a = O { unO :: f (g a) }
имеет вид (* -> *) -> (* -> *) -> * -> *.
Определим класс векторов на двумерной сетке и сделаем его экземпляром класса VectorSpace. Для нача-
ла создадим новый модуль с активным расширением TypeFamilies и запишем в него классы для линейного
пространства
{-# Language TypeFamilies #-}
module Point2D where
class AdditiveGroup v where
…
Теперь определим новый тип:
data V2 = V2 Int Int
deriving (Show, Eq)
Сделаем его экземпляром класса AdditiveGroup:
instance AdditiveGroup V2 where
zeroV
= V2 0 0
(V2 x y)
^+^ (V2 x’ y’)
= V2 (x+x’) (y+y’)
negateV (V2 x y)
= V2 (—x) (—y)
Мы складываем и вычитаем значения в каждом из элементов кортежа. Нейтральным элементом от-
носительно сложения будет кортеж, состоящий из двух нулей. Теперь определим экземпляр для класса
VectorSpace. Поскольку кортеж состоит из двух целых чисел, скаляр также будет целым числом:
instance VectorSpace V2 where
type Scalar V2 = Int
s *^ (V2 x y) = V2 (s*x) (s*y)
Попробуем вычислить что-нибудь в интерпретаторе:
258 | Глава 17: Дополнительные возможности
*Prelude> :l Point2D
[1 of 1] Compiling Point2D
( Point2D. hs, interpreted )
Ok, modules loaded: Point2D.
*Point2D> let v =
V2 1 2
*Point2D> v ^+^ v
V2 2 4
*Point2D> 3 *^ v ^+^ v
V2 4 8
*Point2D> negateV $ 3 *^ v ^+^ v
V2 (—4) (—
Семейства функций дают возможность организовывать вычисления на типах. Посмотрим на такой клас-
сический пример. Реализуем в типах числа Пеано. Нам понадобятся два типа. Один для обозначения нуля,
а другой для обозначения следующего элемента:
{-# Language TypeFamilies, EmptyDataDecls #-}
module Nat where
data Zero
data Succ a
Значения этих типов нам не понадобятся, поэтому мы воспользуемся расширением EmptyDataDecls, ко-
торое позволяет определять типы без значенеий. Значениями будут комбинации типов. Мы определим опе-
рации сложения и умножения для чисел. Для начала определим сложение:
type family Add a b :: *
type instance Add a Zero
= a
type instance Add a (Succ b)
= Succ (Add a b)
Первой строчкой мы определили семейство функций Add, у которого два параметра. Определение семей-
ства типов начинается с ключевой фразы type family. За двоеточием мы указали тип семейства. В данном
случае это простой тип без параметра. Далее следуют зависимости типов для семейства Add. Зависимости
типов начинаются с ключевой фразы type instance. В аргументах мы словно пользуемся сопоставлением с
