LINUX.ORG.RU

Вопрос по алгебраическим типам

 , ,


0

4

Почитал я тут немного теорию, вот отсюда:

http://fprog.ru/2009/issue2/roman-dushkin-algebraic-data-types/

С теоретической точки зрения алгебраическим типом данных является размеченное объединение множеств (иначе называемое «дизъюнктным объединением»)7, под которым понимается видоизменённая классическая операция объединения — такая операция приписывает каждому элементу нового множества метку (или индекс), по которой можно понять, из какого конкретно множества элемент попал в объединение.

не совсем понятен один момент. Если в объединении множеств присутствуют элементы, которые являются элементами многих множеств одновременно, то они должны содержать метки всех множеств, членами которых они являются? Если да, то как их можно пометить в случае, если элемент является элементом бесконечного числа множеств? Где можно увидеть пример такого объединения представленный в коде какого-нибудь ЯП?

Представление типов множествами это такая операция, к которой нужно подходить аккуратно (правда, я не уверен что могу объяснить почему). Ну да ладно, допустим, что тип == множество значений.

Теперь просто о множествах, безотносительно того, считаем ли мы их типами. Пусть есть совокупность множеств, проиндексированных множеством I: { A_i }_{i \in I}. Дизъюнктное объединение строится так: каждый элемент множества A_i — a \in A_i — превращается в пару (a, i) (или (i, a), неважно) и потом все эти пары сливаются в одно множество, которое мы и называем дизъюнктным объединением.

Это простейшая конструкция, которая реализует копроизведение в категории множеств.

utf8nowhere ★★ ()

Где можно увидеть пример такого объединения представленный в коде какого-нибудь ЯП?

В той же статье, не?

struct Tree {
    union {
        int value;
        struct {
            struct Tree *left;
            struct Tree *right;
        } branches;
    } data;
    enum { LEAF, NODE } selector;
};

Короче, variant это. А конструкторы это функции, которые заполняют поля данных.

xaizek ★★★★★ ()
{-|
  A value of type 'Dynamic' is an object encapsulated together with its type.

  A 'Dynamic' may only represent a monomorphic value; an attempt to
  create a value of type 'Dynamic' from a polymorphically-typed
  expression will result in an ambiguity error (see 'toDyn').

  'Show'ing a value of type 'Dynamic' returns a pretty-printed representation
  of the object\'s type; useful for debugging.
-}
data Dynamic = Dynamic TypeRep Any

пожалуйста.

P.S. я наврал про ограничение, мне казалось там Fingerprint а не TypeRep лежит.

qnikst ★★★★★ ()
Последнее исправление: qnikst (всего исправлений: 2)
Ответ на: комментарий от utf8nowhere

вот это I: { A_i }_{i \in I} предполагает просмотр в человеческом виде или нет? если препдолагает, то что поставить чтобы увидеть?

AndreyKl ★★★★★ ()
Ответ на: комментарий от AndreyKl

Не предполагает, т.к. для того, чтобы это отображалось в TeX так, как задумывалось, нужно записать как \{ A_i \}_{i \in I}

utf8nowhere ★★ ()

В Rust

enum MyType {
   Foo(SomeType1),
   Bar(SomeType2),
}

Deleted ()
Ответ на: комментарий от xaizek

не шарю в плюсах и паскалях, но variant разве может содержать разные, скажем, int?

  Int     Int
    \     /
     \   /
    [variant]
qnikst ★★★★★ ()
Ответ на: комментарий от xaizek

Короче, variant это

то есть, столько букв только для того, что в динамически-типизированных языках из коробки, и никто даже не задумывается о том, что это «фича»?

linearisation ()
Ответ на: комментарий от qnikst

Не знаю насчет variant, но в плюсах можно изобразить sum type, очень похожий на настоящий.

tailgunner ★★★★★ ()
Ответ на: комментарий от den73

Показали, что в категории множеств есть копроизведения, предъявив явную конструкцию этого копроизведения. Ну. Нестрого. Мне лень строго. И вообще.

utf8nowhere ★★ ()
Ответ на: комментарий от linearisation

Динамически типизированные языки это узкое подмножество статически типизированных. В статически типизированных языках ты можешь наделать себе каких угодно sum types.

А вот в динамически типизированном языке у тебя есть только один тип и он является sum type.

anonymous ()
Ответ на: комментарий от anonymous

в динамически типизированном языке у тебя есть только один тип

Почему? Или это Ваше личное предположение?

linearisation ()
Ответ на: комментарий от linearisation

в динамически типизированном языке у тебя есть только один тип

Почему?

А ты больше насчитал?

anonymous ()
Ответ на: комментарий от qnikst

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

xaizek ★★★★★ ()
Ответ на: комментарий от linearisation

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

Так что всё, что у тебя есть — это sum type из этих «примитивных типов» и тебе доступен только этот sum type, а «примитивные типы» явно недоступны.

anonymous ()
Ответ на: комментарий от linearisation

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

xaizek ★★★★★ ()
Ответ на: комментарий от anonymous

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

linearisation ()
Ответ на: комментарий от linearisation

Впрочем, тот факт, что написанием таких инструментов особо никто не заморачивается, говорит о том, что это никому не нужно, в массе.

Наличие статически типизированных языков говорит об обратном, а отсутствие «таких инструментов» (для динамических языков) может говорить только о том, что оно не нужно любителям динамики. Впрочем, и последнее не похоже на правду: ведь есть всякие TypeScript, да и в ряде динамических языков имеется возможность типы указывать.

DarkEld3r ★★★★★ ()
Ответ на: комментарий от DarkEld3r

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

linearisation ()
Ответ на: комментарий от linearisation

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

kek

anonymous ()
Ответ на: комментарий от xaizek

но формально тогда variant это не sum type. А ввот с тегами это уже ближе к требуемому.

qnikst ★★★★★ ()
Ответ на: комментарий от qnikst

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

xaizek ★★★★★ ()
Ответ на: комментарий от utf8nowhere

реализует копроизведение

Хорошее слово.
Копроизведение - это то, что реализовал (в этот раз) модератор Klymedy.

thesis ★★★★★ ()
Ответ на: комментарий от thesis

В Вики, даже в русскоязычной, по АТД есть отличная статья. В англоязычной отличные, простым языком написанные, статьи про юнионы, тегирование, сравнение по разным языкам и периодам, доходчивые объяснения. Теории завались, чего тут спорить. Любое тегированное объединение и есть АТД, состоявшееся еще в 60-х в АЛГОЛЕ.

anonymous ()
Ответ на: комментарий от anonymous

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

anonymous ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.