3 ms·

Wait, the thing the article calls "array of variant arrays (or AoVA)" is not the canonical way to decompose tagged unions? Seriously? [A×B×C] ≃ [A]×[B]×[C], tha

Wait, the thing the article calls "array of variant arrays (or AoVA)" is not the canonical way to decompose tagged unions? Seriously? [A×B×C] ≃ [A]×[B]×[C], that's the most obvious thing, isn't it? Edit: Actually, never mind, as the comment points out, the correct equation should be [A+B+C] ≃ [A]×[B]×[C] and it's not obvious at all whether it's actually correct.

ratmice 3y ago
Don't you mean something like [A+B+C] ≃ [A]×[B]×[C]
pornel 3y ago
Things like that can be done by specific collections (e.g. most ECS implementations store components per "archetype"). But from language perspective the limiting factor is that you're always allowed to take a reference to any instance of an enum. This means the tag must be stored in every instance. If you allow mutable references to enums, you must have enough space for writing any variant there through the reference.
kccqzy 3y ago
Of course not: you are mistaking sum types and product types. Even if we assume they are product types, [A×B×C] ≃ [A]×[B]×[C] is still not correct. The former doesn't allow the number of As and Bs and Cs to differ: the latter does. So the latter strictly speaking admits more values than the former. Since both of them allow infinite number of values, to make a size comparison we will use generating functions. A list of A (or [A] in your notation) allows an empty list (one possible value), a one-element list (as many values as A itself), a two-element list… which becomes 1+A+A^2+…=1/(1-A). The beautiful thing about calling them sum types or products types is that you can manipulate it just by summing or multiplying respectively. So the number of values for [AxBxC] is identified by 1/(1-ABC). For [A]*[B]*[C] it's 1/(1-A)/(1-B)/(1-B) which simplifies to 1/(1-A-B-C+AB+AC+BC-ABC). Now it becomes obvious† this form admits more values and you can in a sense quantify how many more! †: Okay perhaps it's only obvious if I also include a Venn diagram but diagramming is beyond what I can do on HN.
- Joker_vD 3y ago
  Yeah, and if you carefully expand 1+(A+B+C)+(A+B+C)^2+(A+B+C)^3+..., there'll be strictly more summands than in (1+A+A^2+A^3+...)×(1+B+B^2+B^3+...)×(1+C+C^2+C^3+...) due to more flexible ordering of elements, so they're not isomorphic. I still think it's the most obvious thing that [A+B+C] at least maps surjectively onto [A]×[B]×[C] :)
deleted 3y ago
[deleted]
catgary 3y ago
It’s a section/retract, definitely not an isomorphism. You’ll need to carry around the index data, and any sort of array update will incur a crazy upfront cost.
- Joker_vD 3y ago
  Eh, I imagine it should be possible to maintain an out-of-line skip-list or an array of tombstones or something to deal with deletion/tag mutation (although in my experience with ASTs that's not that common of a requirement); and allocation can be done quite effectively with the help of the good old .bss section: just grab couple of millions of every type of node at the program's startup, virtual memory is almost free.

ratmice 3y ago

Don't you mean something like [A+B+C] ≃ [A]×[B]×[C]

pornel 3y ago

Things like that can be done by specific collections (e.g. most ECS implementations store components per "archetype"). But from language perspective the limiting factor is that you're always allowed to take a reference to any instance of an enum. This means the tag must be stored in every instance. If you allow mutable references to enums, you must have enough space for writing any variant there through the reference.

kccqzy 3y ago

Of course not: you are mistaking sum types and product types. Even if we assume they are product types, [A×B×C] ≃ [A]×[B]×[C] is still not correct. The former doesn't allow the number of As and Bs and Cs to differ: the latter does. So the latter strictly speaking admits more values than the former. Since both of them allow infinite number of values, to make a size comparison we will use generating functions. A list of A (or [A] in your notation) allows an empty list (one possible value), a one-element list (as many values as A itself), a two-element list… which becomes 1+A+A^2+…=1/(1-A). The beautiful thing about calling them sum types or products types is that you can manipulate it just by summing or multiplying respectively. So the number of values for [AxBxC] is identified by 1/(1-ABC). For [A]*[B]*[C] it's 1/(1-A)/(1-B)/(1-B) which simplifies to 1/(1-A-B-C+AB+AC+BC-ABC). Now it becomes obvious† this form admits more values and you can in a sense quantify how many more! †: Okay perhaps it's only obvious if I also include a Venn diagram but diagramming is beyond what I can do on HN.

Joker_vD 3y ago
Yeah, and if you carefully expand 1+(A+B+C)+(A+B+C)^2+(A+B+C)^3+..., there'll be strictly more summands than in (1+A+A^2+A^3+...)×(1+B+B^2+B^3+...)×(1+C+C^2+C^3+...) due to more flexible ordering of elements, so they're not isomorphic. I still think it's the most obvious thing that [A+B+C] at least maps surjectively onto [A]×[B]×[C] :)

deleted 3y ago

[deleted]

catgary 3y ago

It’s a section/retract, definitely not an isomorphism. You’ll need to carry around the index data, and any sort of array update will incur a crazy upfront cost.

Joker_vD 3y ago
Eh, I imagine it should be possible to maintain an out-of-line skip-list or an array of tombstones or something to deal with deletion/tag mutation (although in my experience with ASTs that's not that common of a requirement); and allocation can be done quite effectively with the help of the good old .bss section: just grab couple of millions of every type of node at the program's startup, virtual memory is almost free.