What is the difference between Abstract Data Types and Algebraic Data Types

Question

Could someone please tell me, what is the difference between Abstract Data Types and Algebraic Data Types?

Answer 1

An algebraic data type is a type that consists of sums and products (different constructors and constructors with multiple fields). An abstract data type is a data type that has its implementation abstracted over by an API that is defined... Usually with some sort of encapsulation over its implementation.

For example, a priority queue is an abstract data type. In memory it might be implemented as an array, or as allocated cells on the heap, or with a struct in C, or as a Shakespearean sonnet. However, you abstract over it with a well defined interface: push and pop. you can push items into the queue with priority, and you can pop the highest priority item out at any time. Another example is the associative map or dictionary, which can be implemented with hashing, binary search trees, or well trained sea otters. What matters is that you define lookup, insert, and delete operations that abstract over the underlying implementation.

So they really talk about fundamentally different things. Some data structures can actually be seen as abstract data types implemented as algebraic data types! Like the commom linked list abstract data type in Prelude, which is implemented as the [] algebraic data type. the interface it offers is consing and unconsing, but it's implemented as multiple constructors with one having multiple fields -- sums and products.

Answer 2

I assume you are referring to abstract types and algebraic data types. Most people in Scala refer to ADTs (Algebraic Data Types) as to sum types. [Product types] are algebraic data types as well. A very simple example is the tree (you've actually defined it in one of your previous questions):

sealed abstract class Tree[+A]
case object Leaf extends Tree[Nothing]
case class Branch[A](left: Tree[A], right: Tree[A], value: A) extends Tree[A]

Abstract types in Scala can be defined by letting a type alias undefined in a trait / abstract class to achieve a granular representation. This question is already answered here.

Abstract types are usually used to hide information about the internal structure of a component, so basically to abstract over the concrete type of some component. Trying to rewrite the tree representation using abstract types gives something like:

sealed trait Tree {
  type A
}
case object Leaf extends Tree {
  override type A = Nothing
}
case class Branch(left: Tree, right: Tree) {
  // This doesn't really make sense, we don't want to hide A!
  override type A = ???
}

Finally, abstract types are more of a feature of the type system of Scala (in this case) while algebraic data types are just a form of defining composite types and are independent of the programming language.