Abstract data type

Not to be confused with an algebraic data type.

An abstract data type is a type whose implementation is not visible, but can only accessed through specific operations.

For example, a stack of integers can be represented as any type S which is equipped with operations

  \textsf{push} : S \times \textsf{Int} \to S
  \qquad
  \textsf{pop} : S \to \textsf{Int} \times S

In type theory

Type-theoretically, abstract data types are represented through existential types.

In OOP

In object-oriented programming, abstract data types are represented through interfaces.

In functional languages

In purely functional languages, such as Haskell, abstract data types are sometimes represented through type classes. This does not provide the hiding mechanisms that existential types and interfaces provide, but it does allow for constraining types in a signature to ones that support a certain interface.

However, please note that Haskell does have some limited support for existential types.

References

• The connection between abstract data types and existential types was spelled out by Mitchell and Plotkin in a POPL 1985 paper, the full version of which was published in TOPLAS in 1988.

@inproceedings{mitchell_1985,
	title = {Abstract types have existential types},
	doi = {10.1145/318593.318606},
	pages = {37--51},
	booktitle = {Proceedings of the 12th {ACM} {SIGACT}-{SIGPLAN} symposium on Principles of Programming Languages  - {POPL} '85},
	publisher = {Association for Computing Machinery},
	author = {Mitchell, John C. and Plotkin, Gordon D.},
	date = {1985},
}

@article{mitchell_1988,
	title = {Abstract types have existential type},
	volume = {10},
	doi = {10.1145/44501.45065},
	pages = {470--502},
	number = {3},
	journaltitle = {{ACM} Transactions on Programming Languages and Systems},
	author = {Mitchell, John C. and Plotkin, Gordon D.},
	date = {1988},
}