Зоопарк Алгебрaических Типов Данных

В этой статье мы попытаемся рассмотреть всё разнообразие Алгебраических Типов Данных.

Надо сказать, задача это достаточно неподъёмная, и понять человеку, если он ранее с Алгебраическими Типами не имел дело — не очень просто.
АТД были впервые использованы в языке Hope, но основную популярность они приобрели благодаря языкам ML, такими как Standart ML, OCaml, F#, и языку Haskell.
Ныне АТД в той или иной мере поддерживаются в значительно большем количестве языков: Scala, Rust, Nemerle, Racket,…
АТД называются алгебраическими, потому что их можно представить как некую алгебраическую композицию типов. Это знание даёт своё преимущество: понимая свойства алгебраической композиции, можно посчитать какой тип необходим для построения тех или иных данных.
Будем рассматривать типы на основе языка Haskell, однако подобного с лёгкими изменениями можно добиться в других языках с поддержкой АТД.

Надо отметить, что теории типов, развитые в ХХм веке Расселом, Чёрчем, Мартином-Лёфом получили такую популярность, что ныне (уже в ХХІм веке) появилась теория Гомотопической Теории типов, которая покусилась объяснить фундамент математики.

Наша же задача посмотреть на Алгебраические Типы Данных. Зачастую данные АТД называют коробочными. Они так названы, потому что выглядят как запакованные в коробку данные. Самое интересное, что даже реализация подразумевает хранение не данных, а указателей. Помимо простоты реализации, это даёт действенные механизмы ленивости, коим обладает Хаскель.
Справедливости ради, замечу, что Хаскель позволяет создавать неленивые, в том числе и безкоробочные данные, что помогает при обработке высоко-нагруженными объёмами данных.
В Хаскеле существует 2 способа создать АТД, с помощью декларации data или newtype. Разница между ними состоит в том, что newtype де-факто безкоробочный, а значит и более дешёвый (по ресурсам машины), и поэтому более выгодный, но с помощью него можно записать лишь узкий круг АТД, поэтому он не подходит в общем случае.

Типы данных, реализованные через примитивы

В Хаскеле таких немного, прежде всего это такие типы данных, как
Int, Integer, Float, Double, Char,…
Дело не в том, что нельзя составить эти типы по настоящему (через АТД), просто компьютер уже умеет работать с числами, и грех этим не воспользоваться.
Хочу обратить внимание, что все типы пишутся с заглавной буквы, это связано с тем, что все конструкторы типов и данных в Хаскеле пишутся исключительно с заглавной буквы.

Нулевые типы данных

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

Это не настоящие, псевдо-нулевые, пустые типы данных

data S
data T a
data K a b

Синтаксис, как мы видим прост до безобразия.
Тут мы создали 3 типа данных, второй из которых — параметрический. Мы видим, что a пишется с прописной буквы, а значит не может быть конструктором. Вывод — это параметр, в который можно подставлять любой тип, то есть можно иметь следующие типы: T Int, T Char, T S, T (T Double) и даже T (T ( T String)).
Мы также видим, что конструктор стоит вначале типа, а далее данные как бы упаковываются в коробку.
Вы спросите, зачем они нужны?
Например, мы можем писать следующий валидный код функций:

doubleT :: T a -> (T a, T a)
doubleT t = (t, t)

Конечно, в большинстве случаев написать все функции без внутреннего знания о данных нельзя, но можно часть функций оставить на потом, занимаясь другими задачами, такими как эта:

foo :: S -> Int -> T a
foo = undefined

bar :: S -> IO Int -> IO (T a)
bar s i = i >>= foo s

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

Настоящий нулевой тип данных выглядит достаточно необычно для нетренированного глаза, но мы сможем это понять.
Он был найден сравнительно недавно, всё ещё нет в Платформе (чтобы можно было пользоваться из коробки), и ещё мало используемый.

newtype Void = Void Void

newtype VoidData = Void VoidData

Единичные типы данных

Единичные типы данных не дают ничего, кроме знания о том, что он есть.
Из распространённых типов данных используются

data () = ()      --X

здесь и далее комментарием

  -- X

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

main :: IO ()

потому что программа должна что-то возвращать. Поэтому () является самым популярным типом, когда надо возвращать ничего.
Или, вот ещё известный единичный тип:

data Unit = Unit  

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

data UnitData = Unit  

дело в том, что пространство имён типов не пересекается с пространством конструкторов типа, поэтому компилятор отлично понимает где есть рекурсия, а где нет.

Типы произведений

Типы произведений названы так, что их можно представить как произведение нескольких типов, которые его составляют.
Очень популярные типы данных, используются повсеместно.
Самые известные из них, это кортежи или туплы. В Хаскеле используется специальный синтаксический сахар для этого:

data (,) a b        = (,) a b            --X  (a, b)
data (,,) a b c     = (,,) a b c         --X  (a, b, c)
data (,,,,) a b c d = (,,,,) a b c d     --X  (a, b, c, d)

то же самое мы можем записать и с помощью обычных конструкторов:

data Pair a b = Pair a b
data Triple a b c = Triple a b c

Везде где нужно хранить более одного данного в данных — это тип произведений.

Суммарные типы данных

Суммарные типы данных названы потому, что они суммируют типы данных, которые их составляют.
Например, если суммировать единичные типы данных, получается перечисление.
Представляю один из самых знаменитых перечислений:

data Bool = False | True

так же известным перечислением является тип Ordering, который используется в сравнениях

data Ordering = LT | EQ | GT

Если перейдём к более сложным АТД, тут необходимо вспомнить нулл-абельный тип:

data Maybe a = Nothing | Just a

Данные, которые имеют поле для результата, когда его нет, так сказать null из многих языков программирования.

(</>) :: Int -> Int -> Maybe Int
_ </> 0 = Nothing
a </> b = Just (a `div` b)

Если необходимо более детально узнать об ошибке, используется ещё более сложный тип данных:

data Either a b = Left a | Right b

тип данных, где есть либо «левый» результат (описание ошибки или сама ошибка), либо «правильный» результат.
Также этот тип данных используют для бинарного выбора.

type IdPerson = Int
type ErrorMsg = String

personChecker :: Person -> Either ErrorMsg IdPerson
personChecker p = do
            when (age p < 0) $ Left "this guy is not born yet!"
            when (null $ first_name p) $ Left "this guy is unnamed!"
            Right $ registeredId p

Можно составлять и более экзотические типы данных, например:

data Both a b = None | First a | Second b | Both a b

тут у нас либо нет результата, либо 1 результат, либо 2й, либо и 1й и 2й.

Рекурсивные типы данных

В Хаскеле спокойно можно создать рекурсивные типы данных.
Самым известным, использующий синтаксический сахар, типом являются списки:

data [] a = [] | a : [a]     --X

Однако его можно легко переписать словами:

data List a = Nil | Cons a (List a)

Хочу заметить, что в качестве конструкторов могут использоваться спец-символы (:), тогда пользуются инфиксной записью
Хотим построить дерево? Да без проблем.
Например, простое бинарное дерево:

data Tree a = Leaf a | Branch (Tree a) (Tree a)
data Tree2 a = Empty | Branch2 (Tree2 a) a (Tree2 a)

Или вот ещё, натуральные числа:

data Nat = Zero | Succ Nat

Если вы ещё не открыли спойлер о нулевом типе данных (или открыли, но не поняли) — самое время открыть и почитать и понять, что Void элементарный бесконечно-рекурсивный тип данных.

Степенные типы данных

Не надо думать, что в АТД можно записать лишь данные. Функции тоже легко могут быть записаны в АТД: степенные типы (общий тип имеет мощность возведения в степень одного типа данных в мощность другого):

data Fun a b = Fun (a -> b)
newtype ContT r m a = Writer ((a -> m r) -> m r)

Если мы будем использовать АТД произведений, где данные будут вперемешку с функциями — это ни что иное, как записи, и очень похожие структуры на объекты.

Фантомные типы данных

Иногда приходится создавать достаточно необычное поведение, и приходится изобретать типы, которые ничего не делают, но делают вид, что делают. Для этого используют, в частности, фантомные типы. Одним из самых известных типов является:

data Proxy a = Proxy

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

proxyСonverter :: Proxy a -> Proxy b
proxyСonverter Proxy = Proxy

Записи

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

data Sex =  Female | Male
data Person = Person String String Int Int Sex (String -> String)

значительно удобнее переписать в:

data Sex =  Female | Male
data Person = Person  { lastName  :: String
                      , firstName :: String
                      , age       :: Int 
                      , socialId  :: Int 
                      , sex       :: Sex
                      , greeting  :: String -> String
                      }

Вставки или Враперы

Вставки пользуются там, где необходимо либо скрыть реализацию типа, защитить от постороннего вмешательства, либо для придания других свойств, нежели материнский тип.
Записывается он подобным образом (с синтаксисом записей):

newtype Wrapper a = Wrapper { unwrapper :: a }
newtype Dollar = Dollar Int

Экзистенциальные типы данных

Экзистенциальные типы данных названы так из-за квантора существования ∃.
Парадокс состоит в том, что в Хаскеле нет такого квантора.
Зато есть квантор всеобщности ∀. Но эти кванторы можно легко преобразовать друг в друга.

data HeteroData = forall a. HeteroData a

heteroList :: [HeteroData]
heteroList = [HeteroData 3.7, HeteroData "message", HeteroData True]

Как видим, смогли создать гетерогенный список, несмотря на то, что он гомогенный.
А вот что-то похоже на объект:

data Counter a = forall self. NewCounter
    { _this    :: self
    , _inc     :: self -> self
    , _display :: self -> IO ()
    , tag      :: a
    }

С функциями, записанными со знаком подчёркивания мы не можем работать на прямую.
Правда работать с подобными объектами совсем не похоже на работу с ООП:

inc :: Counter a -> Counter a
inc (NewCounter x i d t) = NewCounter { _this = i x, _inc = i, _display = d, tag = t }

display :: Counter a -> IO ()
display NewCounter{ _this = x, _display = d } = d x

counterA :: Counter String
counterA = NewCounter { _this = 0, _inc = (1+), _display = print, tag = "A" }

counterB :: Counter String
counterB = NewCounter { _this = "", _inc = ('#':), _display = putStrLn, tag = "B" }

main = do
    display (inc counterA)         -- prints "1"
    display (inc (inc counterB))   -- prints "##"

Обобщённые Алгебраические Типы Данных (GADTs)

Обобщённые АТД отличаются от обычных тем, что урезают и специализируют итоговый тип.
В Хаскеле используется «функциональная» запись этих данных. Давайте перепишем простой тип данных в новом синтаксисе:

data Maybe a = Nothing | Just a

data Maybe a where
    Nothing ::      Maybe a
    Just    :: a -> Maybe a
-- --------------------
data List a = Nil | Cons a (List a)

data List a where
    Nil  ::                List a
    Cons :: a -> List a -> List a

Мы видим, что итоговый тип данных у всех совпадает: Maybe a (или List a). ОАТД позволяют иметь разные итоговые типы данных.
Если мы имеем абстрактное дерево:

  data Term a where
      Lit    :: Int -> Term Int
      Succ   :: Term Int -> Term Int
      IsZero :: Term Int -> Term Bool
      If     :: Term Bool -> Term a -> Term a -> Term a
      Pair   :: Term a -> Term b -> Term (a,b)

то легко построить функцию вычисления подобного дерева:

  eval :: Term a -> a
  eval (Lit i) 	= i
  eval (Succ t)     = 1 + eval t
  eval (IsZero t)   = eval t == 0
  eval (If b e1 e2) = if eval b then eval e1 else eval e2
  eval (Pair e1 e2) = (eval e1, eval e2)

Параметрические типы данных с ограниченными параметрами

Иногда уж больно хочется ограничить параметрические типы данных. Срезаются они ограничением вида(kind) типа.
Вид — по сути это тип типа, например

Just 3 :: (Maybe Int :: *)

А вот и данные с ограничением на параметр:

data F (a :: * -> *) where ...

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

Вывод

Алгебраические Типы Данных — очень простой, элегантный, легко расширяемый и мощный инструментарий создания пользовательских типов данных под очень многие нужды программистов.

Автор: Vitter

Источник