4 ms·
The algebra and calculus of algebraic data types (2015)
- saltysalt 2y agoThat is such a great website! Amazing content throughout.
- cvoss 2y agoI always love this topic. > Nat = 1 + Nat. This equation is clearly inconsistent, since x=1+x is false for all possible values of x. Ah, but no, my friend. That equation is false merely for all possible finite values of x. But why impose such a constraint? We've already been identifying a correspondence between certain types and the number of inhabitants they have. Nat has countably many inhabitants. And one more than countably infinite is countably infinite!
- empath75 2y agoYeah because aren't the numbers associated with the types related to cardinality?
- Infinity315 2y ago> Nat has countably many inhabitants. And one more than countably infinite is countably infinite! Two sets having the same cardinality (number of inhabitants) is insufficient to prove that two sets are equal. There is an additional condition that they all share the same elements. I read 1 + Nat as: map each element in the Naturals to its successor (i.e. Nat - {0}). 0 is in Nat, but 0 does not exist in "1 + Nat" since it got mapped to 1. This would be true if the set we were working with were the Integers instead of the Naturals.
- srcreigh 2y agoThis is incorrect.. the equation represents the number of elements in Nat based on its definition. Integers could be Int = Nat | Neg Nat. So Int = 2 * Nat. Your logic would presumably interpret this as even naturals.. but ya
- Infinity315 2y ago> Your logic would presumably interpret this as even naturals.. but ya My logic comes from a Math background. Take any Abstract Algebra class and this notation is common. For example: https://math.stackexchange.com/questions/1378174/how-to-denote-an-even-number-in-mathematics#:~:text=The%20integers.,set%20of%20all%20even%20numbers https://math.stackexchange.com/questions/1378174/how-to-deno.... To say the least I take numerous issues with the notation used, but I accept it. Since the integers and the naturals have the same cardinality, we have that Int = Nat.
- zdragnar 2y agoI'm always confused as to why people want to be able to do arithmetic with infinity. Infinity isn't a number. > countably infinite Countably infinite means you can count to any particular element of a set in finite time, even though there is no end to the pattern of elements in the set. You cannot count to infinity plus one in finite time.
- Smaug123 2y agoThat's not the attitude which leads to inventing the negative numbers, for example! The ordinals are useful and it's very reasonable to call them "numbers"; and I'm told that the surreal numbers are useful, although I've never actually used them.
- gnulinux 2y agoInfinity is not a number but transfinite numbers [1] like omega [2] or aleph-null [3] are. They are just as number as 0, 1, -5, 6/7, pi, i, or quaternion numbers. What is a "number" is not well-defined, any mathematical algebraic object can be called a number with some justification. Mathematicians just don't do it anymore, they just call it "X Algebra" instead of "X Numbers" but there is no fundamental distinction. From this perspective, arithmetic with infinity is not only possible but also extremely useful for Programming Language Theory, e.g. for Dependent Type Theory. [1] https://en.wikipedia.org/wiki/Transfinite_number https://en.wikipedia.org/wiki/Transfinite_number [2] https://en.wikipedia.org/wiki/Ordinal_number#Ordinals_extend_the_natural_numbers https://en.wikipedia.org/wiki/Ordinal_number#Ordinals_extend... [3] https://en.wikipedia.org/wiki/Aleph_number#Aleph-null https://en.wikipedia.org/wiki/Aleph_number#Aleph-null
- empath75 2y agoA set is "countably infinite" if you can construct a one to one mapping from the set to the natural (counting) numbers. The natural numbers are of course countably infinite, but so are even numbers, prime numbers, fractions, algebraic numbers and lots of other kinds of numbers that people want to do arithmetic with. "Uncountably infinite" sets can't be put into a one to one correspondence with the naturals, no matter how you produce to produce such a mapping, it's always possible to produce a number in the set which wasn't part of it. Real numbers being the prototypical example of that, but the power set (the set of all the subsets) of the naturals is, also. People do arithmetic with all kinds of things that "aren't numbers". Math isn't restricted to working with numbers.
- taeric 2y agoI am always torn when I see these discussions. Yes, I fully appreciate a lot of the easy algebra applies to some things. I further appreciate many of the optimizations that can be created by taking advantage of many of these. However, I have grown skeptical on its pedagogical use in programming. Specifically, I question if it is really how most people think in terms of programming. I further question if this is how most modelling considers things. An easy example would be chemistry. There are algebraic ideas in chemistry, but I would struggle to say how they look the same as this. Am I looking past an obvious aide to modelling that these approaches can give? I appreciate how this post acknowledges that there are not obvious uses of integration and such, but I feel that sort of proves my point. There are familiar mathematical tools that are good to use when we can. This does not mean you need to force them onto everything you have. It would probably help me a ton, if I ever saw these applied to state machines?
- marcosdumay 2y ago> Specifically, I question if it is really how most people think in terms of programming. No, of course not. Algebra is only useful when you want to manipulate that exact thing, and most programmers never do any complex manipulation of types. Compiler programmers writing powerful type systems do think that way. > There are algebraic ideas in chemistry, but I would struggle to say how they look the same as this. Oh no, they don't. The algebra of Quantum Mechanics is way weirder than that. (At least when you move after simple rotations and step-potential wheels.)
- taeric 2y agoJust to make sure I'm not misreading, this is largely an agreement? I think I'm fully in agreement that a compiler class should cover this. I will also hasten to say that I find it a fun topic, such that I don't think it should not be offered elsewhere. I just don't know that I can see a lot of application to general programming.
- marcosdumay 2y ago> I think I'm fully in agreement that a compiler class should cover this. Then yes, I agree with you.
- taliesinb 2y agoYes, this is a very cool story. But, fascinatingly, integration does in fact have a meaning. First, recall from the OP that d/dX List(X) = List(X) * List(X). You punched a hole in a list and you got two lists: the list to the left of the hole and the list to the right of the hole. Ok, so now define CrazyList(X) to be the anti-derivative of one list: d/dX CrazyList(X) = List(X). Then notice that punching a hole in a cyclic list does not cause it to fall apart into two lists, since the list to the left and to the right are the same list. CrazyList = CyclicList! Aka a ring buffer. There's a paper on this, apologies I can't find it right now. Maybe Alternkirch or a student of his. The true extent of this goes far beyond anything I imagined, this is really only the tip of a vast iceberg.
- ianandrich 2y agoI would be interested in reading more if you manage to find the paper(s).
- emmelaich 2y agoThis reminds me of a section from a category theory text that I encountered. It had similarly 'crazy' what-ifs, including one where the author used the quadratic formula and interpreted some meaning from it. It was a course only text, not distributed outside the university as far as I know.
- itishappy 2y ago> Can we extend the analogy to integration? Dumb idea: Unzipping? Differentiation takes as input the overall structure and extracts the behavior at a certain location. Integration takes the behavior at many different locations and returns a coherent picture of the overall structure. I'm struggling to picture the math. Does this work the way I envision?
- gwking 2y agoThis appears to have been published in 2015. Perhaps update the title with the year?
- dang 2y agoRelated: The algebra and calculus of algebraic data types - https://news.ycombinator.com/item?id=17942112 https://news.ycombinator.com/item?id=17942112 - Sept 2018 (48 comments) The Algebra of Algebraic data types - https://news.ycombinator.com/item?id=9775467 https://news.ycombinator.com/item?id=9775467 - June 2015 (40 comments)
- rramadass 2y agoFor people without some mathematical/language-relevant background, the following preliminaries would be useful; 1) A brief introduction to the Algebra of Types (nice intuitive explanation) - https://code.egym.de/a-brief-introduction-to-the-algebra-of-types-df92f0820e5 https://code.egym.de/a-brief-introduction-to-the-algebra-of-... 2) Algebraic data type - https://en.wikipedia.org/wiki/Algebraic_data_type https://en.wikipedia.org/wiki/Algebraic_data_type 3) Comparison of programming languages (algebraic data type) - https://en.wikipedia.org/wiki/Comparison_of_programming_languages_(algebraic_data_type) https://en.wikipedia.org/wiki/Comparison_of_programming_lang...
- sakras 2y ago> Let’s pause for a moment to remember that we’re dealing with types. And the expression 1 / (1 - a) contains both a negative and a fractional type, neither of which have a meaning yet. This makes me wonder, is there a ring of types? There's addition and multiplication. Division and subtraction aren't necessary to define a ring, so their absence isn't particularly surprising.
- eigenket 2y agoA ring forms an Abelian group with just its additive operation, so you basically have subtraction there. As far I can tell the structure we have formed by these datatypes is a semiring.
- sakras 2y agoAh also the multiplication operation isn't commutative, since struct { int A; float B; } is different from struct { float A; int B; }. So maybe it's a "noncommutative semiring".
- Sharlin 2y agoRing don’t require multiplication to commute, only addition. (Square) matrices make just fine rings despite noncommutativity. But the semiring of types does have commutative multiplication (only a semiring, or "rig", because the lack of additive inverses). Those two structs are equivalent (isomorphic) in the algebraic sense – names don’t matter, and order (indices are just a kind of names) doesn’t either. (a, b) = a x b = b x a = (b, a).
- eigenket 2y agoTechnically yeah but there is a natural isomorphism between struct { int A; float B; } and struct { float B; int A; } so if you're willing to do everything up to isomorphism (which is usually completely fine and standard) then you get a commutative semiring. You have to work up to isomorphism anyway even to get a noncomutative semiring because technically the multiplication isn't exactly associative only associative up to an isomorphism.