News for hackers. Stuff that matters.
Re:Where does the name "algebraic data type" come from? by marcosdumay on Wednesday July 31, 2024 @02:34PM (#41121938)
I really don't like this view (but looks like I'm a small minority).

Types shouldn't have an algebra similar to numbers, they should have an algebra similar to sets. While for numbers A + A + A = 3A, on sets A ∪ A ∪ A = A.

Types are all about predicate satisfaction, and predicates don't change their value because they can be proven in more than one way. In practice, defining type sums as tagged sums leads to your algebra, and also leads to a lot of confusion between structure and denomination that would be completely avoided if sums and tags were independent operations.

Re:Where does the name "algebraic data type" come from? by nine_k on Wednesday July 31, 2024 @04:04PM (#41122912)
It depends on what operations you pick. I like ML-style operations on types because they make set-theoretic sense.

C = A + B means that type C is a union of A and B, aka a "sum type", so its cardinality is the sum of cardinalities of A and B. In Typescript or Python terms, C = A | B, which I read that an element of type C can be either an element of A or an element of B.

C = A * B means that C is a Cartesian product of A and B, and its cardinality is the product of those of A and B. In Python terms, C = tuple[A, B]. Hence something like Point = {x: number, y: number, z: number} is not "3 * number", but number^3, because it's a point in the R^3 space.

Re:Where does the name "algebraic data type" come from? by marcosdumay on Wednesday July 31, 2024 @04:10PM (#41122950)
> C is a union of A and B, aka a "sum type", so its cardinality is the sum of cardinalities of A and B

That's exactly what's wrong. The cardinality is len(A ∪ B) = len(A) + len(B) - len(A ∩ B).

Also, the Cartesian product is a tagged operation. It literally creates a result where you access the elements by index.

Re:Where does the name "algebraic data type" come from? by nine_k on Wednesday July 31, 2024 @06:00PM (#41123935)
We reasonably assume that A ∩ B = ∅ in all practical cases, such as `int | None` or `string | number `, etc.

Yes, a Cartesian product is tagged (each axis is), but it does not affect the fact that len(A * B) = len(A) * len(B), hence it's logical to use multiplication to denote "record types".

Re:Where does the name "algebraic data type" come from? by marcosdumay on Wednesday July 31, 2024 @07:03PM (#41124459)
That's not a good assumption, and even the original example is Bool + Bool; len(Bool ∪ Bool) = 2 * len(Bool) is trivially false.

About the Cartesian product, the tags create that rule. Untagged multiplication again has fewer elements.

Re:Where does the name "algebraic data type" come from? by ajkjk on Wednesday July 31, 2024 @03:52PM (#41122816)
Here's a thought I have had cached in my head from a long time ago. Ignore me if this is obvious or dumb; I don't know anything about type theory really.

There are basically two varieties of types: predicate types and enumerated types. Predicate types are functions that return true for objects that have their type. Enumerated types in some way list all the values the type can have. So "Boolean" is an enumerated type, but "even integer" is a predicate type (you test if it's even. Nevermind that you could enumerate the even integers within your language, you wouldn't). (I'm pretty sure these varieties are dual in the category-theoretic sense of reversing arrows, but I don't know much about that either.)

So what happens is that the cardinalities of enumerated types obey arithmetic, but the cardinalities of predicate types do not. Predicate types only have a notion of "cardinality" anyway when you restrict the possible values to some finite universe. The intersection of two predicate types (x -> f(x) && g(x)) may be of the same cardinality as each of the predicates (if they are equal) or it might be the same cardinality as one of them (if f(x) implies g(x) then {x | f(x)} = {x | f(x) && g(x)}) or it might be some new value entirely.

All of the cases where algebra works on types is cases where they're being used as enumerated types. The usual definition of a list in functional languages ([] a = [] | a : [a] or w/e) enumerates the possibilities, hence it obeys algebra. Were it described as a predicate, on the other hand, it would not (necessarily) obey algebra.

Re:Where does the name "algebraic data type" come from? by feoren on Wednesday July 31, 2024 @06:15PM (#41124077)
I don't think a distinction between "predicate types" and "enumerated types" is particularly useful. As you pointed out, you can enumerate all even integers. All enumerated types can be represented as predicate types instead, with the predicate "does this belong to the enumerated set?". All countably infinite predicate types can be enumerated. So focusing on the difference seems like a red herring to me.

> All of the cases where algebra works on types is cases where they're being used as enumerated types.

No, algebra works perfectly fine "predicate types" as well, because all the predicate types we care about (constructible / countably infinite) are enumerable too.

> Predicate types only have a notion of "cardinality" anyway when you restrict the possible values to some finite universe.

No, there are infinite cardinalities.

Re:Where does the name "algebraic data type" come from? by ajkjk on Wednesday July 31, 2024 @11:34PM (#41125905)
I think you've misunderstood me. If the predicate types are enumerable then they're not predicate types, they're enumerated types. And if the enumeration turns out to be infinite then you get the algebra of infinite cardinals, not the algebra of numbers, which looks very different. But it still explains why they obey algebra.
Re:Where does the name "algebraic data type" come from? by kccqzy on Thursday August 01, 2024 @07:32AM (#41128111)
I don't understand you. Everything you can do on a computer is enumerable. So every type is enumerable. Then predicate types don't exist.

Infinite cardinals are not very useful when it comes to computers because there's only one infinite cardinal that's relevant: aleph-zero. All other infinite cardinals are beyond what computers can handle.

Re:Where does the name "algebraic data type" come from? by ajkjk on Thursday August 01, 2024 @02:47PM (#41132225)
I'm not talking about the notion of enumerable sets. I'm talking about whether a type explicit enumerates its members (like A = B | C or A = [] | [A]) or whether it is a contract which does not know how many members it has (like a class Foo, or a predicate like "lists of Foos" or just "even integers". You can do algebra on the former, including sometimes divergent-series style algebra like writing 1/(1-X) = 1 + X + X^2 + ...; you can't do algebra on the latter.

It doesn't matter that you could in principle enumerate the, say, the even integers, either finitely (since there are finite values in your chosen language) or infinitely (in the sense of having cardinality aleph-zero). It matters whether the type definition does that. If the definition of an even integer was `Even = [] | S^2(Even)` with S as the successor function, then it would fall in the first category and some algebra on the type would work (although it would be silly to do that).

Re:Where does the name "algebraic data type" come from? by feoren on Thursday August 01, 2024 @04:13PM (#41133094)
> I'm talking about whether a type explicit enumerates its members (like A = B | C or A = [] | [A]) or whether it is a contract which does not know how many members it has

And I'm asserting that this is an implementation detail that doesn't matter to type theory and would be unnecessary and distracting to think about.

> you can't do algebra on the latter.

Yes, you can. You can take sum types and cross products of the latter. You can use them as "type variables" in "type algebraic equations" That's what "doing algebra" on types means. Whether or not you

> It doesn't matter that you could in principle enumerate the [type] ... It matters whether the type definition does that.

This is the root of our disagreement. You should be able to replace the definition (implementation) of a type, e.g. "a list of the even integers between 0 and 100", with an equivalent definition (implementation), e.g. "all integers x such that x is even and x is between 0 and 100", and you type theory must not care. If your type theory cares about the exact implementation details of your type, it's hard to even call it a theory at all. From the point of view of any reasonable type theory, enumerated types and predicate types are interchangeable.

Question: take type X to be the cross product of some predicate type and some enumerated type. Is X enumerated or predicate? You've claimed they can't overlap. Which is it? A type theory that frets over this distinction is a bad type theory.

Imagine trying to categorize all your functions as either "bit-fiddling": those that use bit manipulation to calculate, and "arithmetic": those that use + - * / to calculate. Who cares? You can convert one to the other. You can do both at once. It's an implementation detail of your function and you should not be worrying about it.

Re:Where does the name "algebraic data type" come from? by ajkjk on Thursday August 01, 2024 @08:18PM (#41134996)
> take type X to be the cross product of some predicate type and some enumerated type. Is X enumerated or predicate? You've claimed they can't overlap.

A type like X = enum | predicate is enumerated, since it has two options that it explicitly lists, one of which happens to be a predicate.

> Yes, you can. You can take sum types and cross products of the latter.

You are talking about a different kind of algebra than I am, which should be pretty obvious from the context of this conversation. This was all in reply to somebody who was put off by the fact that you can do literal actual algebra on types, like L(A) = 1 + A * L(A) and then rearrange it into an infinite sum, and was saying that types ought to be obey something like set algebra instead, wherein A ∪ A = A. I am saying, the sense in which the former algebra works is due to the existence of types which enumerate their variants and therefore act like numbers (or, like, decategorify to numbers, or w/e).

Anyway, I understand that I am not well-versed in type-theory, but your thickheaded refusal to see my actual point and instead dismiss me with your confused counterpoints is just rude and unnecessary. Although I might be saying something in slightly incorrect terminology or missing something subtle, I'm not missing the non-subtle things you're saying and it should really not be hard to see the sense of what I'm getting at. So... cut it out, please.

Re:Where does the name "algebraic data type" come from? by feoren on Friday August 02, 2024 @03:44AM (#41136898)
You started by saying:

> Enumerated types in some way list all the values the type can have

And then said:

> X = enum | predicate is enumerated, since it has two options that it explicitly lists

But you can't list its values by your own definition. You defined types as being either A or B, and accepting that definition, you can come up with types that are neither. This is my point: your model is inconsistent. Your categorizations are not useful. You should not use that model. That is not a good way of thinking about the world.

>your thickheaded refusal to see my actual point and instead dismiss me with your confused counterpoints is just rude and unnecessary.

I honestly see myself as attempting to help you here. I see you making a mistake, and I'm trying to convince you, and to a lesser extent any other readers, not to make that mistake.

This has nothing to do with you using "wrong terminology" or not understanding type theory; I've accepted your definitions, and shown that they are inconsistent with themselves. Your math doesn't work. Your model is not helpful. The fact that you cannot define tuples of (enum, predicate) as either enum or predicate by your own definition shows that your model fails. Don't use it. Move on. Dismissing you is not rude nor unnecessary. It is highly necessary that we dismiss each others' ideas when those ideas don't work.

I get that that sounds harsh. It's great to come up with interesting ideas and categorizations. It's even better to throw them away when you realize they don't work. Do that seven thousand more times. Six thousand, nine hundred and eighty seven of them will be thrown away. The 13 remaining ones will be worth it. But you'll never get there if you cling to ones that are provably wrong. This one is. From my point of view, you are the one being thickheaded here, by clinging to this one idea as if it's the only one you'll ever have. It's not. I strongly urge you to get better at killing your own ideas to make room for new ones. Accept proofs that your ideas are wrong as improvements in your knowledge.

Re:Where does the name "algebraic data type" come from? by ajkjk on Wednesday August 07, 2024 @04:40PM (#41185244)
> From my point of view, you are the one being thickheaded here, by clinging to this one idea as if it's the only one you'll ever have.

It's just that you and I haven't yet talked about my idea yet, because you're talking about something else, then failing to realize it and thinking I'm ignoring your rebuttals because I'm stubborn rather than because they're irrelevant to my point.

Anyway I will try one more time for posterity:

> But you can't list its values by your own definition.

You have misunderstood me. The X I have described enumerates its values in the sense I am talking about: it's one or the other, type A (and enum) or B (a predicate). I am talking about it being enumerated _in terms of other things_. If for some reason you had X = A | B, as a definition, and then you the cardinalities of A or B, then you would be able to say |X| = |A| + |B| (or |A| + |B| - |A ∩ B| if they overlap). This is the sense in which algebra works. That is just... obviously true, right?

The interesting parts show up if you have recursive definitions (in which case you get these infinite series) or if some of the sets have cardinalities that you don't know how to use for algebra (like a predicate over an un-enumerable set of values...) ... but in some cases algebra still works, and I don't know the details about that.

In the case of "predicate" types, it is much harder to see how arithmetic would work in the cardinalities, because I could write down something like Prime = x: integer & isPrime(x) and regardless of how you think about |Integer| in your language/setting/etc, you have a complex predicate over integers that's not going to correspond to any obvious algebra. And yet if I wrote Q = Prime | true | false you can still say that |Q| = |P| + 2 and that works fine. On the other hand if I wrote Q = Prime | Fibonacci then good luck because Prime ∩ Fibonacci is hard to do anything with.

Re:Where does the name "algebraic data type" come from? by kccqzy on Wednesday July 31, 2024 @06:37PM (#41124258)
When you have "predicate types" in practice you need restrictions on what kind of predicates are allowed. If you allow anything at all, that's when you get Russell's paradox. That tells us the general comprehension principle is invalid, that is, you cannot allow the construction of a set from an arbitrary predicate (or definite condition).

> Predicate types only have a notion of "cardinality" anyway when you restrict the possible values to some finite universe.

It is much more subtle than that. Regular set theory allows cardinalities far bigger than the least infinite cardinal, aleph-zero. But of course it's computers that we are talking about. Even then it's wrong. What if I define a predicate that's returns true for every natural number? Then it's infinite. But what if I define a complicated enough predicate that it does not halt for some numbers? Then we get back a recursively enumerable set that may or may not be infinite. In essence, when you introduce predicates, you no longer really care about cardinalities you start to care about the complexity of the predicates.

For your purpose, your predicate has to be sufficiently simple that it denotes a recursive set (not a recursively enumerable set).

Re:Where does the name "algebraic data type" come from? by ajkjk on Wednesday July 31, 2024 @11:37PM (#41125920)
As a predicate Russell's paradox translates to an infinite loop in programming, not an impossibility. And yes, you get in trouble if you define a set from an arbitrary predicate, but a type is not (necessarily) a set: a type can be a predicate without asking that it be explicitly cast as a set. You can certainly consider the "set of all lists", but you can't enumerate it, because you can have a list of any type and you don't know all the types that can be put into a list.

Anyway, I feel like you missed my point. It's that, if you are wondering why types seem to obey algebra but ALSO obey the laws of set theory and the two seem compatible, that this is why: predicates obey the algebra of sets while enumerated types have cardinalities which obey algebra.

Re:Where does the name "algebraic data type" come from? by paholg on Wednesday July 31, 2024 @03:00PM (#41122281)
The difference is mostly a matter of perspective, isn't it?

In Rust, if I have

``` enum Foo { A(u32), B(u32), C(u32), } ```

Then the number of representable states is deduced my an "algebra of numbers", but the size is deduced by an "algebra of sets".

For example, the size of Foo is just 8 (4 bytes for u32, and 4 for the tag + alignment).

Re:Where does the name "algebraic data type" come from? by marcosdumay on Wednesday July 31, 2024 @03:09PM (#41122366)
Given the types: I = A + B; J = C; X = A; Y = B + C

Is I + J the same type as X + Y?

If your types are tagged, they aren't. Because that's what tags do.

Re:Where does the name "algebraic data type" come from? by paholg on Wednesday July 31, 2024 @03:44PM (#41122729)
Okay? I don't know what point you're making.
Re:Where does the name "algebraic data type" come from? by bombela on Wednesday July 31, 2024 @11:11PM (#41125817)
My answer would be: No they are not the same type. Yes they have the same amount of bits representing them. They might have different RAM usage because of alignment.
Re:Where does the name "algebraic data type" come from? by xigoi on Thursday August 01, 2024 @03:00AM (#41126787)
> Is I + J the same type as X + Y?

They are not the same, but they are isomorphic. Just like with (A×B)×C versus A×(B×C).

Re:Where does the name "algebraic data type" come from? by ndriscoll on Wednesday July 31, 2024 @05:00PM (#41123410)
The "correct" (in the categorical sense) sum operation for sets is disjoint (tagged) union, not union. So A + A + A = A ∐ A ∐ A, which is isomorphic to 3*A = (3,A) (i.e. each element of A ∐ A ∐ A carries the information of a tag from 3 and an element of A). All is well.
Re:Where does the name "algebraic data type" come from? by syrak on Wednesday July 31, 2024 @05:48PM (#41123827)
IMO your view, if not common, is kinda intuitive from the point of view of someone trained in set theory/classical logic (i.e., most people before they find an interest in type theory; I myself was here a few years ago). If it feels like you're in a minority, it's because most others who might have the same opinion haven't reached the point where they could articulate it; many just give up way earlier on understanding type theory.

It certainly makes sense to a set theorist that union and intersection are more primitive than sums and products. From that perspective, type theory seems like a roundabout and unnecessary way of doing things.

The challenge is to imagine type theory as a radically different foundation to logic (because that's what it is), with sums and products as primitives instead, for one superficial difference.

It's hard to explain in words. I personally didn't get it without years of first-hand experience with proof assistants based on type theory. Constructivism and category theory are other possible gateways into the right mindset.

There is one key difference which I think highlights the charm and simplicity of type theory without delving in technical details too much. The syntax of set theory is in two layers: there are sets, and there are propositions (about elements of those sets). In contrast, there is only one such "layer" in (dependent) type theory: types.

Types play the role of both sets and propositions if you want to encode set theory in type theory. The point is that types can be much more than either of those things, and that idea is inherently difficult to convey to someone whose only conception of logic is sets and propositions.

Re:Where does the name "algebraic data type" come from? by kccqzy on Wednesday July 31, 2024 @06:28PM (#41124196)
You are not wrong but you are indeed a minority. If you read research papers you will definitely find papers that use union in the way you describe (when it comes to subtyping), and then use a different notation for record extension (basically the kind of discriminated union operator). It's essential to differentiate between them using different notations. For the former, for example the Animal class and the Cat class are unioned into the Animal superclass. For the latter, you have an Animal object and a Cat object that's separate.