> Inheritance may be a theoretical superset of ADTs, but it is not as convenient due to the complexity of subtyping and problems with its inference. Scala is the proof of this.
Scala isn't proof of this, because so much of the complexity of Scala's type system is due to a desire to provide smooth interoperability with Java's, which requires the replication of and dealing with some of the more misguided aspects of Java's approach. (The biggest one is probably that Java's constrained parametric polymorphism is intimately tied to a form of nominal subtyping that is simultaneously too constraining and not expressive enough for a number of use cases, leading to things such as implicit arguments and CanBuildFrom in Scala.)
> Both extensible records and open recursion can be achieved with ADTs, so why do we need inheritance with all its problems? You still haven't explained this.
My general argument would be that any single approach to polymorphism will be insufficient to cover all use cases, many of which have mutually incompatible requirements:
1. You may want to be able to exhaustively enumerate operations on a type or subtype for purposes of code verification or optimization.
2. You may want to be able to add additional operations to a type or subtype for purposes of modularity or extensibility.
3. You may want to be able to exhaustively enumerate subtypes of a type for purposes of code verification or optimization.
4. You may want to be able to add additional subtypes to a type for purposes of modularity or extensibility.
5. You may want to resolve polymorphism at runtime.
6. You may want to resolve polymorphism at compile-time.
ADTs present you with a closed universe of subtypes and an open universe of operations as well as runtime polymorphism. In other words, they meet half of the above criteria.
Haskell's approaches to extensible records and open recursion cannot square the circle, either. They require their own mechanisms and/or hacks on top of ADTs and have their pros and cons that are distinct from the pros and cons of using inheritance. There is no single mechanism for polymorphism that can do it all. (OCaml, incidentally, has at least six distinct polymorphism mechanisms that support runtime polymorphism: ADTs, polymorphic variants, open types, records of closures, first-class modules, objects.)
A simple example of something that basic ADTs just don't do: add more variants (subtypes in the OO case) to the type. You can go with something like OCaml's polymorphic variants, but that doesn't make it easy to extend existing operations in a modular fashion as you add more variants. If you want to simulate OO-style extensible late binding in Haskell, you'll generally need {-# LANGUAGE ExistentialQuantification #-} and type classes.
Inheritance, incidentally, does not inherently present more or less problems than other approaches. That it does not fit neatly in the Haskell universe is the result of various constraints and preferences within Haskell's design, just as some of Haskell's mechanisms fit poorly into other languages. These are not universal problems; this is about language design constraints.