алгебраический тип данных - это struct?

Смотрю в википедию, отличий не нахожу

Ты правда не видишь отличий product types и sum types?

Tagged union

https://www.youtube.com/watch?v=w1WMykh7AxA

В общем, дочитал до конца, и все стало ясно. Если тип находится в хаскеле, значит он алгебраический

В языке Haskell любой тип данных, который не является примитивным, является алгебраическим

http://dem-dem.ru/OD/ftvcik0bwx1.jpg

Ну то есть только и отличий - что tagged?

Структура может включать в себя поле типа union или enum.

Иногда в тебе есть смысл.

Это довольно жирное отличие.

Да. АТД можно эмулировать на структурах с юнионами, это не новость.

Смысл тут в том, что именно размеченные объединения обладают определенными важными свойствами. По-этому под АТД понимается то, что понимается.

Ты правда не видишь отличий product types и sum types?

Структура может включать в себя поле типа union или enum.

Не стоит тебе начинать с таких сложных вещей. Рассмотри product из int и float, потом sum из них же. Возможно, разница станет понятной.

Одно свойство размеченного объединения - то, что можно тип узнать. Оно важное, не спорю. В Си прямо так на уровне типов это выразить нельзя, но в лиспе можно. Какие ещё есть важные свойства?

Ты исходишь из ложной гипотезы, что я не понимаю отличия между product и sum.

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

Что выразить нельзя и что можно?

В Common Lisp даже pattern matching нет искаропки, а ведь удобство ADT не в последнюю очередь связано с PM

Одно свойство размеченного объединения - то, что можно тип узнать. Оно важное, не спорю.

Нет, важное свойство то, что размеченные объединения двойственны структурам, а обычные - нет.

pattern matching - это инструмент, а не свойство типа данных, как такового. Представим себе, что он есть.

Дальше что?

неразмеченный union вообще не является типом - ты просто в принципе не знаешь, что в нём хранится, эту информацию нужно как-то отдельно хранить. Вот это и нельзя выразить - тип данных. В лиспе если у тебя есть два непересекающихся типа a и b, то ты можешь создать тип (or a b) и я пока не вижу чем он отличается от sum type.

PM - это код, изоморфный данным.

Представим себе, что он есть.

О да, в CL все есть, только еще не реализовано.

Я знаю что такое PM. Кроме PM, ещё какой-то профит есть? Мне вот интересно, это прямая ложь или что?

https://www.schoolofhaskell.com/user/Gabriel439/sum-types

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

изоморфный

чёёёёёёё

чо, триггернуло?

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

< то ты можешь создать тип (or a b) и я пока не вижу чем он отличается от sum type.

Рассмотри пример, где a = b. сразу поймешь, чем отличается (a or a = a, a + a != a).

Я же тебе сказал, атд такие какие есть, потому что эта конструкция обладает «хорошими» свойствами с теоретической точки зрения. Про нее можно доказывать разные хорошие теоремы ит анализировать при помощи развитого матаппарата. При замене размеченных объединений обычными все силньо ломается.

ну а так да, только не структ а юнион.

Какие конкретно хорошие теоремы? Надеюсь, ты не обидишься, если я попрошу их объяснить на пальцах :)

Хорошо, ограничения ок. И всё?

ну, с алгебраичискими типами данных можно делать вот такие вот фокусы

если ты знаешь что a * (b + c) = a * b + a * c и если у тебя тип (a, Either b c) то это значит что твой тип то же самое что тип Either (a, b) (a, c)

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

ну и как уже упоминалось, паттерн матчинг, без которого как без рук просто

вот так ещё вот

a^b * a^c = a^(b + c)
(b -> a, c -> a) = Either b c -> a

вот так ещё вот

А что с (a + b)^c делать? 😲😲😲

c -> Either a b ?

или я не понял вопроса?

Хочу бином Ньютона.

ахх...

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

