24

I am a long time OO programmer and a functional programming newbie. From my little exposure algebraic data types only look like a special case of inheritance to me where you only have one level hierarchy and the super class cannot be extended outside the module.

So my (potentially dumb) question is: If ADTs are just that, a special case of inheritance (again this assumption may be wrong; please correct me in that case), then why does inheritance gets all the criticism and ADTs get all the praise?

Thank you.

1
  • Even if inheritance is really is more general than ADT (which is not), you also make a mistake where more general means better. It's not the case.
    – Xwtek
    Oct 28, 2018 at 7:33

4 Answers 4

32

I think that ADTs are complementary to inheritance. Both of them allow you to create extensible code, but the way the extensibility works is different:

  • ADTs make it easy to add new functionality for working with existing types
    • You can easily add new function that works with ADT, which has a fixed set of cases
    • On the other hand, adding new case requires modifying all functions
  • Inheritance makes it easy to add new types when you have fixed functionality
    • You can easily create inherited class and implement fixed set of virtual functions
    • On the other hand, adding a new virtual function requires modifying all inherited classes

Both object-oriented world and functional world developed their ways to allow the other type of extensibility. In Haskell, you can use typeclasses, in ML/OCaml, people would use dictionary of functions or maybe (?) functors to get the inhertiance-style extensibility. On the other hand, in OOP, people use the Visitor pattern, which is essentially a way to get something like ADTs.

The usual programming patterns are different in OOP and FP, so when you're programming in a functional language, you're writing the code in a way that requires the functional-style extensibility more often (and similarly in OOP). In practice, I think it is great to have a language that allows you to use both of the styles depending on the problem you're trying to solve.

9
  • +1. so how is this different than Aspect Oriented Programming? it seems to be related. could you elaborate in your answer?
    – eruciform
    Jul 17, 2010 at 15:58
  • " I think it is great to have a language that allows you to use both of the styles depending on the problem you're trying to solve." <-- Are you talking about Scala here? Jul 17, 2010 at 17:41
  • @Cheryl: I was talking mainly about F# and Scala (because I know them). However, I think that Haskell may actually also fit into this category to some point thanks to typeclasses. They do not give you dynamic dispatch, but they allow you to "add new types" easily. Jul 17, 2010 at 18:31
  • 1
    Scala supports both styles, as does Haskell. Jul 17, 2010 at 18:36
  • @Tomas Petricek: Dynamic dispatch works just fine with type classes--GHC, for instance, bundles explicit type class dictionaries with values when it can't determine the exact type at compile time for a polymorphic expression using type class methods. Jul 17, 2010 at 18:58
12

Tomas Petricek has got the fundamentals exactly right; you might also want to look at Phil Wadler's writing on the "expression problem".

There are two other reasons some of us prefer algebraic data types over inheritance:

  • Using algebraic data types, the compiler can (and does) tell you if you have forgotten a case or if a case is redundant. This ability is especially useful when there are many more operations on things than there are kinds of thing. (E.g., many more functions than algebraic datatypes, or many more methods than OO constructors.) In an object-oriented language, if you leave a method out of a subclass, the compiler can't tell whether that's a mistake or whether you intended to inherit the superclass method unchanged.

  • This one is more subjective: many people have noted that if inheritance is used properly and aggressively, the implementation of an algorithm can easily be smeared out over a half a dozen classes, and even with a nice class browser at can be hard to follow the logic of the program (data flow and control flow). Without a nice class browser, you have no chance. If you want to see a good example, try implementing bignums in Smalltalk, with automatic failover to bignums on overflow. It's a great abstraction, but the language makes the implementation difficult to follow. Using functions on algebraic data types, the logic of your algorithm is usually all in one place, or if it is split up, its split up into functions which have contracts that are easy to understand.


P.S. What are you reading? I don't know of any responsible person who says "ADTs good; OO bad."

3
  • 1
    I didn't say OO bad. I say inheritance is bad and almost everybody seems to be saying it. (Just a quick googling gives hundreds of results) Jul 17, 2010 at 17:40
  • and you yourself keep praising ADTs in many Haskell / FP threads :) Jul 17, 2010 at 17:40
  • 2
    @Cheryl: I'll back you up on that--I'm happy to say that inheritance as it exists in many languages is, from a purely OO standpoint, almost always a bad idea. Some combination of generics, interfaces, mix-ins, and object composition is almost always a much better approach. Jul 17, 2010 at 18:25
9

In my experience, what people usually consider "bad" about inheritance as implemented by most OO languages is not the idea of inheritance itself but the idea of subclasses modifying the behavior of methods defined in the superclass (method overriding), specifically in the presence of mutable state. It's really the last part that's the kicker. Most OO languages treat objects as "encapsulating state," which amounts to allowing rampant mutation of state inside of objects. So problems arise when, for example, a superclass expects a certain method to modify a private variable, but a subclass overrides the method to do something completely different. This can introduce subtle bugs which the compiler is powerless to prevent.

Note that in Haskell's implementation of subclass polymorphism, mutable state is disallowed, so you don't have such issues.

Also, see this objection to the concept of subtyping.

2
  • 1
    This is well put. Programming through interfaces is a good thing (and implementing them also - compiler will make sure you implement them entirely), their purpose being to abstract a certain functionality. But subclassing and abstract classes, on the other hand, are there mainly as a tool for code reuse, and promote state sharing and coupling between subclasses which often reduces maintenability.
    – vgru
    Dec 23, 2014 at 19:52
  • Excellent observation on the root cause.
    – jmrah
    Jan 7, 2019 at 17:37
8

I am a long time OO programmer and a functional programming newbie. From my little exposure algebraic data types only look like a special case of inheritance to me where you only have one level hierarchy and the super class cannot be extended outside the module.

You are describing closed sum types, the most common form of algebraic data types, as seen in F# and Haskell. Basically, everyone agrees that they are a useful feature to have in the type system, primarily because pattern matching makes it easy to dissect them by shape as well as by content and also because they permit exhaustiveness and redundancy checking.

However, there are other forms of algebraic datatypes. An important limitation of the conventional form is that they are closed, meaning that a previously-defined closed sum type cannot be extended with new type constructors (part of a more general problem known as "the expression problem"). OCaml's polymorphic variants allow both open and closed sum types and, in particular, the inference of sum types. In contrast, Haskell and F# cannot infer sum types. Polymorphic variants solve the expression problem and they are extremely useful. In fact, some languages are built entirely on extensible algebraic data types rather than closed sum types.

In the extreme, you also have languages like Mathematica where "everything is an expression". Thus the only type in the type system forms a trivial "singleton" algebra. This is "extensible" in the sense that it is infinite and, again, it culminates in a completely different style of programming.

So my (potentially dumb) question is: If ADTs are just that, a special case of inheritance (again this assumption may be wrong; please correct me in that case), then why does inheritance gets all the criticism and ADTs get all the praise?

I believe you are referring specifically to implementation inheritance (i.e. overriding functionality from a parent class) as opposed to interface inheritance (i.e. implementing a consistent interface). This is an important distinction. Implementation inheritance is often hated whereas interface inheritance is often loved (e.g. in F# which has a limited form of ADTs).

You really want both ADTs and interface inheritance. Languages like OCaml and F# offer both.

1
  • I assume you meant the last line to read "You really want both ADTs and interface inheritance"? Jul 19, 2010 at 9:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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