[willtim]

ADTs and pattern matching are much more convenient and higher-level in practice than using OOP with inheritance. The visitor pattern, essentially just a fold, is the best one can do in an OOP language. With type-class abstractions and data type generic programming, the gap widens further.

In Haskell, my current FP language of choice, I can implement a complex transform such as Lambda lifting in a few 10's of lines of readable idiomatic code.

[rbehrends]

First, inheritance provides a strict superset of standard ADT functionality. Proof: Scala does ADTs through inheritance. ADTs are basically isomorphic to a closed two-tiered inheritance hierarchy with an abstract superclass at the top tier.

Second, you're confusing inheritance with the ability to map subtypes to operations (and in statically typed languages, in a type-safe fashion). This is a function of OCaml's (or SML's, or Haskell's, or F#'s) pattern matching facilities, not of inheritance vs. ADTs. It can also be done with typecase statements, multi-methods (or actually, just external methods), or tree parsers. The tree parser approach in particular is more general and powerful than the typical pattern matchers in functional languages.

Third, if you look at actual compilers, such traversal will commonly be done in an ad-hoc fashion and can be done equally well with bog-standard methods. Where you have generalized traversal mechanisms, the visitor pattern will crop up in OCaml, too (in some guise or another). Examples are the Ast_mapper module for PPX in OCaml itself [1] and the visitor interface in CIL [2]. The reason is that if you want to perform a generalized fold, map, etc. operation over a heterogeneous data structure such as an AST (visitor is usually fold + map due to destructive updates), you need to also provide a set of operations for the various types that you can encounter during traversal.

[1] https://caml.inria.fr/pub/docs/manual-ocaml/libref/Ast_mappe...

[2] https://people.eecs.berkeley.edu/~necula/cil/api/Cil.cilVisi...

[willtim]

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.

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.

I lumped inheritance and OOP together as this is what is typically packaged and available for us to use.

It is true that more principled traversals (e.g. catamorphisms) only match one level deep, but pattern matching is still a convenient and high-level syntax in such cases. Pattern matching would also complement e.g. attribute grammars.

[rbehrends]

> 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.

[noblethrasher]

I'm happy that you posted this. It's something that I discovered on my own, and have been tentatively arguing for years[1][2][3][4].

In fact, I never really understood the visitor pattern until after I started using ML's pattern matching. The "eureka" moment came when I realized that not only do abstract classes map to sum types (logical disjunction), but interfaces correspond to product types (logical conjunction).

[1] https://www.reddit.com/r/programming/comments/2e572a/rebutta...

[2] https://www.reddit.com/r/programming/comments/14t3ay/either_...

[3] https://news.ycombinator.com/item?id=822479

[4] http://stackoverflow.com/questions/19696342/limiting-class-a...

[wtetzner]

> First, inheritance provides a strict superset of standard ADT functionality.

That's not true. Much of the value of ADTs in OCaml is full type inference. Scala has type inference, but it only sorta-kinda sometimes works.

In other words, a lot of the value of OCaml's types are that they are quite flexible, while still having enough restrictions for the compiler to usefully reason about them.

[rbehrends]

> That's not true. Much of the value of ADTs in OCaml is full type inference.

I consider using type inference for your interfaces to be a software engineering anti-pattern. (Scala also doesn't really support that, except for return types, but you see related issues if you try type inference with objects in OCaml.) Without explicitly typing your interface, users have to look at the implementation to know what the type of a function is. Type inference for local entities is usually pretty easy.

Most of the remaining problems with type inference in Scala are the result of prioritizing Java interoperability in the type system, leading to a number of contortions and workarounds.

[wtetzner]

I don't necessarily disagree with what you've said, my main point was that much of the value of ADTs in OCaml is in their restrictions.