Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Is the concept of Algebraic Data Type akin to Class definitions in OO languages?

Both concepts allow new data types to be created. The only difference I can see is that in functional languages, one can perform pattern matching on algebraic data types. But there is no comparable succinct feature for OO languages. Is this an accurate statement ?

like image 938
canadadry Avatar asked May 09 '12 06:05

canadadry


3 Answers

Algebraic data types are so named because they form an "initial algebra",

+ represents sum types (disjoint unions, e.g. Either).
• represents product types (e.g. structs or tuples)
X for the singleton type (e.g. data X a = X a)
1 for the unit type ()
and μ for the least fixed point (e.g. recursive types), usually implicit.

from these operators all regular data types can be constructed. Algebraic data types also support parametric polymophism -- meaning they can be used as constainers for any underlying type, with static guarantees of safety. Additionally, ADTs are provided with uniform syntax for introducing and eliminating data types (via constructors and pattern matching). E.g.

-- this defines a tree
data Tree a = Empty | Node a (Tree a) (Tree a)

-- this constructs a tree
let x = Node 1 (Node 2 Empty) Empty

-- this deconstructs a tree
f (Node a l r) = a + (f l) + (f r)

The richness and uniformity of algebraic data types, along with the fact they're immutable, distinguish them from OO objects, which largely:

  • only represent product types (so no recursive or sum-types)
  • do not support pattern matching
  • are mutable
  • do not support parametric polymorphism
like image 142
Don Stewart Avatar answered Sep 20 '22 05:09

Don Stewart


I can see three major differences between algebraic data types and OO-style classes, not counting (im)mutablility because that varies.

  • Algebraic data types allows sums as well as products, whereas OO-style classes only allow products.
  • OO-style classes allow you to bundle a complex data item with it's accepted operations, whereas algebraic data types don't.
  • Algebraic data types don't distinguish between the data passed to the constructor and the data stored in the resulting value, whereas OO-style classes do (or can).

One thing I deliberately left out of that list was subtyping. While the vast majority of OO languages allow you to subclass (non-final, non-sealed, currently accessible) classes, and the vast majority of generally ML-family functional languages do not, it is clearly possible to forbid inheritance completely in a hypothetical OO (or at least OO-like) language, and it is likewise possible to produce subtyping and supertyping in algebraic data types; for a limited example of the latter, see this page on O'Haskell, which has been succeeded by Timber

like image 32
Ptharien's Flame Avatar answered Sep 21 '22 05:09

Ptharien's Flame


A class is more than just a type definition -- classes in most OO languages are really kitchen sink features that provide all sorts of loosely related functionality.

In particular, classes act as a kind of module, giving you data abstraction and namespacing. Algebraic data types don't have this built in, modularity is usually provided as a separate, orthogonal feature (usually modules).

like image 30
Andreas Rossberg Avatar answered Sep 22 '22 05:09

Andreas Rossberg