(defstruct Апельсин-или-яблоко-с-меткой
  (Метка 'Апельсин :type (member Апельсин Яблоко))
  (Значение (Вырастить-апельсин) :type (or Апельсин Яблоко)))

я, если оставить в стороне пропаганду, положа руку на сердце не сказал бы, что в Хаскеле «есть» эти типы а в Си «нет»

Это потому, что Википедия говорит о «algebraic data types as a first class notion», а ты о «я могу сделать ADT из говна и палок».

Вот что говорит stackoverflow относительно понятия «first class»:

http://stackoverflow.com/questions/646794/what-is-a-first-class-programming-c...

«As you can see, it's a definite grey area :)»

Т.е. пока что ты не освободил свою речь от пропаганды.

http://stackoverflow.com/questions/646794/what-is-a-first-class-programming-c...
«As you can see, it's a definite grey area :)»

Начни отсюда: http://stackoverflow.com/questions/646794/what-is-a-first-class-programming-c...

Ну и вообще - если уж учишься по stackoverflow, то хотя бы читай не только ответ, помеченный зеленой птичкой.

Т.е. пока что ты не освободил свою речь от пропаганды.

Просто ты не отличаешь случай «поддержка $FEATURE встроена в ЯП» и «$FEATURE может быть выражена средствами языка».

Просто ты всё время строишь неадекватные предположения обо мне. Достал уже.

положа руку на сердце я бы поддержал тейлганнера: по моему ты не отличаешь «встроена» и «может быть выражена»

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

чем тогда обычный ассоциативный массив в php не сум тайм? если городить из говна и палок, действительно, то всё сум тайп. одна проблема с этим сум тайпом - пока нагородишь, весь в говне поперепачкаешься. ну или перчатки надо по уши натягивать.

Просто ты не отличаешь случай «поддержка $FEATURE встроена в ЯП» и «$FEATURE может быть выражена средствами языка».

Ога. И тут надо напомнить топикстартеру про тьюринг-полноту. Поэтому выражать $FEATURE он может хоть на брейнфаке.

В общем, всем спасибо за ответы.

Для меня сухой остаток такой:

• Product type - запись (рекорд, структура)
• Tagged union (который иногда называют Sum Type, но это плохое название) - это union.

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

В большинстве ЯП АДТ есть (вопреки пропаганде хаскелеводов). Я не знаю точно, но догадываюсь, что единственное, чем Хаскель реально выделяется - так это контролем связи между тегом и значением в tagged union на уровне компилятора. Ещё есть pattern matching, но это уже совсем ортогонально и не будем об этом.

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

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

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

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

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

Поэтому да, я предвзят отноительно Хаскеля. Но дело не в этом. Я честно пытаюсь понять, что даёт АДТ для практики, с той точки зрения, нужно ли включать их в планы для включения в ЯП, к-рый я создаю.

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

Один профит я понял - контроль связи между тегом и содержимым. Но явно мне это никто не сказал - мне говорили о «хороших свойствах» и т.п. Мутность мышления, неясные посулы без конкретики с декларацией превосходства, в которое я должен поверить - это тоже из сектоводтсва.

Но допустим, такой контроль есть. Конкретно: есть некая конструкция «разобрать все случаи тега типа». Внутри каждой клаузы компилятор обругается на использование значения, не соответствующего тегу. А также он опционально обругается, если я рассмотрел не все теги. Это понятный профит и думаю, что он есть в Хаскеле.

Это реальный профит. Для справки отмечу, что здесь есть сходство с наследованием и я нашёл одну статью об имитации АДТ с помощью наследования (правда, там были и дефекты).

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

Аминь.

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

Algebraic data types were introduced in Hope, a small functional programming language developed in the 1970s at Edinburgh University.

Окай.

Паттерн матчинг и рассуждения о типах.

По моему про паттерн матчинг тебе ленивый не сказал только. Просто когда человека спрашивают «профит» он сразу про паттерн матчинг, ибо реальный профит. А ты это требуешь в форме «контроль связи между тегом и содержимым». Я ж тебе сразу сказал - проверка компилятором. Нес па? А без этого пишешь кучу мутных функций руками. Ты не доволен. Может ты просто немного не владеешь терминологией? Коли ты уж спрашиваешь про сум тайп то очевидно что ответ прилетит в виде «алгебра типов » и «паттерн матчинг», а не в виде «контроль за содержимым тегов». Если хочешь услышать «контроль за содержимым тегов», мне кажется надо спросить «какой смысл теггировать юнионы в си». вот тут да, «контроль за содержимым типов» (ну, если ручками наговняешь из палок этот контроль, конечно, то да, и то с оговорками)

Я в принципе-то доволен, спасибо за твои ответы. Паттерн матчинг я просто отложил в сторону ввиду его ортогональности, да и второстепенности.

Паттерн-матчинг - это не просто удобство, а единственный (?) способ сохранить статичную типобезопасность ADT. Без него вообще нет смысла говорить что в языке есть ADT, ибо нет самой алгебры.

лиспер

Для меня сухой остаток такой:

Product type - запись (рекорд, структура)
Tagged union (который иногда называют Sum Type, но это плохое название) - это union.

jeezus christ, у лисперов всегда такая каша в голове? Есть теоретико-категорные понятия произведения и суммы (копроизведения) объектов, а объекты, которые являются произведениями или суммами объектов называем product object и sum object. Когда у нас есть категория в которой объекты это типы, то тогда говорим о product type и sum type. :-)

Записи, структуры и прочие tagged union — это конкретные способы реализации product или sum type. :-)

В большинстве ЯП АДТ есть (вопреки пропаганде хаскелеводов).

Haskell это категория Hask, где объектами являются типы Хаскеля, а морфизмами — функции Хаскеля. И известно, что там есть произведения и суммы типов. Поэтому мы можем говорить о наличии АДТ. :-)

Как можно говорить о том, что в ЯП есть АДТ, если для этих «большинства ЯП» не определена категория типов? :-)

«встроена» и «может быть выражена»

Хорошо когда может быть выражена(в тч синтаксически). Когда встроена — не всегда хорошо.

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

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