Abstract Data Types vs. Parametric Polymorphism in Haskell

Question

I am trying to get a grip on the relationship between these two concepts.

First consider an example of an Abstract Data Type:

data Tree a = Nil 
            | Node { left  :: Tree a,
                     value :: a,
                     right :: Tree a }

According to Haskell wiki:

This type is abstract because it leaves some aspects of its structure undefined, to be provided by the user of the data type. This is a weak form of abstract data type. Source

Now consider the notion of parametric polymorphism:

Parametric polymorphism refers to when the type of a value contains one or more (unconstrained) type variables, so that the value may adopt any type that results from substituting those variables with concrete types. -- Source

Here an example of id :: a -> a is given:

For example, the function id :: a -> a contains an unconstrained type variable a in its type

Question: What is the formal relationship between these two concepts? In particular, are all instances of abstract data types also instances of parametric polymorphism? What about vice versa?

As a warning, this is not what people typically mean by the term "abstract data type" as even the referenced page goes on to say. In fact, I find it bizarre that someone decided to use the term that way. As given in that wiki page, a parameterized data type does require parametric polymorphism (of some sort at least), and such a type is simply an example of a parameterized type. The usual meaning of "abstract data type" does have intimate connections to parametric polymorphism though. — Derek Elkins left SE

Kwarrtz Kwarrtz · Accepted Answer · 2016-04-30T00:01:18

Two things to realize. First, your example Tree is actually a parametric type, which is a special kind of abstract type. Second, parametric polymorphisms can be types or functions. With both of these things in mind, it is obvious that neither abstract types nor parametric polymorphisms are supersets of the other. However, any parametric polymorphism which is a type is also an abstract type. In otherwords, abstract types are a superset of parametrically polymorphic types (dunno if they're actually called that).

Abstract Data Types vs. Parametric Polymorphism in Haskell

2 Answers