<p>Many languages support <a href="https://en.wikipedia.org/wiki/Algebraic_data_type" rel="nofollow noreferrer">algebraic data types</a> which are essentially <a href="https://en.wikipedia.org/wiki/Tagged_union" rel="nofollow noreferrer">tagged unions</a> of tuples or structs. For example, suppose we have a type for an expression node in an AST:</p>
<pre><code>type Expr =
    | Literal of int                 // 23
    | Var of str                     // x
    | Add of (Expr, Expr)            // a + b
    | IndexAccess of (Expr, Expr)    // a[b]
    | FieldAccess of (Expr, str)     // a.x
    // ...
</code></pre>
<p>For some purposes we may need a subtype, e.g. the lvalue of an assignment statement might be a <code>Var</code>, <code>IndexAccess</code> or <code>FieldAccess</code> but not any other kind of expression.</p>
<p>In many languages (e.g. Rust) it would be necessary to declare a separate type for just these cases, and there would be no subtype relation between the two types; <code>LValue</code> would not be assignable to <code>Expr</code> via upcasting, nor vice versa by downcasting. In these languages it would be necessary to write a (trivial) type conversion function to transform values from one type to the other.</p>
<p>On the other hand, in some languages there can be subtype relations between tagged union types, e.g. in Typescript the above example might be written like this:</p>
<pre class="lang-typescript prettyprint-override"><code>type Expr =
    | {kind: 'Literal', value: number}
    | {kind: 'Var', name: string}
    | {kind: 'Add', left: Expr, right: Expr}
    | {kind: 'IndexAccess', subject: Expr, index: Expr}
    | {kind: 'FieldAccess', subject: Expr, field: string}
    // ...

type LValue = Extract&lt;Expr, {kind: 'Var' | 'IndexAccess' | 'FieldAccess'}&gt;
</code></pre>
<p>This can be more convenient since it allows the subtype to be directly used where the supertype is expected, without needing trivial type conversion functions. It also opens the door to other features such as control-flow type narrowing, which requires that the narrower types be expressible within the type system. Given these advantages, what are the reasons <em>against</em> having this feature for algebraic data types?</p>

<algebraic-data-types><subtypes>
Are there disadvantages to having subtypes of algebraic data types?
CC BY-SA 4.0
2023-05-23T15:09:17.637Z
The disadvantages for subtyping in general apply too: handling variance gets confusing, and often leads to either bugs or lack of expressiveness in the type system.
pxeger
CC BY-SA 4.0
2023-05-23T15:19:44.033Z
Also, this question is really only about sum types, not algebraic data types in general (which also includes product types and maybe more)
pxeger
CC BY-SA 4.0
2023-05-23T16:15:23.793Z
@pxeger I use the term the way it is used on the linked Wikipedia page ─ programming languages like Haskell, OCaml and F# have this concept where a type is declared as a sum of products. The products could be factored out to give `type Expr = | Add Add | IndexAccess IndexAccess | FieldAccess FieldAccess | ...` but I think this is much less clear, and it would be confusing to write the question that way because `Add` *wouldn't* be a subtype of `Expr`, due to lacking the tag for the `Add` constructor from the sum type.
kaya3
CC BY-SA 4.0
2023-05-23T18:13:17.497Z
That's true, but  OOP classes are really just products, so subtyping products is a pretty well studied idea, which is why I think the main point of your question is about subtyping with sum types. But if it's really about both then I'd say it's two questions in one, and should be narrowed in scope.
pxeger
CC BY-SA 4.0
2023-05-23T19:30:59.627Z
@pxeger Yes, the question is about subtyping of sum types, it's just additional context that the sum types I'm interested in are sums of products. Many languages make "sum of products" a language construct without necessarily having sum types as a separate concept; and that language construct is usually called an algebraic data type, perhaps this usage is not exactly consistent with academic usage of that term
kaya3
<h1>Memory Layout</h1>
<p>In some languages, such as Swift or Rust, the “associated values” are stored inline, and so the size of a sum type is a function of the size of the largest case. If subsets were required to be compatible with the whole, they could be much larger than necessary.</p>
<p>Consider this slightly impractical example:</p>
<pre class="lang-swift prettyprint-override"><code>enum Whole {
  case nothing
  case integer(Int32)
  case floatingPoint(Float)
  case gigantic(fee: String, fi: String, fo: String, fum: String)
}

enum Part {
  case integer(Int32)
  case floatingPoint(Float)
}

print(MemoryLayout&lt;Whole&gt;.size) // 65
print(MemoryLayout&lt;Part&gt;.size) // 5
</code></pre>
<p>Note that this isn’t the case in TypeScript, where these types are just a single reference either way.</p>

CC BY-SA 4.0
2023-05-23T13:21:35.513Z
2023-05-23T13:21:35.513Z
Bbrk24
CC BY-SA 4.0
2023-05-23T14:39:41.040Z
This proves a casting step is necessary, but it could be implicit
mousetail 'he-him'
CC BY-SA 4.0
2023-05-23T14:41:35.147Z
Languages affected by this tend not to do conversions like this implicitly; however, you could write a macro for these casts.
Bbrk24
CC BY-SA 4.0
2023-05-23T15:14:32.407Z
@mousetail Implicit casts get more complicated once you start dealing with first-class functions ─ if `foo` is a function of type `() => LValue` and somewhere expects a callback of type `() => Expr`, for example, then you have to pass a version of `foo` that is composed with the cast operation.
kaya3
CC BY-SA 4.0
2023-05-23T15:43:07.270Z
Supporting implicit casts for the specific case of enums does not mean you need to always support them in every case. You could not allow implicit casting of functions for the reasons stated
mousetail 'he-him'
# Are there disadvantages to having subtypes of algebraic data types?
Posted by: username_0 on 2023-05-23
Many languages support algebraic data types which are essentially tagged unions of tuples or structs. For example, suppose we have a type for an expression node in an AST:
type Expr =
    | Literal of int                 // 23
    | Var of str                     // x
    | Add of (Expr, Expr)            // a + b
    | IndexAccess of (Expr, Expr)    // a[b]
    | FieldAccess of (Expr, str)     // a.x
    // ...

For some purposes we may need a subtype, e.g. the lvalue of an assignment statement might be a Var, IndexAccess or FieldAccess but not any other kind of expression.
In many languages (e.g. Rust) it would be necessary to declare a separate type for just these cases, and there would be no subtype relation between the two types; LValue would not be assignable to Expr via upcasting, nor vice versa by downcasting. In these languages it would be necessary to write a (trivial) type conversion function to transform values from one type to the other.
On the other hand, in some languages there can be subtype relations between tagged union types, e.g. in Typescript the above example might be written like this:
type Expr =
    | {kind: 'Literal', value: number}
    | {kind: 'Var', name: string}
    | {kind: 'Add', left: Expr, right: Expr}
    | {kind: 'IndexAccess', subject: Expr, index: Expr}
    | {kind: 'FieldAccess', subject: Expr, field: string}
    // ...

type LValue = Extract

This can be more convenient since it allows the subtype to be directly used where the supertype is expected, without needing trivial type conversion functions. It also opens the door to other features such as control-flow type narrowing, which requires that the narrower types be expressible within the type system. Given these advantages, what are the reasons against having this feature for algebraic data types?
**Tags:** algebraic-data-types subtypes
> **Comments:**
> **username_1**: The disadvantages for subtyping in general apply too: handling variance gets confusing, and often leads to either bugs or lack of expressiveness in the type system.  
> **username_1**: Also, this question is really only about sum types, not algebraic data types in general (which also includes product types and maybe more)  
> **username_0**: @pxeger I use the term the way it is used on the linked Wikipedia page ─ programming languages like Haskell, OCaml and F# have this concept where a type is declared as a sum of products. The products could be factored out to give `type Expr = | Add Add | IndexAccess IndexAccess | FieldAccess FieldAccess | ...` but I think this is much less clear, and it would be confusing to write the question that way because `Add` *wouldn't* be a subtype of `Expr`, due to lacking the tag for the `Add` constructor from the sum type.  
> **username_1**: That's true, but  OOP classes are really just products, so subtyping products is a pretty well studied idea, which is why I think the main point of your question is about subtyping with sum types. But if it's really about both then I'd say it's two questions in one, and should be narrowed in scope.  
> **username_0**: @pxeger Yes, the question is about subtyping of sum types, it's just additional context that the sum types I'm interested in are sums of products. Many languages make "sum of products" a language construct without necessarily having sum types as a separate concept; and that language construct is usually called an algebraic data type, perhaps this usage is not exactly consistent with academic usage of that term  
---
## 1 answers
### Answer by username_2 on 2023-05-23. Score: 5 | Accepted answer
Memory Layout
In some languages, such as Swift or Rust, the “associated values” are stored inline, and so the size of a sum type is a function of the size of the largest case. If subsets were required to be compatible with the whole, they could be much larger than necessary.
Consider this slightly impractical example:
enum Whole {
  case nothing
  case integer(Int32)
  case floatingPoint(Float)
  case gigantic(fee: String, fi: String, fo: String, fum: String)
}

enum Part {
  case integer(Int32)
  case floatingPoint(Float)
}

print(MemoryLayout.size) // 65
print(MemoryLayout.size) // 5

Note that this isn’t the case in TypeScript, where these types are just a single reference either way.
> **Comments:**
> **username_3** (2023-05-23): This proves a casting step is necessary, but it could be implicit  
> **username_2** (2023-05-23): Languages affected by this tend not to do conversions like this implicitly; however, you could write a macro for these casts.  
> **username_0** (2023-05-23): @mousetail Implicit casts get more complicated once you start dealing with first-class functions ─ if `foo` is a function of type `() => LValue` and somewhere expects a callback of type `() => Expr`, for example, then you have to pass a version of `foo` that is composed with the cast operation.  
> **username_3** (2023-05-23): Supporting implicit casts for the specific case of enums does not mean you need to always support them in every case. You could not allow implicit casting of functions for the reasons stated  
---
