BTW: Union types ("tagged unions") predate OOP by some years and thus were there long before OCaml or Haskell. Algol68 had them and also Pascal for example. The invention of ML was pattern matching on those data structures.
FWIW, Peter Landin sowed the seeds in "Mechanical Evaluation of Expressions" in 1964 in his description of recursive discriminated union for lists:
A list is either null
or else has a head (h)
and a tail (t) which is a list.
Rod Burstall picked up on this in "Proving Properties of Progams by Structural Induction" (1968) in an extension to Landin's ISWIM that used pattern matching on these. If you look closely the pattern matching was present in his if-then-else syntax, but he changed it to the more convenient "case".
Pascal's "tagged unions" don't offer anything more than C's though. It's still unsafe and always requires as much memory as the combination of largest cases. OCaml / Haskell / others don't allow type changes at least. That would be useful even without the pattern matching.
