StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Union and intersection types are just considering types to be sets of values (infinite sets, mostly). If that's how you're thinking of types then any operation on sets that results in a set could be applied to types (sets of values) to make a new type (set of values), at least conceptually.</p> <p>A union type is similar in some senses to a sum type, which you seem to be familiar with. Indeed I've often heard sum types described as "discriminated union" types. The basic difference is that a sum type like (Haskell notation) <code>data FooBar = Foo Integer | Bar String</code> allows you to tell whether a given <code>FooBar</code> value contains an <code>Integer</code> or a <code>String</code> (because <code>FooBar</code> values are tagged with <code>Foo</code> or <code>Bar</code>). Even if we write <code>data FooBar = Foo Integer | Bar Integer</code> where both types are the same, the "tag" adds extra information and we can tell "which integer" the <code>FooBar</code> value is.</p> <p>The union type equivalent would be something like (not valid Haskell) <code>data FooBar = Integer | String</code>. The values in <code>FooBar</code> simply are all the string values and all the integer values. If we make a union type of the same two types like <code>data FooBar = Integer | Integer</code> it should be logically indistinguishable from just <code>Integer</code>, since the union of a set with itself is itself.</p> <p>In principle, the things you could do with values in a type U that is the union of types A and B are just the operations that work on As and also work on Bs; any operation that only works on either As or Bs might get the wrong kind of input, because a U has no information to say whether it's an A or a B.<sup>1</sup></p> <p>(Undiscriminated) union types wouldn't be very interesting in languages with type systems similar to Haskell's, because concrete types are disjoint<sup>2</sup>, so the only operations that work on both As and Bs work on all values (unless A is B, in which it's just all the operations that work on that single type).</p> <p>But in a way, a type classes (if you're familiar with them) are a way of providing something a bit like a union type. A type which is polymorphic but constrained to be a member of some type class is a little like a union of all the types which are in the type class (except that you don't know what those are, because type classes are in principle open); the only things you can do with such a value are the thins which have been declared to work on values of <em>every</em> type in the type class.</p> <p>Union types could be interesting in a language with sub-typing (as is common in object-oriented programming languages). If you union together two subtypes of a common super-type you get something that supports at least the operations of the super-type, but it excludes any other subtypes of the super-type, so it isn't the same as just using the super-type.</p> <p>An intersection type is exactly the concept, but using intersection instead of union. This means the things you could do with a value in a type I that is the intersection of types A and B are the operations that work on As <em>plus</em> the operations that work on Bs; anything in I is guaranteed to be both an A and a B, so it can safely be given to either kind of operation.</p> <p>These also wouldn't be very interesting in languages with Haskell-like type systems. Because concrete types are disjoint<sup>2</sup>, any non-trivial intersection is empty. But again, type class constraints can provide something a bit like an intersection type; if you add multiple type class constraints to the same type variable, then the only values that can be used where that type variable is expected are of types that are in the "intersection" of all the type classes, and the operations you can use on such values are the operations that work with any of the type classes.</p> <hr> <p><sup>1</sup> You could imagine combining an operation <code>A -> C</code> and an operation <code>B -> D</code> to get an operation <code>(A | B) -> (C | D)</code>, much like you can use the tags of sum types to "route" a sum type to the appropriate operation. But it gets murky for fully general union types. If A and B overlap (and overlapping types enter the fray as soon as you've got union types), then which operation do you invoke on a value in the overlapping region? If you can tell whether it's an A or a B then you've really got a sum type rather than a union type, and if you apply some arbitrary resolution strategy like picking the <code>A -> C</code> operation because <code>A</code> was listed earlier in the union type's definition, then things work fine in simple cases but get very confusing if you've got types like <code>(A | B) & (B | A)</code> (where I'm using <code>&</code> to denote intersection).</p> <p><sup>2</sup> Although the "disjoint types" point is debatable. In types like <code>data Maybe a = Nothing | Just a</code> you could justifiably argue that the <code>Nothing</code> is the "same value" even for different <code>a</code>. If so, then the union of <code>Maybe String</code> and <code>Maybe Integer</code> only contains one <code>Nothing</code> (rather than both the <code>Nothing</code> that is "no string" and the <code>Nothing</code> that is "no integer"). And the intersection of <code>Maybe String</code> and <code>Maybe Integer</code> contains only one value, that being <code>Nothing</code>.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload