Дополнительные возможности

В этой главе мы рассмотрим некоторые дополнительные возможности языка и расширения, которые часто используются в серьёзных программах. Можно писать программы и без них, но с ними гораздо легче и увлекательней.

Пуд сахара

В этом разделе мы рассмотрим специальный синтаксический сахар, который позволяет более кратко записывать операции для некоторых структур.

Сахар для списков

Перечисления

Для класса 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"]

Сахар для монад, do-нотация

Монады используются столь часто, что для них придумали специальный синтаксис, который облегчает подстановку специальных значений в функции нескольких переменных. Монады позволяют комбинировать специальные функции вида

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)))

do или Applicative?

С появлением класса 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 включит в себя наиболее устоявшиеся расширения. Также мы рассмотрели несколько полезных классов и синтаксических конструкций, которые, возможно, облегчают написание программ.

Упражнения

Это была справочная глава, присмотритесь к рассмотренным возможностям и подумайте, какие нужны вам, а какие нет. Возможно, вы вовсе не будете ими пользоваться, но некоторые из них могут встретиться вам в чужом коде или в библиотеках.

Зарегистрировано под лицензией Creative commons Attribution-NonCommercial-NoDerivs 3.0 Generic (CC BY-NC-ND 3.0)