What are algebraic data types (algebraic data types or Adts)?

Question

Eventually I read in some articles related to functional programming the term algebraic data types, but I don’t really know what they are and I end up getting a little lost.

• What are algebraic data types (algebraic data types)?
• What differs it from a "non-ealgebraic" data type, for example, a array javascript?
• It has something to do with mathematics (see "algebraic name")?

Answer 1

Everything in computing has something to do with mathematics, computing is mathematics, not a different invention. Computations are abstractions that we use to express and solve problems, like mathematics.

Technically you already use the Algebraic Data Type because it is a kind fruit of the composition of other types. So an object is certainly an ADT.

The basic composition techniques are the sum and the product.

These types that you already create (such as classes, prototypes, tuples, registers and even vectors) are product-based types. Each type of composition has its space and coexists normally. That’s an ADT.

Already the enumeration is a kind of sum, IE, you work with one value among many possible (many may be only 2). In a Enum you have several members indicating different situations, but the value you will use is only one of them. A Union that some languages have (some variations such as tagged Union or Variant also) is a structure composed of different members, usually of different types (unlike the Enum), but that only one value will prevail and will be available. That’s an ADT.

The biggest difference is that this type of structure is expected to be something closed, that is, there will be no changes in its composition or behavior (including by inheritance). You can see more in An enumeration must be constant in the lifetime of the solution?. Therefore product types tend to be changed over time or even within the application execution itself. The types based on sum this is harder to happen, or should not even happen.

So we usually call ADT only the types that were created to be constant, that indicate something stable, even if strictly speaking others are also ADT.

I see a tendency for people to call ADT those kinds of sums that are composed of specific values. He’s an ADT, but it’s a more specific way. I’ll give an example in Rust because I know that the AP is studying the subject:

enum Optional<T> {
    None,
    Some(T)
}

So this guy named Optional has a value of two possible. Or it is the value called None, so it is a value that does not exist and cannot do anything extra with it; or it has a value called Some, which has an extra component attached to it, and in the example the extra value may be a genetic value established by T in every situation, and then you can do something with that value.

I’d wear something like that Pattern matching:

resultado : Optional<i32> = TentaObterResultado();
match resultado {
    Some(valor) => println!("O valor é {}", valor),
    None => println!("Não deu certo")
}

It could be more sophisticated than that:

enum Message {
    Quit,
    Move { x: i32, y: i32 },
    Write(String),
    ChangeColor(i32, i32, i32),
}

I put in the Github for future reference.

Sounds like a class, right? But only one of them can occur in each situation. That’s a tagged Union, that some people call ADT. Yes, it is an ADT, but all compositions of type are it if the expectation is to be closed.

Another difference that we can observe, although it is dependent on implementation is that you do not have to worry about certain details of the type, the language has already defined some standard behaviors for an ADT. So some people say they’re just enums glorified. He’s very simple, doesn’t have to take care of the details he usually needs in a class or struct.

I would say that the term ends up being used to say that it has a kind of powerful sum, but in a simplified way, with everything ready, more or less as happens with the Records that are fashionable now and various languages are implementing, and that are only classes (a type of product) with a few things ready for you. What people call ADT are just types of ready-to-use sum, but formally it’s a closed compound type.