In this case, I think they meant algebraic data type, since they mention it next to "pattern matching".

An algebraic data type is generally made up of two things: 1) structs or tuples, which are useful but in most (but not all languages); C/C++ has them for example; and 2) tagged or disjoint unions, which are different from C unions in that you can tell which one of the union choices is being used (A variant is a particular tagged union).

Tagged unions are super-useful for pattern matching, so you get code like:

    match rv {
        Ok(_) => {
            None
        }
        Err(CacheError::KeyNotFound) => {
            Some(Resp::NotFound)
        }
        Err(ref err) => Some(from_cache_err(err))
    }

which has a nice syntax, is type-safe and can be compiled reasonably efficiently.

The algebraic part means that these two features can be used in any combination with each other, and also refers to the link that, roughly 0 is the empty type, 1 is the unit type, structs correspond to multiplies (and gets called the product type), and unions to plus (so is called a sum type).

Why? Because if I have a tuple of a union of A or B or C, and another union of X or Y, I have 6 possible values in total, and (1+1+1) x (1+1) = 6.

You probably also want to complete your toolkit with functions which are then exponentiation.

Also, in any ADT system 0 should be exactly the empty sum and 1 exactly the empty product. This is what makes things hang together properly.

0 and 1 are just idiomatic though, correct? The important part, from my knowledge of abstract algebra, is that there exist an identity for any operation function () such that for all x in your domain, x () identity = x.

Oh sure, you can call them whatever you like. But if you have an ADT system which has a unit type that isn't quite the empty product then you'll be in for an interesting time at least.

E.g., this is true in Haskell and it causes there to be some "extra structure" which often has to be smoothed over. Lots of library functions exist just to do this smoothing.

And differentiation, which is useful for functional update of persistent data structures. https://chris-taylor.github.io/blog/2013/02/13/the-algebra-o...

That's nice, but I wouldn't call it particularly core to ADT systems. It also requires quite a bit more machinery to embed directly since you need to be able to talk about functors/containers.

In this context, ADT probably means algebraic data type: https://en.wikipedia.org/wiki/Algebraic_data_type. And I don't think your definition for abstract data type is right either: usually the language feature that automatically determines types from context is called type inference.

Besides what evanpw already answered.

Abstract Data Type were introduced by languages like CLU, Mesa and Modula-2 among others.

It means having modules that only export the type names, but not their definition, while exposing functions/procedures to operate in such types.

It is not the same as the ADTs in functional languages, although they are quite similar.

They're not similar at all. Algebraic data types are finite sums and (tensor) products. Abstract data types are existential types, which are infinite sums indexed by a kind.

The purpose of my remark is how they look like in terms of usage for the humble programmer.

They being similar how having a limited data structure (non extensible) with a set of functions that operate on it. Depending on the FP language ADTs can also partially hide their implementation like the Abstract Data Types in modular languages.

But I can also happily discuss the math theory and the denotational semantics about them across languages, but I don't think it will help for many readers.

What makes them weak?

When you unpack a weak existential type repeatedly, every time you get a fresh new type. When you unpack a strong existential repeatedly, you always get the same type.

Anyway, my original comment was wrong: in ML, every time you project a type component from a module, you always get the same type. So it's more like a strong existential. My bad.

Ah, gotcha. Thanks!

There are two conceptual errors here:

(0) Rust doesn't really have much support for abstract data types. What Rust has is something not too unlike Haskell: you can hide `struct` fields [though not `enum` constructors], but the `struct` remains concrete. With a bona fide abstract data type mechanism, as in ML, you can give a module a signature that reveals the existence, but not the representation, of its type components. I'm guessing this much representation hiding isn't fully compatible with Rust's goals, which require knowing the sizes of types statically, unless they're behind a layer of indirection.

(1) Abstract data types have no relation whatsoever to type inference. [Nor do algebraic data types for that matter.] An abstract data type is an existential type: a dependent pair consisting of a type `T`, and a value whose type is `F T`, for some type function `F`. The closest thing Rust has to existentials is trait objects, but these can't do everything that existentials can do.

I'm neither an ML nor Rust expert, but wouldn't Rust trait objects (which are basically type erasure wrappers over traits) approximate abstract data types?

With the caveat that there can only be one instance of it.