The lack of sum types should really be considered a weird omission rather than a strange fancy language feature. I suspect that their omission from popular languages is mostly due to the historical belief that object-orientation was the way forward and that "everything is an object", leading many programmers to represent things that are decidedly not objects using abstractions designed for objects. An object is a stateful thing which exists over a period of time (sometimes unbounded) and whose identity is characterized by its observable behavior. Abstractions for objects consist of interfaces which expose only a slice of the observable behavior to consumers. On the other hand, a value is really just that; a value. It does not have state, it does not start or stop existing, and its identity is defined only by its attributes. You can use objects to model values (poorly), but you often end up doing a lot of extra work to stop your "fake value" objects from behaving like objects, e.g. by being careful to make all fields immutable and implementing proper deep equality. Abstractions for values are not naturally expressed using interfaces because interfaces force the implementation to be tied to the instance of an object, but since values do not have a lifetime this restriction is a huge disadvantage and often leads to clunky and inflexible abstractions. For example, consider the Comparable interface in Java which tells you that an object is modeling a value which can be compared to other values of the same type. It would be awfully nice if List<A> could implement this interface, but it cannot because doing so will mean that you can only create lists of things (of some type A) which have a total order defined on them.

However, if you consider programming to not only be about expressing what you can do to stateful objects but also expressing values and their operations, then algebraic data types and traits/modules/type classes become the natural basic vocabulary as opposed to classes and interfaces. When dealing with first-order algebraic data types, products (i.e. records) and coproducts (i.e. sum types) are unavoidable. A list is one of the simplest algebraic data types which use both products and coproducts:

data List a = Nil | Cons a (List a)

One trait of lists is that lists of totally ordered things are themselves totally ordered using lexicographic ordering, and this is in Haskell expressed as a type class instance

instance Ord a => Ord (List a) where ...

Crucially, the type class is removed from the definition of what a list is, which enables us to still talk about lists of e.g. functions which do not have an order on them. These lists do not have the Ord trait, but they are still lists.

Another important distinction between traits and interfaces is that some behavior of value types consist of simply identifying special values. For example, the Monoid type class in Haskell is

    typeclass Monoid a where
      mempty :: a
      mappend :: a -> a -> a

Many languages now have proper support for both objects and values in that they have better primitives for defining both products and coproducts, but I still think that most mainstream languages are missing proper primitives for defining traits.

I wonder why sum types are named like that. They are not the sum of their possible states in a way that I would recognize, more like an exclusive-or or one of out many. At some point I came up with an explanation, but I forgot it again. If you need to explain why something is simple, it's not simple.

Sum type sounds like the old Variant from VB.

We use something similar in Solvespace. Where one might have used polymorphism, there is one class with a type enum and a bunch of members that can be used for different things depending on the type. Definitely some disadvantages (what does valA hold in this type?) but also some advantages from the consistency.

This tradeoff sounds similar to the choice to use "tagged types" versus "variant records" in Ada. Ada has provided variant records since 1983 and tagged types since 1995 (and both with a very nice syntax).

No?

I think you're confusing ADT with a Typescript-like type system. Adding language support for ADT is not really a warrant for an "enough DOF to become scary" sticker.

I find modern Java surprisingly pretty good at capturing the essence of ADT without introducing way too much fancy stuff. Modern Java supports ADT via `sealed` classes (sum types) and `record` (product types). For working with ADT classes, modern Java provides exhaustive `switch` expression and `record` destructuring.

That's enough for minimal "language ADT support". You still can't do Typescript's wacky operations like conditional / mapped types or type parameter recursion in Java. You can't do fancy Haskell's typeclasses here either. And it is certainly not turning Java's type system into a Turing-complete type system at all.

Algebraic types, by themselves, don't do anything to make things "scary" or Turing-complete. Even C has (sort of) a weak, limited form of algebraic types through structs and unions. Zod, which you linked to as an example of the "simple, fixed, runtime types" you're advocating for supports discriminated unions too.

ADTs don't give your type system Turing completeness.

