<p>I'm trying to fully understand all of Haskell's concepts.</p>

<p>In what ways are algebraic data types similar to generic types, e.g., in C# and Java? And how are they different? What's so algebraic about them anyway? </p>

<p>I'm familiar with universal algebra and its rings and fields, but I only have a vague idea of how Haskell's types work.</p>

[{'answer_id': 16810, 'author': 'olliej', 'author_id': 784, 'author_profile': 'https://Stackoverflow.com/users/784', 'pm_score': 6, 'selected': True, 'text': '<p>"Algebraic Data Types" in Haskell support <em>full parametric polymorphism</em>, which is the more technically correct name for generics, as a simple example the list data type:</p>\n\n<pre><code> data List a = Cons a (List a) | Nil\n</code></pre>\n\n<p>Is equivalent (as much as is possible, and ignoring non-strict evaluation, etc) to</p>\n\n<pre><code> class List&lt;a&gt; {\n     class Cons : List&lt;a&gt; {\n         a head;\n         List&lt;a&gt; tail;\n     }\n     class Nil : List&lt;a&gt; {}\n }\n</code></pre>\n\n<p>Of course Haskell\'s type system allows more ... interesting use of type parameters but this is just a simple example.  With regards to the "Algebraic Type" name, i\'ve honestly never been entirely sure of the exact reason for them being named that, but have assumed that it\'s due the mathematical underpinnings of the type system.  I <em>believe</em> that the reason boils down to the theoretical definition of an ADT being the "product of a set of constructors", however it\'s been a couple of years since i escaped university so i can no longer remember the specifics.</p>\n\n<p>[Edit: Thanks to Chris Conway for pointing out my foolish error, ADT are of course sum types, the constructors providing the product/tuple of fields]</p>\n'}, {'answer_id': 16825, 'author': 'Timbo', 'author_id': 1810, 'author_profile': 'https://Stackoverflow.com/users/1810', 'pm_score': 0, 'selected': False, 'text': '<p>For me, the concept of Haskell\'s algebraic data types always looked like polymorphism in OO-languages like C#.</p>\n\n<p>Look at the example from <a href="http://en.wikipedia.org/wiki/Algebraic_data_types" rel="nofollow noreferrer">http://en.wikipedia.org/wiki/Algebraic_data_types</a>:</p>\n\n<pre><code>data Tree = Empty \n          | Leaf Int \n          | Node Tree Tree\n</code></pre>\n\n<p>This could be implemented in C# as a TreeNode base class, with a derived Leaf class and a derived TreeNodeWithChildren class, and if you want even a derived EmptyNode class.</p>\n\n<p>(OK I know, nobody would ever do that, but at least you could do it.)</p>\n'}, {'answer_id': 16933, 'author': 'Chris Conway', 'author_id': 1412, 'author_profile': 'https://Stackoverflow.com/users/1412', 'pm_score': 3, 'selected': False, 'text': '<p>Haskell\'s datatypes are called "algebraic" because of their connection to <a href="http://en.wikipedia.org/wiki/Initial_algebra" rel="noreferrer">categorical initial algebras</a>. But that way lies madness.</p>\n\n<p>@olliej: ADTs are actually "sum" types. Tuples are products.</p>\n'}, {'answer_id': 35758, 'author': 'Jared Updike', 'author_id': 2543, 'author_profile': 'https://Stackoverflow.com/users/2543', 'pm_score': 2, 'selected': False, 'text': '<p>@Timbo:</p>\n\n<p>You are basically right about it being sort of like an abstract Tree class with three derived classes (Empty, Leaf, and Node), but you would also need to enforce the guarantee that some one using your Tree class can never add any new derived classes, since the strategy for using the Tree datat type is to write code that switches at runtime based on the type of each element in the tree (and adding new derived types would break existing code). You can sort of imagine this getting nasty in C# or C++, but in Haskell, ML, and OCaml, this is central to the language design and syntax so coding style supports it in a much more convenient manner, via pattern matching.</p>\n\n<p>ADT (sum types) are also sort of like <a href="http://en.wikipedia.org/wiki/Tagged_union" rel="nofollow noreferrer">tagged unions</a> or <a href="http://en.wikipedia.org/wiki/Variant_type" rel="nofollow noreferrer">variant types</a> in C or C++.</p>\n'}, {'answer_id': 382467, 'author': 'ja.', 'author_id': 15467, 'author_profile': 'https://Stackoverflow.com/users/15467', 'pm_score': 2, 'selected': False, 'text': "<p>old question, but no one's mentioned nullability, which is an important aspect of Algebraic Data Types, perhaps the most important aspect.  Since each value most be one of alternatives, exhaustive case-based pattern matching is possible.  </p>\n"}, {'answer_id': 644674, 'author': 'starblue', 'author_id': 49246, 'author_profile': 'https://Stackoverflow.com/users/49246', 'pm_score': 4, 'selected': False, 'text': '<p>In <a href="http://en.wikipedia.org/wiki/Universal_algebra" rel="noreferrer">universal algebra</a> \nan <i>algebra</i> consists of some sets of elements\n(think of each set as the set of values of a type)\nand some operations, which map elements to elements.</p>\n\n<p>For example, suppose you have a type of "list elements" and a\ntype of "lists".  As operations you have the "empty list", which is a 0-argument\nfunction returning a "list", and a "cons" function which takes two arguments,\na "list element" and a "list", and produce a "list".</p>\n\n<p>At this point there are many algebras that fit the description,\nas two undesirable things may happen:</p>\n\n<ul>\n<li><p>There could be elements in the "list" set which cannot be built\nfrom the "empty list" and the "cons operation", so-called "junk".\nThis could be lists starting from some element that fell from the sky,\nor loops without a beginning, or infinite lists.</p></li>\n<li><p>The results of "cons" applied to different arguments could be equal,\ne.g. consing an element to a non-empty list\ncould be equal to the empty list.  This is sometimes called "confusion".</p></li>\n</ul>\n\n<p>An algebra which has neither of these undesirable properties is called\n<i>initial</i>, and this is the intended meaning of the abstract data type.</p>\n\n<p>The name initial derives from the property that there is exactly\none homomorphism from the initial algebra to any given algebra.\nEssentially you can evaluate the value of a list by applying the operations\nin the other algebra, and the result is well-defined.</p>\n\n<p>It gets more complicated for polymorphic types ...</p>\n'}, {'answer_id': 648959, 'author': 'porges', 'author_id': 10311, 'author_profile': 'https://Stackoverflow.com/users/10311', 'pm_score': 4, 'selected': False, 'text': '<p>A simple reason why they are called algebraic; there are both sum (logical disjunction) and product (logical conjunction) types. A sum type is a discriminated union, e.g:</p>\n\n<pre><code>data Bool = False | True\n</code></pre>\n\n<p>A product type is a type with multiple parameters:</p>\n\n<pre><code>data Pair a b = Pair a b\n</code></pre>\n\n<p>In O\'Caml "product" is made more explicit:</p>\n\n<pre><code>type \'a \'b pair = Pair of \'a * \'b\n</code></pre>\n'}, {'answer_id': 5917133, 'author': 'Don Stewart', 'author_id': 83805, 'author_profile': 'https://Stackoverflow.com/users/83805', 'pm_score': 7, 'selected': False, 'text': '<p>Haskell\'s <em>algebraic data types</em> are named such since they correspond to an <em>initial algebra</em> in category theory, giving us some laws, some operations and some symbols to manipulate. We may even use algebraic notation for describing regular data structures, where:</p>\n<ul>\n<li><code>+</code> represents sum types (disjoint unions, e.g. <code>Either</code>).</li>\n<li><code>•</code> represents product types (e.g. structs or tuples)</li>\n<li><code>X</code> for the singleton type (e.g. <code>data X a = X a</code>)</li>\n<li><code>1</code> for the unit type <code>()</code></li>\n<li>and <em><code>μ</code></em> for the least fixed point (e.g. recursive types), usually implicit.</li>\n</ul>\n<p>with some additional notation:</p>\n<ul>\n<li><code>X²</code> for <code>X•X</code></li>\n</ul>\n<p>In fact, you might say (following Brent Yorgey) that a Haskell data type is regular if it can be expressed in terms of <code>1</code>, <code>X</code>, <code>+</code>, <code>•</code>, and a least ﬁxed point.</p>\n<p>With this notation, we can concisely describe many regular data structures:</p>\n<ul>\n<li><p>Units: <code>data () = ()</code></p>\n<p><code>1</code></p>\n</li>\n<li><p>Options: <code>data Maybe a = Nothing | Just a</code></p>\n<p><code>1 + X</code></p>\n</li>\n<li><p>Lists: <code>data [a] = [] | a : [a]</code></p>\n<p><code>L = 1+X•L</code></p>\n</li>\n<li><p>Binary trees: <code>data BTree a = Empty | Node a (BTree a) (BTree a)</code></p>\n<p><code>B = 1 + X•B²</code></p>\n</li>\n</ul>\n<p>Other operations hold (taken from Brent Yorgey\'s paper, listed in the references):</p>\n<ul>\n<li><p>Expansion: unfolding the fix point can be helpful for thinking about lists. <code>L = 1 + X + X² + X³ + ...</code> (that is, lists are either empty, or they have one element, or two elements, or three, or ...)</p>\n</li>\n<li><p>Composition, <code>◦</code>, given types <code>F</code> and <code>G</code>, the composition <code>F ◦ G</code> is a type which builds “F-structures made out of G-structures” (e.g. <code>R = X • (L ◦ R)</code> ,where <code>L</code> is lists, is a rose tree.</p>\n</li>\n<li><p>Differentiation, the derivative of a data type D (given as D\') is the type of D-structures with a single “hole”, that is, a distinguished location not containing any data. That amazingly satisfy the same rules as for differentiation in calculus:</p>\n<p><code>1′ = 0</code></p>\n<p><code>X′ = 1</code></p>\n<p><code>(F + G)′ = F\' + G′</code></p>\n<p><code>(F • G)′ = F • G′ + F′ • G</code></p>\n<p><code>(F ◦ G)′ = (F′ ◦ G) • G′</code></p>\n</li>\n</ul>\n<hr />\n<p><em>References:</em></p>\n<ul>\n<li><a href="http://www.cis.upenn.edu/%7Ebyorgey/papers/species-pearl.pdf" rel="noreferrer">Species and Functors and Types</a>, Oh My!, Brent A. Yorgey, Haskell’10, September 30, 2010, Baltimore, Maryland, USA</li>\n<li><a href="http://personal.cis.strath.ac.uk/%7Econor/Dissect.pdf" rel="noreferrer">Clowns to the left of me, jokers to the right (Dissecting Data Structures)</a>, Conor McBride POPL 2008</li>\n</ul>\n'}]
['https://Stackoverflow.com/questions/16770', 'https://Stackoverflow.com', 'https://Stackoverflow.com/users/1659/']