Are there algebraic data types outside of sum and product?

8
votes

By most definitons the common or basic algebraic data types in Haskell or Scala are sum and product. Examples: 1, 2.

Sometimes a definition just says algebraic data types are sum and product, perhaps for simplicity.

However, the definitions leave an impression that other algebraic data types are possible, and sum and product are just the most useful to describe selection or combination of elements.

Given there are subtraction, division, raising to an integer power operations in a basic algebra - is it correct some implementation of other alternative algebraic types in programming is possible, but they are not useful?

Do any programming languages have algebraic data types implemented that are not sum and product types?

3
scalahaskelltypesalgebraic-data-types
Exponentiation is also represented in ADTs, via function types A -> B. (PS I'm coming to this question from a Haskell background. I don't know Scala at all.) – Robin Zigmond
Does this answer your question? What is an Algebraic Data Type (ADT)? – Suma
@Suma - thanks for the link, it has a similar, but broader question. The answeres provided here are specific to non-sum/product algebraic types and their implementation. Also for abbreviation, ADT is usually reserved for abstract data types wiki.haskell.org/Abstract_data_type, not algebraic data types. – Evgeny

3 Answers

17
votes

"Algebraic" comes from category theory. Every algebraic data type is an initial algebra of a functor. So you could in principle call anything that comes from a functor in this way algebraic, and I think it's quite a large class.

Interpreting "algebraic" to mean "high-school algebra" (I don't mean to be condescending, that's just how we refer to it) as you have, there are some nice analogies.

  • Arbitrary powers, not just integer powers, are closely analogous to function types, that is, A -> B is analogous to BA. In category theory, when you consider a function ("morphism") as an object of a category, it's called an exponential object, and the latter notation is used. For fun, see if you can prove the law CA+B = CA × CB by writing a bijection between the corresponding types.
  • Division is analogous to quotient types, which is a fascinating area of research that reaches into things as hott and trendy as homotopy type theory. The analogy of quotients to division is not as strong as product types with multiplication, as you have to divide by an equivalence relation.
  • At this rate, you would expect subtraction to have some beautiful analogy to go with it, but alas I know of none. Dan Piponi has explored it a little through the antidiagonal, but it is far from a general analogy.
3
votes

The conventional answer is as given by @luqui, and I have nothing to add to that. The downside is that whilst you distinguish the alternants of the sum by tag ('constructor' in Haskell), you must access the components of the product by position. For homogeneous components as in a vector/array that's fine; but for typical data structures (record types) you want to access by 'field label' and abstract away the position. Haskell's record/label system a) does a very bad job of that; and b) is so deeply ingrained into the language it's proving almost impossible to improve -- see endless proposals and endless discussions resulting so far in no change.

Then an unconventional answer is indexed families aka 'indexed sets'. The idea has been developed mostly around the 'Set-Theoretic Data Structures' of D.L.Childs, for example this one. Childs'approach got a mention in the seminal paper on the Relational (database) Model Codd 1970.

The critical feature is that you can use any type to index the collection of components; the components are heterogeneous; and the compiler supports type-safe access (read and update) both by-component and whole-structure. The components might well be organised positionally within the structure, but that's an implementation detail hidden from the programmer. (Haskell's record system fails on this point.)

Do any programming languages have algebraic data types implemented that are not sum and product types?

You might or might not accept that SQL is a programming language. I might but mostly don't accept that SQL 'column names' are an implementation of 'Indexed families'. SQL's columns and rows are far too much oriented to physical layout (and indeed most vendors' SQL still allows positional notation for columns, even though it's been deprecated by the standard). That said, SQL is the nearest you'll find.

There's been a few extensible/anonymous record systems proposed/developed in Haskell (especially HList) or Haskell-like languages (like Ur/web), or even dear old Hugs' TRex. (See the Gaster & Jones paper for links to other attempts in FP languages.) All of them are limited because they're trying to put lipstick on Haskell's sum-of-product types.

0
votes

I know Sum, Product, Exponential and Recursive