Could someone please tell me, what is the difference between Abstract Data Types and Algebraic Data Types?
2 Answers
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.
-
1
-
3A sum type
S = T | U
is a type whose set of values is the sum (union) of the sets of the values of typesT
andU
. A product typeP = T × U
is a type whose set of values is the (cartesian) product of the sets of values ofT
andU
. The most well-known product types areTuple
s andRecord
s. Mar 16, 2017 at 12:03 -
2
-
3@zero_coding Imagine the tuple of type
(Int, String)
. It's type is the combination ofInt
andString
making it the product of those two types. Another way to think about it, is the tuple is any possibleInt
combined with any possibleString
. Combining every possible element from one set with every possible element from another is "Cartesian Product" of those two sets.– puhlenMar 16, 2017 at 14:21 -
1@zero_coding - If you have a type
A
withN
inhabitants and a typeB
withM
inhabitants then the product typeA x B
hasN * M
inhabitants. Similarly the sum typeA | B
hasN + M
inhabitants.– LeeMar 16, 2017 at 14:59
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.
-
1
-
@pedrofurla Thank you, I've updated the answer :) I omitted that only because I tried to illustrate what most people using Scala think of when talking about ADTs. It makes sense though to enumerate the others as well though. Mar 16, 2017 at 13:21