Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Out of curiosity, are there languages that allow you to do set arithmetic on types to create new types? Something like:

interface A {
  void a();
  void b();

interface B {
  void b();
  void c();

interface C = A & B; // has b()
interface D = A | B; // has a(), b() and c()
interface E = (A & B) ^ B; // has c()

I know that in some languages these ideas can be expressed (i.e., Java has List<Comparable & Serializable> for the union of the interfaces) but I've never heard of a language that supports type arithmetic. Thanks!

share|improve this question
How would such a mechanism be useful? –  Robert Harvey Nov 21 '12 at 0:35
A pattern I've seen a lot is an interface that extends two other interfaces and doesn't add anything (i.e., CanWriteAndCompare extends Serializable, Comparable {}) and I was thinking of how to generalize this. –  Will Brown Nov 21 '12 at 0:43
Also, I ran into a case today where I have method that can take an A or a B, with two implementations that look exactly the same. In the method I'm calling a polymorphic method that can take an A or a B, so the implementations are the same, but since I have to take two distinct types I need two implementations. This would be easier if I could do myMethod(A | B aOrB). –  Will Brown Nov 21 '12 at 0:45
Or operation can be emulated by multiple inheritance. –  user Nov 21 '12 at 5:42
show 2 more comments

3 Answers

up vote 4 down vote accepted

Tangent(0.3 spec) uses something akin to this. (disclaimer: this is my own little research project)

Currently with acts as a union operator modelling inheritance, though pragmatism has made it not commutative. Once you introduce implementations to methods, a strict union of methods with the same name is often not what you want and impossible to do right anyways.

intersect is supported that models type inference for something like foo(T,T) where the parameters are different.

Complements were interesting, but led to partial types that seemed not so useful and/or troublesome to include correctly - so are not included.

I know there are a few other research languages I ran across that had something similar, but cannot remember them at the moment. The main issue is that the things aren't really useful without structural typing, which isn't terribly popular itself. The other is that you need some sort of kind (type of types) to store the constructed type, or else it's just shorthand for something that isn't particularly idiomatic without that capability. And that's far less common than even structural typing.

It's biased, and it's not much, but there it is.

share|improve this answer
add comment

Scala supports it partially (intersections but not unions), and any language with structural subtyping (I think OCaml is an example) or a type system powerful enough to emulate that (Haskell is a classic one) will have full "types-as-sets" capabilities, at least within the fragment of its type system that accepts such things (relevant when it's emulated ala HList/OOHaskell).

Since I don't know OCaml very well, I'll give the portion of your example that works in Scala:

trait A {
  def a(): Unit
  def b(): Unit

abstract class B { // just to prove it works with both traits and classes
  def b(): Unit
  def c(): Unit

type C = A with B
type D = { def b(): Unit } // not an exact translation, because unions aren't directly available
// type `E` is unrepresentable

A version for Haskell would depend on the record system you were using, and would likely be somewhat clunky, because it would be emulated rather than natively supported.

As far as I know, Ceylon has both intersection and union types built into the language in full power, so you could presumable encode a type-level "xor" in terms of those.

share|improve this answer
add comment

Yes, Ceylon is a language with ad hoc union and intersection types, as described in this chapter from the Ceylon tour:


It's amazing the number of cool idioms you get out of this. Here's one interesting example I blogged recently. And here's a short presentation where I quickly gloss over several simple idioms.

Even better, union/intersection types are the "missing link" that makes generic type argument inference really work right in Ceylon as opposed to other languages which combine subtype and parametric polymorphism.

Note that there are limitations to this sort of "type arithmetic", as you've described it. For example, you can't have a set complement operator at the type level, at least not without introducing undecidability.


share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.