Язык Haskell, алгебраические типы данных

Опять про последовательности

Напомним, что последовательность с наиболее элементарной точки зрения – одно из двух: пустая последовательность или же результат присоединения первого элемента к последовательности остальных. На языке Haskell это можно выразить определением

data Sequence x = Empty
                | Cons x (Sequence x) -- название Cons для узла списка исторически сложилось

Это объявление определяет два конструктора данных:

Empty :: Sequence x
Cons  :: x -> Sequence x -> Sequence x

Основное отличие от обычных функций или констант – по конструкторам данных можно вести индукцию:

sequenceLength Empty       = 0
sequenceLength (Cons x xs) = 1 + sequenceLength xs

Конечно же, определённый нами тип Sequence x полностью аналогичен стандартному типу [x]. Единственная разница: отсутствие синтаксической поддержки со стороны языка. Покажем, что эти два типа изоморфны:

iso1 :: Sequence x -> [x]
iso1 Empty       = []
iso1 (Cons x xs) = x : xs

iso2 :: [x] -> Sequence x
iso2 []     = Empty
iso2 (x:xs) = Cons x xs

Отображения iso1 и iso2 обратны друг другу в стандартном смысле: выполнены равенства

-- это не настоящий код на Haskell; под = здесь понимается нормальная эквивалентность
iso1 $ iso2 x = x
iso2 $ iso1 x = x

Некоторые стандартные алгебраические типы

При написании модуля есть возможность запретить его пользователям использовать конструкторы некоторого типа данных, вместо этого предоставляя какие-то функции, строящие объекты этого типа. Подобная ситуация, например, имеет место для типа IO a. Такие типы данных называются абстрактными. В противовес им те типы данных, которые рассчитаны на индукцию по их структуре, называются алгебраическими.

Приведём три важнейших стандартных алгебраических типа данных (помимо списков и кортежей):

data Bool       = False   | True
data Maybe a    = Nothing | Just a
data Either a b = Left a  | Right b

Все эти три типа используются для моделирования “частичных функций” – функций, определённых не на всей области определения. Приведём пример трёх функций, выполняющих одно и то же преобразование, но с разной детализацией:

hasDigitCount :: Integer -> Bool
hasDigitCount n = n >= 0

digitCount :: Integer -> Maybe Integer
digitCount n
  | n < 0  = Nothing
  | n < 10 = 1
  | True   = 1 + digitCount (n `div` 10)


digitCountE :: Integer -> Either String Integer
digitCountE n = case digitCount n of
    Just n  -> Right n
    Nothing -> Left "Число отрицательно"

Для типов Maybe a и Either a b определены операции >>= и pure. Это, в частности, позволяет использовать для них do-нотацию. Определения таковы:

-- для Maybe
Nothing  >>= _ = Nothing
(Just x) >>= f = f x

pure x = Just x


-- для Either
(Left  x) >>= _ = Left x
(Right x) >>= f = f x

pure x = Right x

Немного о классах типов

Наверняка вы обратили внимание на типы некоторых стандартных функций, например:

show  :: Show a        => a -> String
(<$>) :: Functor f     => (a -> b) -> f a -> f b
pure  :: Applicative f => a -> f a
(>>=) :: Monad m       => m a -> (a -> m b) -> m b

Выражения между :: и => называются ограничениями или контекстом. Они накладывают ограничения на то, какие типы могут фигурировать вместо соответствующих параметров. Если, например, попытаться ввести в интерпретатор

(Cons 1 $ Cons 2 $ Cons 3 $ Empty)

то он выдаст ошибку о том, что тип Sequence x не удовлетворяет ограничению Show (Sequence x), и ничего не напечатает. На самом деле, к любому вычисленному выражению интерпретатор применяет композицию putStrLn . show. Для нашего же типа Sequence x операция show не реализована.

По некоторым причинам Haskell не позволяет просто написать

show Empty      = "Empty"
show (Cons a b) = "Cons (" ++ show a ++ ") (" ++ show b ++ ")"

Для того, чтобы самостоятельно определить show, нужно использовать специальный синтаксис, который мы рассмотрим в одной из следующих глав. Тем не менее, Haskell позволяет автоматически определить show:

data Sequence x = Empty | Cons x (Sequence x)
  deriving(Show) -- нужно дописать эту конструкцию (правее слова data!)

Такие вещи, как Show, Functor, Applicative, Monad и прочее, называются классами типов. Принадлежность типа некоторому классу означает наличие для величин этого типа некоторого набора функций (обычно при этом ещё и удовлетворяющих некоторым алгебраическим свойствам). Опишем несколько простейших классов типов:

Уже упомянутый Show, и “обратный” класс Read. Обеспечивают возможность преобразования в текст и обратно. По-хорошему, вместо функций show и read гораздо лучше использовать функции shows и reads. Работают они следующим образом:

shows x text = show x ++ text

-- shows при помощи очень странного трюка кардинально меняет асимптотическую сложность 
-- множественной левоассоциированной конкатенации
-- (..((show 1 ++ show 2) ++ show 3) ++ ... ++ show n)    имеет время работы, пропорциональное n^2
-- (..((shows 1 . shows 2) . shows 3) . ... . shows n) "" имеет время работы, пропорциональное n


--                 Входной текст      Прочтение  Оставшаяся часть входного текста
reads :: Read a => String ->        [(a,         String)]

-- reads выдаёт множество всевозможных прочтений начала входного текста как величины типа a.
-- Например, можно реализовать следующий способ считывания числа, не приводящий к вылету программы:

readMaybe text = case reads text of
    (x,_):_ -> Just x
    []      -> Nothing

Классы Eq и Ord. Первый класс отвечает за возможность сравнивать на равенство оператором ==, а второй – за возможность использовать операций “больше/меньше”.
Класс Num. Число или нечто похожее. Именно этот класс даёт возможность применения сложения и умножения. А также, зачем-то, абсолютной величины, знака, вычитания и fromInteger. Вообще говоря, в Haskell определено ещё несколько числовых классов, причём тоже крайне неудачных.
Класс Enum. Именно этот класс отвечает за возможность писать [a..b]. Главные функции: fromEnum :: Enum a => a -> Int и toEnum :: Enum a => Int -> a. Например, для типа Char эти функции осуществляют биекцию между символами их их кодами в кодировке UTF32.
Functor, Applicative, Monad – ограничения, накладываемые не на типы, а на конструкторы типов. Отвечают за следующие функции:
```
(<$>) :: Functor     f => (a ->   b) -> f a -> f b
pure  :: Applicative f =>         b         -> f b
(<*>) :: Applicative f => f (a -> b) -> f a -> f b
(=<<) :: Monad       f => (a -> f b) -> f a -> f b
```
Каждое следующее ограничение строго сильнее предыдущего: Applicative включает в себя Functor, а Monad включает в себя Applicative. Трудно дать какой-то общий взгляд на какой бы то ни было из этих трёх классов: конкретные реализации вышеупомянутых функций для различных типов данных могут быть совершенно непохожими друг на друга.

И совсем чуточку о катаморфизмах

Рассмотрим следующий алгебраический тип:

data Expr = Add Expr Expr | Sub Expr Expr | Mul Expr Expr | Num Integer

Он описывает выражения, составленные при помощи чисел и знаков сложения, вычитания, умножения. Значения подобных выражений можно вычислять функцией

evaluate :: Expr -> Integer
evaluate (Num x)     = x
evaluate (x `Add` y) = evaluate x + evaluate y
evaluate (x `Sub` y) = evaluate x - evaluate y
evaluate (x `Mul` y) = evaluate x * evaluate y

Эта функция представляет собой пример катаморфизма для типа Expr. В общем случае катаморфизм для типа Expr выглядит так:

exprCata :: (e -> e -> e) -> (e -> e -> e) -> (e -> e -> e) -> (Integer -> e) -> Expr -> e
exprCata add sub mul num = go
  where
    go (Num x)   = num x
    go (Add x y) = add (go x) (go y)
    go (Sub x y) = sub (go x) (go y)
    go (Mul x y) = mul (go x) (go y)

По сути, катаморфизм заменяет все конструкторы данных, из которых составлен объект некоторого типа, на заданные функции или константы.

Вспомним теперь, как определены стандартные списки. У них два конструктора:

[]  :: [a]
(:) :: a -> [a] -> [a]

Поэтому катаморфизм для списка выглядит так:

listCata :: (a -> l -> l) -> l -> [a] -> l
listCata cons empty []     = empty
listCata cons empty (x:xs) = x `cons` listCata cons empty xs

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

length   list = foldr (\a b -> 1 + b)                     0 list
sum      list = foldr (+)                                 0 list
factorial   n = foldr (*)                                 1 [1..n]
(<$>)  f list = foldr (\a b -> f a : b)                  [] list
filter p list = foldr (\a b -> if p a then a : b else b) [] list

Кодировка Чёрча

Поменяем порядок аргументов у listCata/foldr:

listToCata :: [a] -> ( (a -> l -> l) -> l -> l )
listToCata l c e = foldr c e l

Мы видим, что listToCata сопоставляет каждому списку типа [a] функцию типа (a -> l -> l) -> l -> l. Оказывается, по этой функции можно восстановить список:

cataToList :: (forall l. (a -> l -> l) -> l -> l) -> [a]
cataToList cata = cata (:) []

Чтобы указать правильный тип аргумента функции cataToList, нам понадобилось расширение языка RankNTypes, которое включается специальным комментарием

