В этой главе мы рассмотрим некоторые дополнительные возможности языка и расширения, которые часто используются в серьёзных программах. Можно писать программы и без них, но с ними гораздо легче и увлекательней.
В этом разделе мы рассмотрим специальный синтаксический сахар, который позволяет более кратко записывать операции для некоторых структур.
Для класса Enum определён специальный синтаксис составления последовательностей перечисляемых значений. Так, например, мы можем составить список целых чисел от нуля до десяти:
Prelude> [0 .. 10] [0,1,2,3,4,5,6,7,8,9,10]
А так мы можем составить бесконечную последовательность положительных чисел:
Prelude> take 20 $ [0 .. ] [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19]
Мы можем составлять последовательности с определённым шагом. Так можно выделить все чётные положительные числа:
Prelude> take 20 $ [0, 2 .. ] [0,2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38]
А так мы можем составить убывающую последовательность чисел:
Prelude> [10, 9 .. 0] [10,9,8,7,6,5,4,3,2,1,0]
Что интересно, в списке могут находиться не только числа, но и любые значения из класса Enum. Например, определим тип:
data Day = Monday | Tuesday | Wednesday | Thursday
| Friday | Saturday | Sunday
deriving (Show, Enum)
Теперь мы можем написать:
*Week> [Friday .. Sunday] [Friday,Saturday,Sunday] *Week> [ Monday .. ] [Monday,Tuesday,Wednesday,Thursday,Friday,Saturday,Sunday]
Также шаг последовательности может быть и дробным:
*Week> [0, 0.5 .. 4] [0.0,0.5,1.0,1.5,2.0,2.5,3.0,3.5,4.0]
Генераторы списков (list comprehensions) объединяют в себе функции преобразования и фильтрации списков. Они записываются так:
[ f x | x <- list, p x]
В этой записи мы фильтруем список list предикатом p и преобразуем результат функцией f. Например, возведём в квадрат все чётные элементы списка:
Prelude> [x*x | x <- [1 .. 10], even x] [4,16,36,64,100]
Предикатов может быть несколько. Так, например, мы можем оставить лишь положительные чётные числа:
Prelude> [x | x <- [-10 .. 10], even x, x >= 0] [0,2,4,6,8,10]
Также элементы могут браться из нескольких списков, посмотрим на все возможные комбинации букв из пары слов:
Prelude> [ [x,y] | x <- "Hello", y <- "World"] ["HW","Ho","Hr","Hl","Hd","eW","eo","er","el", "ed","lW","lo","lr","ll","ld","lW","lo","lr", "ll","ld","oW","oo","or","ol","od"]
Монады используются столь часто, что для них придумали специальный синтаксис, который облегчает подстановку специальных значений в функции нескольких переменных. Монады позволяют комбинировать специальные функции вида
a -> m b
Если бы эти функции выглядели как обычные функции:
a -> b
их можно было бы свободно комбинировать с другими функциями. А так нам постоянно приходится пользоваться методами класса Monad. Очень часто функции с побочными эффектами имеют вид:
a1 -> a2 -> a3 -> ... -> an -> m b
А теперь представьте, что вам нужно подставить специальное значение третьим аргументом такой функции и затем передать ещё в одну такую же функцию. Для облегчения участи программистов было придумано специальное окружение do, в котором специальные функции комбинируются так, словно они являются обычными. Для этого используется обратная стрелка. Посмотрим, как определяется функция sequence в окружении do:
sequence :: [m a] -> m [a]
sequence [] = return []
sequence (mx:mxs) = do
x <- mx
xs <- sequence mxs
return (x:xs)
Во втором уравнении сначала мы говорим вычислителю словом do о том, что выражения записаны в мире монады m. Запись с перевёрнутой стрелкой x <- mx означает, что мы далее в do-блоке можем пользоваться значением x так, словно оно имеет тип просто a, но не m a. Смотрите, в этом определении мы сначала извлекаем первый элемент списка, затем извлекаем хвост списка, приведённый к типу m [a], и в самом конце мы соединяем голову и хвост и оборачиваем результат в специальное значение.
Например, мы можем построить функцию, которая дважды читает строку со стандартного ввода и затем возвращает объединение двух строк:
getLine2 :: IO String
getLine2 = do
a <- getLine
b <- getLine
return (a ++ b)
В do-нотации можно вводить локальные переменные с помощью слова :
t = do
b <- f a
c <- g b
let x = c + b
y = x + c
return y
Посмотрим, как do-нотация переводится в выражение, составленное с помощью методов класса Monad:
do
a <- ma => ma >>= (\a -> exp)
exp
do
exp1 => exp1 >> exp2
exp2
do
let x = fx => let x = fx
y = fy y = fy
exp in exp
Переведём с помощью этих правил определение для второго уравнения из функции sequence
sequence (mx:mxs) = do
x <- mx mx >>= (\x -> do
xs <- sequence mxs => xs <- sequence mxs =>
return (x:xs) return (x:xs))
=> mx >>= (\x -> sequence mxs >>= (\xs -> return (x:xs)))
С появлением класса Applicative во многих случаях do-нотация теряет свою ценность. Так, например, любой do-блок вида:
f mx my = do
x <- mx
y <- my
return (op x y)
можно записать гораздо короче:
f = liftA2 op
Например, напишем функцию, которая объединяет два файла в один:
appendFiles :: FilePath -> FilePath -> FilePath -> IO ()
С помощью do-нотации:
appendFiles file1 file2 resFile = do a <- readFile file1 b <- readFile file2 writeFile resFile (a ++ b)
А теперь с помощью класса Applicative:
appendFiles file1 file2 resFile = writeFile resFile =<< liftA2 (++) (readFile file1) (readFile file2)
Расширение появляется в ответ на проблему, с которой трудно или невозможно справиться в рамках стандарта Haskell. Мы рассмотрим несколько наиболее часто используемых расширений. Расширения подключаются с помощью специального комментария. Он помещается в начале модуля. Расширение действует только в текущем модуле.
{-# LANGUAGE ExtentionName1, ExtentionName2, ExtentionName3 #-}
Обратите внимание на символ решётки, обрамляющего комментарии. Слово LANGUAGE говорит компилятору о том, что мы хотим воспользоваться расширениями с именами ExtentionName1, ExtentionName2, ExtentionName3. Такой комментарий называется прагмой (pragma). Часто компилятор ghc в случае ошибки предлагает нам подключить расширение, в котором ошибка уже не будет ошибкой, а возможностью языка. Он говорит: возможно, вы имели в виду расширение XXX. Например, попробуйте загрузить в интерпретатор модуль:
module Test where class Multi a b where
В этом случае мы увидим ошибку:
Prelude> :l Test
[1 of 1] Compiling Test ( Test.hs, interpreted )
Test.hs:3:0:
Too many parameters for class `Multi'
(Use -XMultiParamTypeClasses to allow multi-parameter classes)
In the class declaration for `Multi'
Failed, modules loaded: none.
Компилятор сообщает нам о том, что у нас слишком много параметров в классе Multi. В рамках стандарта Haskell можно создавать лишь классы с одним параметром. Но за сообщением мы видим подсказку: если мы воспользуемся расширением -XMultiParamTypeClasses, то всё будет хорошо. В этом сообщении имя расширения закодировано в виде флага. Мы можем запустить ghc или ghci с этим флагом и тогда расширение будет активировано, и модуль загрузится. Попробуем:
Prelude> :q Leaving GHCi. $ ghci -XMultiParamTypeClasses Prelude> :l Test [1 of 1] Compiling Test ( Test.hs, interpreted ) Ok, modules loaded: Test. *Test>
Модуль загрузился! У нас есть и другая возможность подключить модуль с помощью прагмы LANGUAGE. Имя расширения записано во флаге после символов -X. Добавим в модуль Test расширение с именем MultiParamTypeClasses:
{-# LANGUAGE MultiParamTypeClasses #-}
module Test where
class Multi a b where
Теперь загрузим ghci в обычном режиме:
*Test> :q Leaving GHCi. $ ghci Prelude> :l Test [1 of 1] Compiling Test ( Test.hs, interpreted ) Ok, modules loaded: Test.
Предположим, что мы хотим написать компилятор небольшого языка. Наш язык содержит числа и логические значения. Мы можем складывать числа и умножать. Для логических значений определена конструкция 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). Наш тип Exp включает в себя все хорошие выражения и много плохих. Эта проблема проявится особенно ярко, если мы попытаемся определить функцию 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 мы можем писать конкретные типы. Определим тип Exp
{-# 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
eval x = case x of
ValTrue -> True
ValFalse -> False
If p t e -> if eval p then eval t else eval e
Val n -> n
Add a b -> eval a + eval b
Mul a b -> eval a * eval b
Если eval получит логическое значение, то будет возвращено значение типа Bool, а на значение типа Exp Int будет возвращено целое число. Давайте убедимся в этом:
*Prelude> :l Exp
[1 of 1] Compiling Exp ( Exp.hs, interpreted )
Ok, modules loaded: Exp.
*Exp> let notE x = If x ValFalse ValTrue
*Exp> let squareE x = Mul x x
*Exp>
*Exp> eval $ squareE $ If (notE ValTrue) (Val 1) (Val 2)
4
*Exp> eval $ notE ValTrue
False
*Exp> eval $ notE $ Add (Val 1) (Val 2)
<interactive>:1:14:
Couldn't match expected type `Bool' against inferred type `Int'
Expected type: Exp Bool
Actual type: Exp Int
In the return type of a call of `Add'
In the second argument of `($)', namely `Add (Val 1) (Val 2)'
Сначала мы определили две вспомогательные функции. Затем вычислили несколько значений. Haskell очень часто применяется для построения компиляторов. Мы рассмотрели очень простой язык, но в более сложном случае суть останется прежней. Дополнительный параметр позволяет нам закодировать в параметре тип функций нашего языка. Спрашивается: зачем нам дублировать вычисления в функции eval? Зачем нам сначала кодировать выражение конструкторами, чтобы только потом получить то, что мы могли вычислить и напрямую.
При таком подходе у нас есть полный контроль за деревом выражения: мы можем проводить дополнительную оптимизацию выражений, если нам известны некоторые закономерности. Ещё функция eval может вычислять совсем другие значения. Например, она может по виду выражения составлять код на другом языке. Возможно, этот язык гораздо мощнее Haskell по вычислительным способностям, но беднее в плане выразительности, гибкости синтаксиса. Тогда мы будем в функции eval проецировать разные конструкции Haskell в конструкции другого языка. Такие программы называются предметно-ориентированными языками программирования (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
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 false true 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 ++ ")"
instance E Print
Теперь распечатаем предыдущие выражения:
*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.
Семейства типов позволяют выражать зависимости типов. Например, представим, что класс определяет не только методы, но и типы. Причём новые типы зависят от конкретного экземпляра класса. Посмотрим, например, на определение линейного пространства из библиотеки 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)
Попробуем вычислить что-нибудь в интерпретаторе:
*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) (-8)
Семейства типов дают возможность организовывать вычисления на типах. Посмотрим на такой классический пример. Реализуем в типах числа Пеано. Нам понадобятся два типа: один для обозначения нуля, а другой для обозначения следующего элемента:
{-# 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. В аргументах мы словно пользуемся сопоставлением с образцом, но на этот раз на типах. Первое уравнение
type instance Add a Zero = a
говорит о том, что если второй аргумент имеет тип ноль, то мы вернём первый аргумент. Совсем как в обычном функциональном определении сложения для натуральных чисел Пеано. Во втором уравнении мы составляем рекурсивное уравнение:
type instance Add a (Succ b) = Succ (Add a b)
Точно также мы можем определить и умножение:
type family Mul a b :: * type instance Mul a Zero = Zero type instance Mul a (Succ b) = Add a (Mul a b)
При этом нам придётся подключить ещё одно расширение UndecidableInstances, поскольку во втором уравнении мы подставили одно семейство типов в другое. Этот флаг часто используется в сочетании с расширением TypeFamilies. Семейства типов фактически позволяют нам определять функции на типах. Это ведёт к тому, что алгоритм вывода типов становится неопределённым. Если типы правильные, то компилятор сможет это установить, но если они окажутся неправильными, то может возникнуть такая ситуация, что компилятор зациклится и будет бесконечно долго искать соответствие одного типа другому. Теперь проверим результаты. Для этого мы создадим специальный класс, который будет переводить значения-типы в обычные целочисленные значения:
class Nat a where
toInt :: a -> Int
instance Nat Zero where
toInt _ = 0
instance Nat a => Nat (Succ a) where
toInt x = 1 + toInt (proxy x)
proxy :: f a -> a
proxy = undefined
Мы определили для каждого значения-типа экземпляр класса Nat, в котором мы можем переводить типы в числа. Функция proxy позволяет нам извлечь значение из типа-конструктора Succ: так мы поясняем компилятору тип значения. При этом мы нигде не пользуемся значениями типов Zero и Succ, ведь у этих типов нет значений.
Теперь посмотрим, что у нас получилось:
Prelude> :l Nat *Nat> let x = undefined :: (Mul (Succ (Succ (Succ Zero))) (Succ (Succ Zero))) *Nat> toInt x 6
Видно, что с помощью класса Nat мы можем извлечь значение, закодированное в типе. Зачем нам эти странные типы-значения? Мы можем использовать их в двух случаях. Мы можем кодировать значения в типе или проводить более тонкую проверку типов.
Помните, когда-то мы определяли функции для численного интегрирования. Там точность метода была жёстко задана в тексте программы:
dt :: Fractional a => a dt = 1e-3 -- метод Эйлера int :: Fractional a => a -> [a] -> [a] int x0 ~(f:fs) = x0 : int (x0 + dt * f) fs
В этом примере мы можем создать специальный тип потоков, у которых шаг дискретизации будет закодирован в типе.
data Stream n a = a :& Stream n a
Параметр n кодирует точность. Теперь мы можем извлекать точность из типа:
dt :: (Nat n, Fractional a) => Stream n a -> a
dt xs = 1 / (fromIntegral $ toInt $ proxy xs)
where proxy :: Stream n a -> n
proxy = undefined
int :: (Nat n, Fractional a) => a -> Stream n a -> Stream n a
int x0 ~(f:&fs) = x0 :& int (x0 + dt fs * f) fs
Теперь посмотрим, как мы можем сделать проверку типов более тщательной. Представим, что у нас есть тип матриц. Известно, что сложение определено только для матриц одинаковой размерности, а для умножения матриц число столбцов одной матрицы должно совпадать с числом строк другой матрицы. Мы можем отразить все эти зависимости в целочисленных типах:
data Mat n m a = ...
instance Num a => AdditiveGroup (Mat n m a) where
a ^+^ b = ...
zeroV = ...
negateV a = ...
mul :: Num a => Mat n m a -> Mat m k a -> Mat n k a
При таких определениях мы не сможем сложить матрицы разных размеров. Причём ошибка будет вычислена до выполнения программы. Это освобождает от проверки границ внутри алгоритма умножения матриц. Если алгоритм запустился, то мы знаем, что размеры аргументов соответствуют.
Скоро в ghc появится поддержка чисел на уровне типов. Это будет специальное расширение TypeLevelNats, при включении которого можно будет пользоваться численными литералами в типах, также будут определены операции-семейства типов на численных типах с привычными именами +, *.
Рассмотрим несколько полезных расширений, относящихся к определению классов и экземпляров классов. Расширение MultiParamTypeClasses позволяет объявлять классы с несколькими аргументами. Например, взгляните на такой класс:
class Iso a b where
to :: a -> b
from :: b -> a
Так мы можем определить изоморфизм между типами a и b
Расширение TypeSynonymInstances позволяет определять экземпляры для синонимов типов. Мы уже пользовались этим расширением, когда определяли рекурсивные типы через тип Fix: там нам нужно было определить экземпляр Num для синонима Nat:
type Nat = Fix N instance Num Nat where
В рамках стандарта все суперклассы должны быть простыми. Все они имеют вид T a. Если мы хотим использовать суперклассы с составными типами, нам придётся подключить расширение FlexibleContexts. Этим расширением мы пользовались, когда определяли экземпляр Show для Fix:
instance Show (f (Fix f)) => Show (Fix f) where
show x = "(" ++ show (unFix x) ++ ")"
Класс можно представить как множество типов, для которых определены данные операции. С появлением расширения MultiParamTypeClasses мы можем определять операции класса для нескольких типов. Так наше множество классов превращается в отношение. Наш класс связывает несколько типов между собой. Если из одной компоненты отношения однозначно следует другая, такое отношение принято называть функцией. Например, обычную функцию одного аргумента можно представить как множество пар (x, f x). Для того чтобы множество таких пар было функцией, необходимо, чтобы выполнялось свойство:
forall x, y. x == y => f x == f y
Для одинаковых входов мы получаем одинаковые выходы. С функциональными зависимостями мы можем ввести такое ограничение на классы с несколькими аргументами. Рассмотрим практический пример. Библиотека Boolean определяет обобщённые логические значения,
class Boolean b where
true, false :: b
notB :: b -> b
(&&*), (||*) :: b -> b -> b
Логические значения определены в терминах простейших операций, теперь мы можем обобщить связку if-then-else и классы Eq и Ord:
class Boolean bool => IfB bool a | a -> bool where
ifB :: bool -> a -> a -> a
class Boolean bool => EqB bool a | a -> bool where
(==*), (/=*) :: a -> a -> bool
class Boolean bool => OrdB bool a | a -> bool where
(<*), (>=*), (>*), (<=*) :: a -> a -> bool
Каждый из классов определён на двух типах. Один из них играет роль обычных логических значений, а второй тип – это такой же параметр, как и в обычных классах из модуля Prelude. В этих определениях нам встретилась новая конструкция: за переменными класса через разделитель “или” следует что-то похожее на тип функции. В этом типе мы говорим, что из типа a следует тип bool, или тип a однозначно определяет тип bool. Эта информация помогает компилятору выводить типы. Если он встретит в тексте выражение v = a <* b и тип одного из аргументов a или b известен, то тип v будет определён по зависимости.
Зачем нам может понадобиться такая система классов? Например, с ней мы можем определить экземпляр Boolean для предикатов или функций вида a -> Bool и затем определить три остальных класса для функций вида a -> b. Мы сравниваем не отдельные логические значения, а функции, которые возвращают логические значения. Так в выражении ifB c t e функция c играет роль “маски”: если на данном значении функция c вернёт истину, то мы воспользуемся значением функции t, иначе возьмём результат из функции e. Например, так мы можем определить функцию модуля:
*Boolean> let absolute = ifB (>0) id negate *Boolean> map absolute [-10 .. 10] [10,9,8,7,6,5,4,3,2,1,0,1,2,3,4,5,6,7,8,9,10]
Мы можем указать несколько зависимостей (через запятую) или зависимость от нескольких типов (через пробел, слева от стрелки):
class C a b c | a -> b, b c -> a where
...
Отметим, что многие функциональные зависимости можно выразить через семейства типов. Пример из библиотеки Boolean можно было бы записать так:
class Boolean a where
true, false :: a
(&&*), (||*) :: a -> a -> a
class Boolean (B a) => IfB a where
type B a :: *
ifB :: (B a) -> a -> a -> a
class IfB a => EqB a where
(==*), (/=*) :: a -> a -> B a
class IfB a => OrdB a where
(<*), (>*), (>=*), (<=*) :: a -> a -> B a
Исторически первыми в Haskell появились функциональные зависимости. Поэтому некоторые пакеты на Hackage определены в разных вариантах. Семейства типов используются более охотно.
В Haskell мы можем не писать типы функций - они будут выведены компилятором автоматически. Но написание типов функций считается признаком хорошего стиля, поскольку по типам можно догадаться, чем функция занимается. Но есть в правиле вывода типов одно исключение. Если мы напишем
f = show
то компилятор сообщит нам об ошибке. Это выражение приводит к ошибке, которая вызвана ограничением мономорфизма. Мы говорили о нём в главе о типах. Часто в сильно обобщённых библиотеках, с большими зависимостями в типах, выписывать типы крайне неудобно. Например, в библиотеке создания парсеров Parsec с этим ограничением приходится писать огромные объявления типов для крохотных выражений. Что-то вроде:
fun :: (Stream s m t, Show t) => ParsecT s u m a -> ParsecT s u m [a] fun = g . h (q x) y
И так для любого выражения. В этом случае лучше просто выключить ограничение, добавив в начало файла:
{-# Language NoMonomorphismRestriction #-}
Когда мы говорили об ST нам встретилась функция с необычным типом:
runST :: (forall s. ST s a) -> a
Слово forall обозначает для любых. Любой полиморфный тип в Haskell подразумевает, что он определён для любых типов. Например, когда мы пишем:
reverse :: [a] -> [a] map :: (a -> b) -> [a] -> [b]
На самом деле мы пишем:
reverse :: forall a. [a] -> [a] map :: forall a b. (a -> b) -> [a] -> [b]
По названию слова forall может показаться, что оно несёт в себе много свободы. Оно говорит о том, что функция определена для любых типов. Но если присмотреться, то эта свобода оказывается жёстким ограничением. “Для любых” означает, что мы не можем делать никаких предположений о внутренней природе значения. Мы не можем разбирать такие значения на составляющие части. Мы можем только подставлять их в новые полиморфные функции (как в map), отбрасывать (как const) или перекладывать из одного места в другое (как в swap или reverse). Мы можем немного смягчить ограничение, если укажем в контексте функции какие классы определены для значений данного типа.
Все стандартные полиморфные типы имеют вид:
fun :: forall a b .. z. Expr(a, b, ..., z)
Причём Expr не содержит forall, а только стрелки и применение новых типов к параметрам. Такой тип называют полиморфным типом первого порядка (rank). Если forall стоит справа от стрелки, то его можно вынести из выражения, например, следующие выражения эквивалентны:
fun :: forall a. a -> (forall b. b -> b) fun :: forall a b. a -> (b -> b)
Так мы можем привести нестандартный тип к стандартному. Если же forall встречается слева от стрелки, как в функции runST, то его уже нельзя вынести. Это приводит к повышению порядка полиморфизма. Порядок полиморфизма определяется как самый максимум среди всех подвыражений, что стоят слева от стрелки плюс один. Так в типе
runST :: (forall s. ST s a) -> a
слева от стрелки стоит тип первого порядка, прибавив единицу, получим порядок для всего выражения. Если вдруг нам захочется воспользоваться такими типами, мы можем включить одно из расширений:
{-# Language Rank2Types #-}
{-# Language RankNTypes #-}
В случае рангов произвольного порядка алгоритм вывода типов может не завершиться. В этом случае нам придётся помогать компилятору, расставляя типы сложных функций вручную.
Мы уже привыкли к тому, что когда мы пишем
swap :: (a, b) -> (b, a)
компилятор понимает, что a и b указывают на один и тот же тип слева и справа от стрелки. При этом типы a и b не обязательно разные. Иногда нам хочется расширить действие контекста функции и распространить его на всё тело функции. Например, ранее в этой главе, когда мы имитировали числа через типы, для того чтобы извлечь число из типа, мы пользовались трюком с функцией proxy:
instance Nat a => Nat (Succ a) where
toInt x = 1 + toInt (proxy x)
proxy :: f a -> a
proxy = undefined
Единственное назначение функции proxy – это передача информации о типе. Было бы гораздо удобнее написать:
instance Nat a => Nat (Succ a) where
toInt x = 1 + toInt (undefined :: a)
Проблема в том, что по умолчанию любой полиморфный тип в Haskell имеет первый ранг – компилятор читает нашу запись как (x :: forall a. a), и получается, что мы говорим: x имеет любой тип, какой захочешь! Не очень полезная информация. Компилятор заблудился и спрашивает у нас: “куда пойти?” А мы ему: “да куда захочешь”. Как раз для таких случаев существует расширение ScopedTypeVariables. Оно связывает тип, объявленный в заголовке класса/функции с типами, которые встречаются в теле функции.
В случае функций есть одно отличие от случая с классами. Если мы хотим расширить действие переменной из объявления типа функции, необходимо упомянуть её в слове forall в стандартном положении (как для типа первого порядка). У нас был ещё один пример с proxy:
dt :: (Nat n, Fractional a) => Stream n a -> a
dt xs = 1 / (fromIntegral $ toInt $ proxy xs)
where proxy :: Stream n a -> n
proxy = undefined
В этом случае мы пишем:
{-# Language ScopedTypeVariables #-}
...
dt :: forall n. (Nat n, Fractional a) => Stream n a -> a
dt xs = 1 / (fromIntegral $ toInt (undefined :: n))
Обратите внимание на появление forall в определении типа. Попробуйте скомпилировать пример без него или переместите его в другое место. Во многих случаях применения этого расширения можно избежать с помощью стандартной функции asTypeOf, посмотрим на определение из Prelude:
asTypeOf :: a -> a -> a asTypeOf x y = x
Фактически это функция const, оба типа которой одинаковы. Она часто используется в инфиксной форме для фиксации типа первого аргумента:
q = f $ x `asTypeOf` var
Получается очень наглядно, словно это предложение обычного языка.
Стоит упомянуть несколько расширений. Они лёгкие для понимания – в основном служат украшению записи или для сокращения рутинного кода.
Директива deriving может использоваться только с несколькими стандартными классами, но если мы определили тип-обёртку через newtype или просто синоним, то мы можем очень просто определить новый тип экземпляром любого класса, который доступен завёрнутому типу. Как раз для этого существует расширение GeneralizedNewtypeDeriving:
newtype MyDouble = MyDouble Double
deriving (Show, Eq, Enum, Ord, Num, Fractional, Floating)
Мы говорили о том, что обычные числа в Haskell перегружены, но иногда возникает необходимость в перегруженных строках. Как раз для этого существует расширение OverloadedStrings. При этом за обычной записью строк может скрываться любой тип из класса:
class IsString a where
fromString :: String -> a
Расширение TypeOperators позволяет определять инфиксные имена не только для конструкторов данных, но и для самих типов, синонимов типов и даже классов:
data a :+: b = Left a | Right b
В этой главе мы затронули малую часть возможностей, которые предоставляются системой ghc. Haskell является полигоном для испытания самых разнообразных идей. Это экспериментальный язык. Но в практических целях в 1998 году был зафиксирован стандарт языка, который обычно называют Haskell98. Любое расширение подключается с помощью специальной прагмы Language. Новый стандарт Haskell Prime включит в себя наиболее устоявшиеся расширения. Также мы рассмотрели несколько полезных классов и синтаксических конструкций, которые, возможно, облегчают написание программ.
Это была справочная глава, присмотритесь к рассмотренным возможностям и подумайте, какие нужны вам, а какие нет. Возможно, вы вовсе не будете ими пользоваться, но некоторые из них могут встретиться вам в чужом коде или в библиотеках.