1
$\begingroup$

If you have two product types A×B×C and D×E×F you can construct a new type A×B×C×D×E×F. In typescript (structural typing) this is called intersection &. Should this operation be called something different in nominally typed languages? (since the intersection of different nominal types is empty)

If you have two sum types A+B+C and D+E+F you can construct a new type A+B+C+D+E+F. In typescript (structural typing) this is called union |.

Do any languages have built in support for these operations? (aside for golang (product types only) and typescript)

In C you can always do

struct A;
struct B;
struct C { A a; B b; };

In rust you can do

enum EnumA {
    VariantA1,
    VariantA2,
}
enum EnumB {
    VariantB1,
    VariantB2,
}
enum CombinedEnum {
    A(EnumA),
    B(EnumB),
}

However, this doesn't take advantage of the weak associativity of product and sum types i.e. (A×B)×(C×D)=A×B×C×D, but you get stuck working with (A×B)×(C×D). What languages allow you to take advantage of this associativity? What should this be called? For example Golang allows you to do struct embedding

type TypeA struct {
    PropertyA string
}
type TypeB struct {
    PropertyB int
}
type CombinedType struct {
    TypeA
    TypeB
}

It was pointed out that typescript's & does not really a product operator, neither is typescript's | really a sum operator.

$\endgroup$
9
  • 3
    $\begingroup$ You might enjoy reading Types and Programming Languages - there are several sections that walk through different implementations of products and sums, from both a nominal viewpoint and a structural viewpoint. $\endgroup$
    – apropos
    Commented Jun 24 at 3:37
  • 3
    $\begingroup$ Notice that TypeScript's intersection types are not product types at all. Compare A×A to A&A $\endgroup$
    – Bergi
    Commented Jun 24 at 15:44
  • 2
    $\begingroup$ Typescript's intersection types (&) are not product types, and its union types (|) are not sum types. Notably, T & T and T | T are equal to T, but these are not generally true of product or sum types. It's also not generally true that an intersection of nominal types is empty, e.g. Serializable & Cloneable in Java. $\endgroup$
    – kaya3
    Commented Jun 24 at 18:05
  • 1
    $\begingroup$ It's worth noting that mathematically, the Cartesian product × is not literally associative according to its set-theoretic definition, but there is an easy bijection between the products A×(B×C) and (A×B)×C, so nobody ever really cares about the formal difference, and we write A×B×C and tuples like (a, b, c) because everybody agrees it is a better notation than always writing (a, (b, c)). Likewise, the disjoint union of sets is not literally associative based on its definition, but mathematically it's often convenient to abuse notation and pretend it is. $\endgroup$
    – kaya3
    Commented Jun 24 at 18:22
  • 4
    $\begingroup$ Was it ChatGPT that said Typescript's & is a product type, or | is a sum type? Do yourself a favour, and don't ask ChatGPT this kind of thing. $\endgroup$
    – kaya3
    Commented Jun 24 at 21:48

2 Answers 2

4
$\begingroup$

This is somewhat possible in OOP languages that have both sealed interfaces and "records" (AKA "data classes", "case classes"), such as Java 21, Scala, and Kotlin. The caveat is that you must own all of the types, i.e. they can't be in a dependency or standard library, or you will have to make wrappers to put them in the union or intersection.

For example, let's say you have the following "algebraic data types" (example is Kotlin, but Scala and Java can do the same with different syntax):

sealed interface Currency {
    data class US(val dollars: Int, val cents: Int) : Currency
    data class CAD(val dollars: Int, val cents: Int) : Currency
    data class BTC(val bitcoins: Float) : Currency
}

sealed interface Length {
    data class US(val miles: Int, val feet: Int, val inches: Int, val centimeters: Float) : Length
    data class Euro(val meters: Float) : Length
}

To define a union, define a sealed interface that is inherited by all members, like so:

sealed interface Quantity {}

sealed class Currency : Quantity { ... }

sealed class Length : Quantity { ... }

You can still do everything with Currency and Length that you could if they weren't part of the union. But now you can also define variables of type Quantity that can be inhabited by both currencies and lengths. And importantly, like a true "union type" and unlike a "sum type" (your Rust example), they don't have to be manually wrapped in Quantity.Currency and Quantity.Length. You can even pattern-match on the union, and then further pattern match on the "sum type"s.

when (quantity) {
  is Currency -> when (val currency = quantity) {
    is Currency.US -> ...
    is Currency.CAD -> ...
    is Currency.BTC -> ...
  }
  is Length -> when (val length = quantity) {
    is Length.US -> ...
    is Length.Euro -> ...
  }
}

Defining an "intersection" type is more complicated, and doesn't preserve every functionality of the product types; specifically, you'll no longer be able to de-structure them, although you can access their fields by name. To define an intersection, split all of the product types into interfaces and implementing classes, then add the "intersection class" that inherits the interfaces of all of its components.

sealed interface Currency {
    sealed interface US : Currency { 
        val dollars: Int
        val cents: Int 
        
        companion object {
            operator fun invoke(dollars: Int, cents: Int) : US =
                USImpl(dollars, cents)
            
            private data class USImpl(override val dollars: Int, override val cents: Int) : US
        }
    }

    ... // same boilerplate for CAD and BTC
}

sealed interface Length {
    ... // same boilerplate as above
}

data class USCurrencyAndLength(
    override val dollars: Int,
    override val cents: Int,
    override val miles: Int,
    override val feet: Int,
    override val inches: Int,
    override val centimeters: Float
) : Currency.US, Length.US

USCurrencyAndLength, as a true "intersection type", can be assigned to any variable or parameter of type Currency.US or Length.US. Whereas a "product type" like:

data class USCurrencyAndLength2(val currency: Currency.US, val length: Length.US)

cannot be assigned to those types directly, one must assign usCurrencyAndLength2.currency or usCurrencyAndLength2.length respectively.

$\endgroup$
1
$\begingroup$

For product types, to make the operation associative and commutative, I don't know if there are other ways, but the obvious solution is to make every field having a natural name.

Using the field name as the natural name, is probably not a good design in modern statically typed languages. In dynamically typed languages, it seems inferior to just use no types at all, and check whether the field names exist in situations that need to check the type.

It makes more sense to use a combination of the field name and the type as the natural name, where the later one could be omitted if no ambiguity is found. We could see it's just inheritance. (Inheritance marked as virtual in C++, and interfaces in C# and Java, would make the operation also idempotent.) It's just not easy to use the product as an actual type without some advanced templating. But you could add every type as a constraint in templated code where a product type is expected.

For sum types, there is usually a "top type" that is the sum of all types, or at least all types with a vtable. The vtable pointer works better than enums for this purpose, as the sequential order is not predetermined. Sum types of exact types are better implemented as subsets of the top type, by adding constraints. But again, it is usually not easy to use as an actual type.

The reason they are not directly supported as types, might be because of types usually describe exact memory arrangements, but the sum and product types are abstract concepts that ignored such details. But they came back with other more abstract concepts in programming languages that are just not called types.

$\endgroup$
1
  • $\begingroup$ You wouldn't make a product commutative would you? It would be natural just to preserve the order. I cant see memory arrangements being the reason why rust does not do enum embedding similar to golang's struct embedding $\endgroup$ Commented Jun 24 at 21:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .