Sum Types in Julia and Rust
andreaskroepelin.de
andreaskroepelin.de
I was expecting union types (e.g., https://www.typescriptlang.org/docs/handbook/unions-and-inte... or https://dotty.epfl.ch/docs/reference/new-types/union-types.h... )
I guess enums are a type of sum type, but seems this is more specifically about enums
Language designers: stop changing the meanings of words! I know you mean well and you're trying to tie unfamiliar ideas to familiar ones for beginners, but you end up causing more confusion for everyone in the long run.
enum Colour {
Red,
Blue,
Green,
}
#[derive(Debug)]
enum Colour {
Red = 1,
Blue = 2,
Green = 4,
}
fn main() {
println!("{:?}", Colour::Blue);
println!("{}", Colour::Blue as u8);
}In other languages the concept might correspond to (finite) recursively enumerable sets (ie you can list all their elements).
Rust calls them enum to be familiar to people coming from C-family languages, which is a large target.
> since as you noted that term already had a well-established meaning in other languages
Rust enums "degenerate" to a C-style enum (except typesafe) as it can be repr'd to a number and it's possible to select the discriminant (if there's no associated data).
> the concept that Rust calls "enums" also had several existing names (sum type, coproduct type, disjoint union, and, more generally, algebraic data type) in the literature and in prior languages.
Pretty much none of which are actually part of the language e.g. in Haskell or OCaml the designator is `type`, and it's used for both sum types and product types: the sum type simply has a single constructor.
But Rust doesn't use `type`, it uses `struct`. And a `struct` with multiple variants doesn't make sense.
> the sum type simply has a single constructor.
this should be "product" not "sum"
i.e.
https://play.rust-lang.org/?version=stable&mode=debug&editio...
In the example you gave, the type-of `left` is still `SumType::Left` instead of being just `String`.
I'm not too familiar with Rust to say, but I don't consider this to be a syntactically zero-cost abstraction (even if the wrapper-types are elided by the compiler) because we still have more keyboard typing to do than we should be doing, imo.
1. A union type is like int | double. It means the value is one of a set of possible types. And it's a true set: `int | int | double` is indistinguishable from `int | double`.
2. A sum type is a new type built from a list of other types, which assigns a 'tag' to each possible list element, like a Rust enum. The tags are not themselves types: they are like a struct field name. It's quite possible to have a sum type with N tags, each wrapping `int`.
So with this understanding Rust has sum types but not union types, while TypeScript has union types but not sum types.
type Maybe<T> =
| { kind: "Some", value: T }
| { kind: "None" }Recently there has also been a lot of discussion [2] about possibly adding anonymous enums to the language, and whether these should have sum or union semantics.
[1]https://doc.rust-lang.org/reference/items/unions.html
[2]https://internals.rust-lang.org/t/ideas-around-anonymous-enu...
> Two common classes of algebraic types are product types (i.e., tuples and records) and sum types (i.e., tagged or disjoint unions, coproduct types or variant types).
Edit: e.g. X | Y isn't so different from 'a' A | 'b' B
Except for the fact that the union of a type with itself (X | X) doesn't add any extra values, while a tagged union can have distinct tags with the same data type ('a' A | 'b' A) and actually sums the possible values for each tag. They are equivalent only so long as the unions are disjoint with no overlap between the members.
"In computer science, a tagged union, also called a variant, variant record, choice type, discriminated union, disjoint union, sum type or coproduct, ..."
More specifically sum types in Rust must also be tagged, meaning you need to explicitly construct and deconstruct them. This aspect is along the type-alias vs newtype axis which gets into structural vs nominative typing and the trade-offs therein.
So yes, Rust enums and Typescript union types are both exactly sum-types and the differences are due to the surrounding decisions made about the languages. Rust's sum types are named and tagged, Typescript's are anonymous and untagged, but they're both sum types.
As others have pointed out, untagged unions are not sum types because the union of a type with itself has no effect, whereas adding a type to itself yields twice as many possible values. Untagged unions can function as sum types when there is no overlap between the members, but not in the general case.
To illustrate the difference: You can construct every possible algebraic type as some combination of void (no values), unit (one value), sum (|A + B| = |A| + |B|), and product (|A * B| = |A| * |B|). This does not work if the sum type is replaced with an untagged union. You can't even get as far as constructing the equivalent of the boolean type; while |Unit + Unit| has two distinct values, |Unit ⋃ Unit| only has one value.
It is.
> I was expecting union types (e.g., https://www.typescriptlang.org/docs/handbook/unions-and-inte.... or https://dotty.epfl.ch/docs/reference/new-types/union-types.h.... )
Union types are basically an anonymous form of sum types. In the same way tuples and structs / records are both forms of product types.
Statically typed languages which support sum types generally only support the named version (because it tends to be more useful and powerful).
> I guess enums are a type of sum type, but seems this is more specifically about enums
Depends on the language, C's enums are not types at all, Java's or C++'s are product types. Technically enums (or more generally tagged unions, which is what Rust's enums are) is a superset of sum types as you can have multiple variants of the same type, but that's not leveraged here.
This is false on multiple levels. First, being a sum type has nothing to do with the type being named vs. anonymous. What makes a sum type a sum type is that it's a categorical coproduct, whether you give it a name or not. Second, sum types are synonymous with _disjoint_ (i.e., tagged) unions, not unions. Consider the union of boolean with itself. The result would be equivalent to boolean, because union is an idempotent operation. Disjoint union, or sum, would give you a type with 4 values instead of 2.
> Technically enums (or more generally tagged unions, which is what Rust's enums are) is a superset of sum types as you can have multiple variants of the same type
That just how sum types work (have you ever wondered why they are called "sum" in the first place?). You're thinking of union types.
enum Sum<A, B> {
Inl(A),
Inr(B),
}
Sol = Inl . Inl
Pol = Inl . Inr
Cent = Inr . Inr
A union type "A | B" means "a value of type A or a value of type B". Example:
function f1(): String | Integer {
if (rand()) {
return "hello"
} else {
return 12
}
}
function f2(x: String | Integer) {
switch (typeof x) {
case String: return "string: " + x
case Integer: return "integer: " + x
}
}
A tagged union (aka sum type) "A + B" means "either a left value or a right value; if it's the left, it has type A, if it's the right it has type B".
function g1(): String + Integer {
if (rand()) {
return Inl("hello")
} else {
return Inr("bye")
}
}
function g2(x: String + String) {
switch (x) {
case Inl(s): return "left value: " + x
case Inr(s): return "right value: " + x
}
}
I would use enums in Julia, making the enum you define a field of the PlayerClass:
@enum PlayerStar Sol Pol Cent
struct PlayerClass
star::PlayerStar
# other fields
end
But if your code is performance sensitive, I'm more comfortable controlling the behavior than relying on these optimizations. The problem is, dispatch is often a more convenient coding style than long branches.
fn greet<T: Player>(&self, other: &T);
fn greet(&self, other: Box<dyn Player>);edit - Alright I think I see what the original article was trying to express. In the original article that top example method was defined as part of a trait. Because that method is generic that would make the trait not object safe. On its own that is fine (this would still compile), but there was some previous example code which relied on this trait being object safe.
fn greet(&self, other: &dyn Player);For this problem, I would use union types in Julia. Union types are a sort of sum, but they are amalgamated sums whilst sums types in PL semantics usually means disjoint sums. The difference is that disjoint sums 'mark' whether a value is of the left or right type, while with amalgamated sums the value may belong unmarked to the intersection. The distinction does not matter in the example the post gives.
Second, Julia does not give the benefit that Rust gives of type coverage, that is, ensuring that functions that take the sum type as argument actually are defined for each branch of the sum type. The Rust compiler guarantees this automatically. AFAICS, with Julia it is up to the user to provide tests exploring the branches.
Julia is a compiled language and Rust is too. Julia is dynamically typed while Rust is statically typed.
[0] https://ahsmart.com/pub/holy-traits-design-patterns-and-best...
This extensibility from the outside is the most important idea behind Julia!
For example this is why a generic deep learning library doesn't need any extra implementation details to be able to run on GPU as well. https://fluxml.ai/Flux.jl/stable/gpu/
If you do that, then anyone writing the code must add code to handle other cases, or it's a compile error (i.e. you must match the enum as:
#[non_exhaustive]
enum Foo {
CaseA,
CaseB
}
let f : Foo = get_foo();
match foo {
CaseA => {},
CaseB => {},
// Exhaustive matching
_ => {},
}
It's different than if you were implementing those methods on a trait and just had several types that implemented the trait. But the article does show the potential complications that sometimes arise with Rust traits.
The difference is that a trait is "open" and an enum is "closed". So the enum's methods can/must account for all variants. A trait method calls to the implementor for work, much like inheritance in other languages.
My question is just - do people really accept this tradeoff? The Rust advice in the article seems to create a maintenance burden compared to the Julia version. Every time you want to extend the system you have to go back and crack open old code. Is the performance difference really that great? Is this really the default approach for Rust programmers? Not snarking about Rust at all, I'm fascinated, but the open-closed principle would be front of mind for me when deciding on these sorts of abstractions (both as a language designer and just a developer).
If you want something open for extension, use a trait unless you can prove to yourself that you "can't". If it's closed or unlikely to be extended, use an enum.
Think of it this way: In Rust you have a choice between open and closed (trait vs enum). In Java, you get open (interface) and that's it. Other languages do also have both, like Rust: Swift, Kotlin, apparently Julia.
Traits have a few sharp edges because of the nature of Rust being built around zero-cost abstractions. But, most of the time, they work just like an interface in Java. The snag I most often hit is if one wants to return Self in a trait method. The most obvious way to work around that, IIRC, is to just return a Box<dyn MyTrait>. Keep in mind that in many languages, these things actually work similarly except that the language will just happily throw stuff on the heap transparently. Rust requires you to acknowledge that the former case needs to be boxed and likely on the heap, since you can't know its size at compile time.
In this particular case of extending an enum, I don't see it nearly as horrible as you're describing it. Let's look at it from the POV of another implementation in another language (I don't know Julia): You have an interface, Player. That interface defines a couple of methods. You implement three classes that conform to that interface. Now, six months later you come back and want to add a fourth. You make a new class, say that it implements Player and then your IDE/compiler yells at you until you implement those methods. In the Rust-enum version, you have an enum with three variants and a couple of methods, each of which has to match on the variants. Six months later, you want to add a fourth PlayerClass variant. So, you add it and then your compiler yells at you until you implement the fourth match branch in the couple of methods on the class.
That doesn't seem that different.
To answer some of your inner questions: Yes, Rust devs reach for enums a lot. But really only if you don't expect the cases to change much. Writing version 1.0 in Rust usually takes longer than in other languages because Rust is still a low-level language. Rust's performance advantage doesn't matter for most applications. People choose Rust for much more than the performance: its error philosophy, its enums and good matching, etc.
The place where this ends up happening most is around error handling. Crafting your public error types in Rust is an art form. Usually in Rust libraries, errors are implemented in enums. So whoever calls your API can see that it failed and then can match on the reasons it may have failed (or just wrap it in their own error type and bubble it up). If you're not careful, you can cause breaking changes in your API by doing something as simple as changing a dependency (your dep's concrete error type was wrapped inside one of your error variants).
I have somewhat mixed feelings on it, but Rust does allow us to mark enums with a special annotation that forces all matches on it to include a wildcard match (even if it matches all current variants explicitly). It is generally considered good practice to mark your error enums with said annotation so that you can add failure modes in the future without requiring a major version bump for just an extra error case. One could use the same annotation for any enum, of course.
The sum of a type with m possible values and a type with n possible values has (m+n) possible values, the product of a type with m possible values and a type with n possible values has (m×n) possible values, a sequence of n items of a type with m possible values has m^n possible values.