Алгебраические типы данных и их использование в программировании

[lionet]

Алгебраические типы данных и их использование в программировании

Роман Душкин

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

Comments

[thedeemon]

Еще стоил упоминания вопрос пересечения наборов конструкторов разных типов. Polymorphic variants и связанные с ними штуки.

[nponeccop]

пересечения наборов конструкторов разных типов??

[thedeemon]

Именно!
В Хаскелле этого нету? Ну хоть чего-то. :)

[nponeccop]

Их там нету из-за особенности алгоритма вывода типов. Вряд ли стоило перегружать этим статью.

[thedeemon]

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

[nponeccop]

То, что написали Вы - чушь. Хоть и можно догадаться, что вы имели ввиду, в статье стоит написать другое, чтобы читатель не гадал.

Типы Maybe Int и Maybe Char - разные, хотя и пересекаются по конструкторам.

[thedeemon]

Да, плохо выразился.
Я про такой вопрос: если у нас есть data Maybe a = Nothing | Just a, можем ли мы определить тип data AnotherBool = Nothing | Something ?

[antilamer]

Нет, т.к. тогда у терма Nothing не будет существовать "наиболее общего типа" (most general type), что противоречит идеям системы типов Haskell.

[nponeccop]

Не совсем так. Идеи допускать одинаковые имена полей обсуждались в haskell-cafe, и принципиальных возражений не было, только усложнение вывода типов и то, что после изменения некоторые валидные программы станут невалидными, т.к. выводильщик типов с ними не справится.

А в Хаскеле что, до сих пор есть principal typing??

[nponeccop]

Это как раз понятно. Но чтобы грамотно без примеров объяснить это, уйдет пара абзацев, что перегрузит статью.

[os80]

А что значит
data Maybe a = Nothing | Just a
"в отрыве" от монад? Т. е. что означают подобные конструкции сами по себе?

[antilamer]

Это алгебраический тип (algebraic data type); охрененно полезная фича в абсолютно всех известных мне областях программирования (полезность АДТ можно сравнить с полезностью, например, массивов или структур), см. википедию, haskell wikibooks и т.п.

Re:

[os80]

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

Re:

[nponeccop]

Ну, там довольно по-дурацки написано.

lionet в соседнем топике написал примерно. в переводе на С++ запись data a = Nothing | Maybe a означает:

template
class Maybe
{
enum { tagMaybe, tagNothing } tag;
tag t;
union {
void mNothing;
struct {
a anon_m1;
}
}
public:
a getMaybe();
void getNothing();
bool isMaybe();
bool isNothing();
void setMaybe(a);
void setNothing(void);
}

[lionet]

В данном случае определён полиморфный тип данных Maybe. Который может либо обозначать отсутствие данных (Nothing), либо обозначать присутствие данных какого-то конкретного типа a (Just a).

Думай о нём, как о контейнере опционального значения. Либо содержит, либо не содержит.

Эта конкретная штука моделирует такие вещи, как вызов функции, которая может дать результат, а может не дать.

Причём, другие функции могут и не знать, какой результат возвращается: они могут уметь работать с любыми данными, "обёрнутыми" в Maybe. Например, превращать списки Maybe a в с писки a:

catMaybes :: [Maybe a] -> [a]

В этом случае, эта функция объединит список [Just 3, Just 4, Nothing, Just 7] в [3, 4, 7], ничего не подозревая о типе Maybe Int.

[nponeccop]

Ну как же "ничего не подозревая". Функция, ничего не подозревающая о типе, была бы

const :: a -> b или id :: a -> a