( Test. hs, interpreted )
Ok, modules loaded: Test.
254 | Глава 17: Дополнительные возможности
Обобщённые алгебраические типы данных
Предположим, что мы хотим написать компилятор небольшого языка. Наш язык содержит числа и логиче-
ские значения. Мы можем складывать числа и умножать. Для логических значений определена конструкция
if-then-else. Определим тип синтаксического дерева для этого языка:
data Exp = ValTrue
| ValFalse
| If Exp Exp Exp
| Val Int
| Add Exp Exp
| Mul Exp Exp
deriving (Show)
В этом определении кроется одна проблема. Наш тип позволяет нам строить бессмысленные выражения
вроде Add ValTrue (Val 2) или If (Val 1) ValTrue (Val 22). Наш тип Val включает в себя все хорошие вы-
ражения и много плохих. Эта проблема проявится особенно ярко, если мы попытаемся определить функцию
eval, которая вычисляет значение для нашего языка. Получается, что тип этой функции:
eval :: Exp -> Either Int Bool
Для решения этой проблемы были придуманы обобщённые алгебраические типы данных (generalised
algebraic data types, GADTs). Они подключаются расширением GADTs. Помните когда-то мы говорили, что
типы можно представить в виде классов. Например определение для списка
data List a = Nil | Cons a (List a)
можно мысленно переписать так:
data List a where
Nil
:: List a
Cons :: a -> List a -> List a
Так вот в GADT определения записываются именно в таком виде. Обобщение заключается в том, что
теперь на месте произвольного параметра a мы можем писать конкретные типы. Определим тип GExp
{-# LANGUAGE GADTs #-}
data Exp a where
ValTrue
:: Exp Bool
ValFalse
:: Exp Bool
If
:: 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
Теперь у нашего типа Exp появился параметр, через который мы кодируем дополнительные ограничения
на типы операций. Теперь мы не сможем составить выражение Add ValTrue ValFalse, потому что оно не
пройдёт проверку типов.
Определим функцию eval:
eval :: Exp a -> a