Also acting like Turing complete type systems are scary is more FUD than reality. If it becomes relevant it's because you are choosing to do recursion in some sort of constraint solver the type system provides.

I strongly agree. Algebraic types aren't "scary," but "algebraic types" is a bad term for what they are. In all popular languages that support "sum types" we just call them "unions."

Your favorite programming language probably already supports unions, including Python, TypeScript, Kotlin, Swift, PHP, Rust, C, and C++. C# is getting unions next year.

The article never mentions the word "union," which is overwhelmingly more likely to be the term the reader is acquainted with. It mentions "sets" only at the start, preferring the more obscure terms "sum types" and "product types."

A union of type sets kinda like a sum, but calling it a "sum" obscures what you're doing with it, rather than revealing. The "sum" is the sum of possible values in the union, but all of the most important types (numbers, arrays, strings) already have an absurdly large number of possible values, so computing the actual number of possible values is a pointless exercise, and a distraction from the union set.

Stop trying to make "algebraic" happen. It's not going to happen.

I always thought "algebraic" sounds unscary because in high school / undergraduate, algebra feels easier than analysis. Now, "analytic data types", that would be something.

I think the term "algebra" is nice and neutral, common ground from grade school through college mathematics and higher, and I think it's a good clue for someone who doesn't have much math background. "You know how you learned to do math operations on numbers, and then in algebra class you learned to do them on other things like variables and equations? You can do operations on types as well."

It's inevitable that someone starting from zero like this needs some time to get used to the ideas. Nobody learns this stuff instantly. Even if they can read an explanation in ten minutes and understand every word of it, it still takes time for the ideas to sink in and become natural. That's why an undergraduate math course might only cover a couple hundred pages in a semester. For someone not used to the process of absorbing ideas like these, the time it takes can be confusing and disappointing, but it's normal.

I think one point of confusion that could be avoided is that areas of math that are initially taught as separate topics often get freely mixed in introductory explanations of type theory. For example, someone who is exposed to a little bit of set theory in one class, and a little bit of logic in another, probably thinks of these things as separate from each other and both separate from algebra. But then an explanation like this confuses them by freely interchanging "union" and "sum" and the operator "|" which programmers learn as logical "or." Ideally, I think an introduction should stick to a single set of terminology from one area (I would pick set theory) at first, and after the student is comfortable with the concepts and operations, only then show how the other terminology maps to the ideas the student has learned.

> their arcane set of arbitrary numbers and if they can be considered a field or ring or a group or everything at the same time.

A toolbag of abstract theory and tools that can be straightforwardly applied to any "arcane set" is the value that upgrading from arithmetic to algebra provides.

Void in Haskell is not the same thing as `void` in C, C++, Java or similar languages. If you return `Void` in Haskell, you will get a runtime error but `void` returning functions in C-like languages don't fail. It's not a type that doesn't have any value, rather it's a type that has a single value (normal return). Therefore it's more similar to `unit`.

That's the point I tried to make. All my bachelor education there was no single mention of sum types even though we learned about the visitor pattern. Instead of having to model sum types with object hierarchies, the language should provide a straightforward way to represent them since it's a very basic concept. I think that while things have improved a lot compared to past, sum types concept is still not known as much as objects for instance. Today all mainstream languages added direct support for sum types but awareness of it lacks.

They are not "just structs and tagged unions". The language support that enforces safe usage is not optional.

And OOP is just subtyping and visibility modifiers too! /j

The main problem with ADT is language support for them. Primarily sum types, as they're missing in a lot of major PLs, while product types are "just" structs or classes.

Without language support, you can simulate them via brittle workarounds like `if (d.isTypeA()) return d.methodA()`.

Actually, I agree, it is mundane. That's exactly why it's kind of becoming an itch for anyone used to ADT, you'll feel like you're missing a basic building block.

Just imagine if all languages removed `struct`-like and `class`-like construct. Something like Brainfuck esolang or any plain asm. It certainly possible to create arbitrary complex program in those languages. But would you pick `struct`-less language over language that supports it natively?

any, extends, unknown and infer.

What algebraic operations do they correspond to?

Where are the sum and product types in this, exactly?