{-# LANGUAGE RankNTypes #-}

который должен стоять в самом начале программы (до строки module … where). Без этого расширения (или же без явного указания типа) определение

cataToList cata = cata (:) []

будет типизировано следующим образом:

cataToList :: ((a -> [a] -> [a]) -> [b] -> c) -> c

На первый взгляд, в таком типе нет ничего страшного, кроме того, что такое отображение не является обратным к listToCata:

listToCata l c e = foldr c e l
cataToList cata = cata (:) []  -- без указания типа используется "неправильный" вариант

-- вариант, отличный от (foldr c e)
bad c e = [1,2,3]


-- ПРИ ВЫЧИСЛЕНИИ ПОЛУЧИТСЯ СЛЕДУЮЩЕЕ --
bad                           (:) [4,5,6] => [1,2,3]
(listToCata $ cataToList bad) (:) [4,5,6] => [1,2,3,4,5,6]

Итого мы имеем пару изоморфизмов: отображение listToCata преобразует список в катаморфизм по этому списку, а cataToList преобразует катаморфизм по некоторому списку в этот список. Представление некоторого объекта в виде катаморфизма по этому объекту называется кодировкой Чёрча.

Вернёмся ненадолго к классическому лямбда-исчислению. Вспомним числительные Чёрча:

zero  f x = x
one   f x = f x
two   f x = f (f x)
three f x = f (f (f x))
-- и так далее

-- ОБЩИЙ ВИД ЧИСЛИТЕЛЬНОГО ЧЁРЧА --
church :: Int -> (a -> a) -> a -> a
church n f x = head $ drop n $ iterate f x

Найдём тип данных a, для которого числительные Чёрча являются катаморфизмами. У него должно быть два конструктора типов:

Succ :: a -> a
Zero :: a

Этот тип – самое обычное “унарное” представление целых неотрицательных чисел:

data Nat = Zero | Succ Nat

Напоследок о полиморфизме в Haskell

Полиморфизм – механизм, обеспечивающий возможность объединить несколько функций под одним названием. Разновидность полиморфизма, используемая в Haskell называется параметрическим полиморфизмом с ограничениями. Это означает, что типы выражений могут содержать «параметры», которые могут в ходе проверки типов конкретизироваться (в произвольный тип или же в тип, принадлежащий некоторому классу).

Например, тип функции

id :: a -> a
id x = x

в выражении id (\x -> 5) конкретизируется в Num b => (a -> b) -> (a -> b).

В Haskell есть одно существенное ограничение, называемое предикативностью: параметры не могут конкретизироваться в полиморфный тип. Типичный пример:

apply :: (a -> b) -> a -> b

foo :: (forall a. a -> a) -> String
foo _ = ":-)"


apply foo id 
-- не типизируется, поскольку в типе (a -> b) -> a -> b параметр a должен 
-- конкретизироваться в полиморфный тип forall x. x -> x

foo $ id
-- типизируется, но ТОЛЬКО из-за специальной поддержки оператора $ со стороны компилятора

В принципе, ограничение предикативности можно обойти, как в следующем примере:

-- В примере представлен гетерогенный список (список, элементы которого могут
-- иметь разные типы) на основе обычного списка и кодировки Чёрча для его элементов.
data Showable = S (forall m . (forall a . Show a => a -> m) -> m)

toShowable :: Show a => a -> Showable
toShowable x = S $ \f -> f x

showShowable :: Showable -> String
showShowable (S s) = s show

printList :: [Showable] -> IO ()
printList list = sequence_ $ (putStrLn . showShowable) <$> list

Упражнения (задание на каникулы)

Определите катаморфизм для бинарного дерева и с помощью него преобразуйте дерево чисел в выражение типа Expr, трактуя узлы как знаки вычитания.

data Tree x = Leaf x
            | Node (Tree x) (Tree x)
            

treeToCata :: Tree x -> ???
treeToCata = ???


treeToExpr :: Tree Integer -> Expr
treeToExpr tree = treeToCata tree ???


-- ДОЛЖНО ВЫПОЛНЯТЬСЯ, НАПРИМЕР, СЛЕДУЮЩЕЕ --
(evaluate $ treeToExpr $ Node (Node (Leaf x) (Leaf y)) (Leaf z)) == (x-y)-z

treeToCata :: Tree x -> (x -> t) -> (t -> t -> t) -> t
treeToCata tree leaf node = case tree of
    Leaf x     -> leaf x
    Node t1 t2 -> node (treeToCata t1 leaf node) (treeToCata t2 leaf node)
    
treeToExpr tree = treeToCata tree Sub Num

Левая свёртка последовательности определена так:
```
foldl f a []     = a
foldl f a (x:xs) = foldl f (f a x) xs
```
Выразите foldl через foldr (в определении не должно присутствовать явной рекурсии).

foldl (**) n l = foldr (=>=) id l n
  where x =>= f = \m -> f (m ** x)

Операции <$>, <*>, =<< по сути являются разнообразными обобщениями обычной операции применения $. Реализуйте эти операции для списков, предварительно поэкспериментировав в ghci со следующими выражениями:
```
(^2) <$> [1,2,3,4,5]
(+)  <$> [1,2,3] <*> [4,5,6]
(,,) <$> [1,2,3] <*> [4,5,6] <*> [7,8]
pure 4 :: [Int]
(\x -> replicate x x) =<< [1,2,3,2,1]
```

f <$> l = case l of
    []   -> []
    x:xs -> f x : (f <$> xs)
    
a <*> l = case a of
    []   -> []
    f:fs -> (f <$> l) : (fs <*> l)

f =<< l = foldr (++) [] (f <$> l)

Вообще говоря, функция pure – очередной пример неудачного дизайна. Точнее, не сама функция, а то, что она является базовой для класса Applicative. Оказывается, функция pure полностью выражается через одно из своих значений:
```
unit :: Applicative f => f ()
unit = pure ()
```
Реализуйте функцию myPure, эквивалентную pure, при помощи unit и <$>. Убедитесь, что myPure работает так же, как и pure, для Maybe, списоков и IO.

myPure x = (\_ -> x) <$> unit

Для типа Expr, приведённого в этой главе, реализуйте функции display :: Expr -> String и parse :: String -> Expr, осуществляющие преобразования между выражениями и их естественным представлением. Например, parse "2 + 3*4" должно преобразовываться в Add 2 (Mul 3 4). Также требуется, чтобы parse $ display x было нормально эквивалентно x.