Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

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.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: