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))
}
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.
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.
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.
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 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.
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.
(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.
It means no need to explicitly define the type of a variable, the compiler infer it based on context.