StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
primarykey
Id
9197803
data
AcceptedAnswerId
0
AnswerCount
0
ClosedDate
CommentCount
2
CommunityOwnedDate
CreationDate
2012-02-08T16:51:49.200
FavoriteCount
0
LastActivityDate
2012-02-08T19:58:28.297
LastEditDate
2012-02-08T19:58:28.297
LastEditorUserId
157360
OwnerUserId
157360
ParentId
9190352
PostTypeId
2
Score
125
ViewCount
0
LastEditorDisplayName
text
Body
Disclaimer: A lot of this doesn't really work quite right when you account for ⊥, so I'm going to blatantly disregard that for the sake of simplicity. A few initial points: <ul> <li>Note that "union" is probably not the best term for A+B here--that's specifically <a href="http://en.wikipedia.org/wiki/Disjoint_union" rel="noreferrer">a disjoint union</a> of the two types, because the two sides are distinguished even if their types are the same. For what it's worth, the more common term is simply "sum type".</li> <li>Singleton types are, effectively, all unit types. They behave identically under algebraic manipulations and, more importantly, the amount of information present is still preserved.</li> <li>You probably want a zero type as well. There isn't a standard one, but the most common name is <code>Void</code>. There are no values whose type is zero, just as there is one value whose type is one.</li> </ul> There's still one major operation missing here but I'll get back to that in a moment. As you've probably noticed, Haskell tends to borrow concepts from Category Theory, and all of the above has a very straightforward interpretation as such: <ul> <li>Given objects A and B in Hask, their product A×B is the unique (up to isomorphism) type that allows two projections fst : A×B → A and snd : A×B → B, where given any type C and functions f : C → A, g : C → B you can define the pairing f &&& g : C → A×B such that fst ∘ (f &&& g) = f and likewise for g. Parametricity guarantees the universal properties automatically and my less-than-subtle choice of names should give you the idea. The <code>(&&&)</code> operator is defined in <code>Control.Arrow</code>, by the way.</li> <li>The dual of the above is the coproduct A+B with injections inl : A → A+B and inr : B → A+B, where given any type C and functions f : A → C, g : B → C, you can define the copairing f ||| g : A+B → C such that the obvious equivalences hold. Again, parametricity guarantees most of the tricky parts automatically. In this case, the standard injections are simply <code>Left</code> and <code>Right</code> and the copairing is the function <code>either</code>.</li> </ul> Many of the properties of product and sum types can be derived from the above. Note that any singleton type is a terminal object of Hask and any empty type is an initial object. Returning to the aforementioned missing operation, in a <a href="http://en.wikipedia.org/wiki/Cartesian_closed_category" rel="noreferrer">cartesian closed category</a> you have <a href="http://en.wikipedia.org/wiki/Exponential_object" rel="noreferrer">exponential objects</a> that correspond to arrows of the category. Our arrows are functions, our objects are types with kind <code>*</code>, and the type <code>A -> B</code> indeed behaves as BA in the context of algebraic manipulation of types. If it's not obvious why this should hold, consider the type <code>Bool -> A</code>. With only two possible inputs, a function of that type is isomorphic to two values of type <code>A</code>, i.e. <code>(A, A)</code>. For <code>Maybe Bool -> A</code> we have three possible inputs, and so on. Also, observe that if we rephrase the copairing definition above to use algebraic notation, we get the identity CA × CB = CA+B. As for why this all makes sense--and in particular why your use of the power series expansion is justified--note that much of the above refers to the "inhabitants" of a type (i.e., distinct values having that type) in order to demonstrate the algebraic behavior. To make that perspective explicit: <ul> <li>The product type <code>(A, B)</code> represents a value each from <code>A</code> and <code>B</code>, taken independently. So for any fixed value <code>a :: A</code>, there is one value of type <code>(A, B)</code> for each inhabitant of <code>B</code>. This is of course the cartesian product, and the number of inhabitants of the product type is the product of the number of inhabitants of the factors.</li> <li>The sum type <code>Either A B</code> represents a value from either <code>A</code> or <code>B</code>, with the left and right branches distinguished. As mentioned earlier, this is a disjoint union, and the number of inhabitants of the sum type is the sum of the number of inhabitants of the summands.</li> <li>The exponential type <code>B -> A</code> represents a mapping from values of type <code>B</code> to values of type <code>A</code>. For any fixed argument <code>b :: B</code>, any value of <code>A</code> can be assigned to it; a value of type <code>B -> A</code> picks one such mapping for each input, which is equivalent to a product of as many copies of <code>A</code> as <code>B</code> has inhabitants, hence the exponentiation.</li> </ul> While it's tempting at first to treat types as sets, that doesn't actually work very well in this context--we have disjoint union rather than the standard union of sets, there's no obvious interpretation of intersection or many other set operations, and we don't usually care about set membership (leaving that to the type checker). On the other hand, the constructions above spend a lot of time talking about counting inhabitants, and enumerating the possible values of a type is a useful concept here. That quickly leads us to <a href="http://en.wikipedia.org/wiki/Enumerative_combinatorics" rel="noreferrer">enumerative combinatorics</a>, and if you consult the linked Wikipedia article you'll find that one of the first things it does is define "pairs" and "unions" in exactly the same sense as product and sum types by way of <a href="http://en.wikipedia.org/wiki/Generating_function" rel="noreferrer">generating functions</a>, then does the same for "sequences" that are identical to Haskell's lists using exactly the same technique you did. <hr> Edit: Oh, and here's a quick bonus that I think demonstrates the point strikingly. You mentioned in a comment that for a tree type <code>T = 1 + T^2</code> you can derive the identity <code>T^6 = 1</code>, which is clearly wrong. However, <code>T^7 = T</code> does hold, and a bijection between trees and seven-tuples of trees can be constructed directly, cf. <a href="http://www.math.lsa.umich.edu/~ablass/comb.html" rel="noreferrer">Andreas Blass's "Seven Trees in One"</a>. Edit×2: On the subject of the "derivative of a type" construction mentioned in other answers, you might also enjoy <a href="https://personal.cis.strath.ac.uk/~conor/Dissect.pdf" rel="noreferrer">this paper from the same author</a> which builds on the idea further, including notions of division and other interesting whatnot.
Tags
Title
singulars
PostAcceptedAnswerId
1. This table or related slice is empty.
PostParentId
1. POAbusing the algebra of algebraic data types - why does this work?
 singulars
 PostTypePostTypeId
 PTQuestion
PostTypePostTypeId
1. PTAnswer
UserLastEditorUserId
1. USC. A. McCann
UserOwnerUserId
1. USC. A. McCann
plurals
PostLinksPostIdRelatedPostId
1. This table or related slice is empty.
PostLinksRelatedPostIdPostId
1. This table or related slice is empty.
PostsAcceptedAnswerId
1. POAbusing the algebra of algebraic data types - why does this work?
 singulars
 PostTypePostTypeId
 PTQuestion
PostsParentIdCreationDate
1. This table or related slice is empty.
VotesPostIdCreationDate
1. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
2. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
3. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
CommentsPostId
1. COThis is a great explanation, particularly as a jumping-off point into things like http://strictlypositive.org/diff.pdf
 singulars
 PostPostId
 PO
 UserUserId
 USacfoltzer
2. CO@acfoltzer: Thanks! :] And yes, that's a great paper that develops these ideas. You know, I think at least 5% of my total reputation on SO can be attributed to "helping people understand one of Conor McBride's papers"...
 singulars
 PostPostId
 PO
 UserUserId
 USC. A. McCann

Querying!

Guidance

A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.