A tagged union is a specific kind of data structure. It essentially refers to a pair of information: the first is a tag and the second is the union. The union might represent many different kinds of values. The important bit is that the size of that memory is the size of the largest value. The tag then tells you what kind of value is in that memory, and crucially, tells you how to interpret that memory. Getting this wrong, for example, in a language like C can lead to undefined behavior.
Tagged unions show up in all sorts of places. The classical example is an AST. You usually have one "node" type that can be one of many possible things: a literal, a binary operation, a function call, a type definition, whatever. And for any non-primitive node, it usually has pointers to children. And what is the type of a child? Well, a "node"! It's a recursive data type. It lets you represent children as just more nodes, and those nodes might be any other AST node. (And as you might imagine, an AST can be quite a bit more complicated than this. You often want restrictions on which types of children are allowed in certain contexts, and so you wind up with many different tagged unions.)
The use of a tagged union like this can be conceptually thought of as a sum type. A sum type is not a data structure. A sum type is a concept. It comes from type theory and it is the "dual" of product types. Product types represent the conjunction of values while sum types represent the disjunction of values. In type theory notation, you usually see 'A x B x C' to refer to the product type of A, B and C. Similarly, you usually see 'A + B + C' to refer to the sum type of A, B or C.
A sum type can be represented by just about anything, because it's just a concept. You can take something that is typically used for product types and use it to present an API that gives you a sum type:
type OptionInt struct {
exists bool // private
number int // private
}
func OptionIntNone() OptionInt {
return OptionInt{false, 0}
}
func OptionIntSome(number int) OptionInt {
return OptionInt{true, number}
}
func (o OptionInt) IsSome() bool {
return o.exists
}
func (o OptionInt) Number() int {
if !o.exists {
panic("option is none, no number available")
}
return o.number
}
This is a very contrived and hamstrung example, because it really doesn't give you much. But what it does give you is the API of a sum type. It is a value that can be either missing or present with an integer. Notably, it does not rely on any particular integer sentinel to indicate whether the value is missing or not. It encodes that state separately. So it can fully represent the presence of any integer value.As you can see, despite it offering an API that represents the sum type concept, it is actually implemented in terms of a product type, or a struct in this case.
In a language like Go, which does not really support either unions or sum types, this sort of API is really hamfisted. In particular, one could object that it is a sum type because it doesn't really represent the "sum typeness" in the type system. Namely, if you get its use wrong, then you don't get a compilation error. That is, you can call the 'Number()' method without checking whether 'IsSome()' returns true or not. In other words, correct use of OptionInt looks like this:
var opt OptionInt := doSomethingThatMightReturnNone()
if opt.IsSome() {
// OK, safe to access Number. It won't panic
// because we just checked that IsSome() is true.
fmt.Println(opt.Number())
}
But nothing in Go stops you from writing this instead: var opt OptionInt := doSomethingThatMightReturnNone()
fmt.Println(opt.Number())
This is why "support for sum types" is critical for making them as useful as they can be. In Rust, that same option type is defined like this: enum OptionInt {
None,
Some(i32),
}
That's it. The language gives you the rest. And crucially, instead of splitting out the 'IsSome()' check and the access via 'Number()', they are coupled together to make it impossible to get wrong. So the above code for getting a number out looks like this instead: let opt: OptionInt = do_something_that_might_return_none()
if let OptionInt::Some(number) = opt {
println!("{}", number);
}
You can't get at the 'number' without doing the pattern matching. The language won't let you. Now, you can define methods on your sum types that behave like Go's 'Number()' method above and panic when the value isn't what you expect. And indeed, Rust's Option and Result types provide this routine under the names 'unwrap()' and 'expect()'. But the point here isn't just about Option and Result, it's about sum types in general. And you don't have to define those methods that might panic. You can just let the language help guide you along instead.Sum types are an idea. A concept. A technique. Tagged unions are an implementation strategy.
Notice also that I haven't mentioned exhaustiveness at all here. It isn't required for sum types. Haskell, for example, doesn't mind at all if your pattern matching isn't exhaustive. You actually have to tell it to warn you about it, and even then, it's not a compilation error unless you treat it as one. In Rust, exhaustiveness checking is enabled by default for all sum types. But you can disable it for a particular sum type with the '#[non_exhaustive]' attribute. The benefit of disabling it is that adding a new variant is possibly semver compatible change, where as adding a new variant in an exhaustive sum type is definitely a semver incompatible change.
I’m not sure this is the best description of what `#[non_exhaustive]` does in Rust. It doesn’t so much disable exhaustiveness checking as it marks the given list of variants as incomplete.
In Rust, some pattern matching contexts are required to be exhaustive (e.g. ‘let pattern = …;’, ‘match … {}’), and others are not (e.g. ‘if let … = … {}’). When an enum is tagged as ‘#[non_exhaustive]’, the former are required to include a wildcard matcher that will accept unknown variants, even if all known variants are explicitly matched.
Rust also allows structs to be `#[non_exhaustive]` to mark that the listed fields might not be sufficient. This disables the ability to (outside of a privacy boundary) directly construct an instance of the structure, or to destructure it with an exhaustive pattern.
Basically, we're talking past each other. I called it out for what it does, but you're pointing out why someone would want to use it. That is, "#[non_exhaustive] on enums indicates that the list of variants is incomplete, and it does this by disabling exhaustiveness checking outside of the crate in which it is defined." Although, of course, not even that is precisely correct. Because your match arms are still forced to be technically exhaustive via the compiler requiring a wildcard arm. But the end effect to the user of the enum is that exhaustiveness checking on the variants of the enum is disabled.
Slightly unrelated, but re
> More to the point, the Wikipedia article for "sum type" redirects to "tagged union," which just honestly makes this more of a mess
I often see Wikipedia articles in CS topics severely lacking, or claiming exact definitions, when no such thing exists. Many definitions we regularly use are not exact at all, different papers/books use them differently, e.g. how would you even define OOP, low-level languages, etc? I would prefer them to use less strong language, as too many people argue on the internet based on Wikipedia definitions.
It happens on other wikis too, like the Arch wiki.
I realize it's a tired complaint that a lot of people have and editors don't have an easy job, but I am so completely done with contributing to wikis. I know a lot of other people with the same complaint and same conclusion, including experts in the domain of type theory. One wonders whether this is one of the reasons why the articles are not as good as they could be.
This is how you'd do it in Java.
Cons(1, Cons(2, Cons(3, Nil)))Here is a definition for a Maybe type, converting it to a List is left as an exercise to the reader :) : https://news.ycombinator.com/item?id=35133670
enum SumType {
Foo(foo),
Bar(bar),
Baz(baz),
}
void DoSomething(SumType sum_type) {
match sum_type {
Foo(foo): foo.do_x();
Bar(bar): bar.do_y();
Baz(baz): baz.do_z();
}
}
This could be lowered to: struct LoweredSumType {
optional<Foo> foo;
optional<Bar> bar;
optional<Baz> baz;
}
void DoSomething(LoweredSumType sum_type) {
if (sum_type.foo.has_value()) {
sum_type.foo->do_x();
} else if (sum_type.bar.has_value()) {
sum_type.bar->do_y();
} else {
sum_type.baz->do_z();
}
}
This isn't real code; it's a pretend language that's kind of a mix of Rust and C++. But it illustrates that the sum type can be lowered into a non-union representation.which looks remarkably like a union to me, if i understand your made-up language.