You normally see people interpret the “Algebraic” as abstract algebra, not the high school algebra most of us think about (polynomial rings). This article ties it back to polynomials, which is pretty damn cool.
Solid introduction to the algebra of data types. One additional fun thing you can do is perform differentiation on algebraic data types to get the zipper of that type. A zipper is a cursor for navigating through a type. If you have a tuple of two values, (a, a), which has the algebraic data type of P = a * a or P = a^2, you can differentiate the type with respect to a, getting dP/da = (d/da)(a^2), which simplifies to dP/da = 2a = Z, the type of the zipper; and indeed 2a (or a + a) is the type of a zipper for a pair, it can be either the left or the right value.
I think a good programmer should be able to apply the refactorings you get from all ~20 laws of algebra. This doesn’t require making the connection to algebra, but I see the connection as being useful in a couple of ways:
It’s a nice mnemonic. I, at least, will always remember the struct-of-enums <-> enum-of-structs refactoring by way the distributive law.
The algebra becomes much more valuable for large examples. You can see this in the post. The largest example is the red-black tree. I’m not sure who originally discovered that red black trees are equivalent to trees of uniform height containing 2-4 children and respectively 1-3 values, but I bet they thought real hard about it. I didn’t have to think at all. I just chugged some algebra, and the result came out.
I do wonder if there’s a useful automation that uses this algebra, or uses something built on its foundation. As an example of a successful automation of something in this vein, check out Derivatives of Regular Expressions. It’s a technique for using derivatives to parse regular expressions. It gives a simple and reasonably efficient regex parser.
So why does a function that cannot be called evaluate to exactly one value (f: ! -> A; A^0 = 1)? Does that mean that if we have a function that will never return, and we pass it to another function, that function should return one possible value? But which? What is happening there?
Does that mean that if we have a function that will never return, and we pass it to another function, that function should return one possible value?
Right, exactly. Since you can’t get any information out of f, it can’t usefully be used to parametrize any other function, so any function in terms of an f must be constant.
You normally see people interpret the “Algebraic” as abstract algebra, not the high school algebra most of us think about (polynomial rings). This article ties it back to polynomials, which is pretty damn cool.
Solid introduction to the algebra of data types. One additional fun thing you can do is perform differentiation on algebraic data types to get the zipper of that type. A zipper is a cursor for navigating through a type. If you have a tuple of two values,
(a, a), which has the algebraic data type ofP = a * aorP = a^2, you can differentiate the type with respect toa, gettingdP/da = (d/da)(a^2), which simplifies todP/da = 2a = Z, the type of the zipper; and indeed2a(ora + a) is the type of a zipper for a pair, it can be either the left or the right value.Yeah zippers as derivatives is amazing. Some links for the curious:
Arguably longer still, since it’s possible to implement sum types in terms of closures, and lambda calculus has been around since the late 50s.
This is one of the better introductions I’ve read. But it still leaves one wondering, what else can we do with it, outside of parlor tricks.
I think a good programmer should be able to apply the refactorings you get from all ~20 laws of algebra. This doesn’t require making the connection to algebra, but I see the connection as being useful in a couple of ways:
I do wonder if there’s a useful automation that uses this algebra, or uses something built on its foundation. As an example of a successful automation of something in this vein, check out Derivatives of Regular Expressions. It’s a technique for using derivatives to parse regular expressions. It gives a simple and reasonably efficient regex parser.
So why does a function that cannot be called evaluate to exactly one value (
f: ! -> A; A^0 = 1)? Does that mean that if we have a function that will never return, and we pass it to another function, that function should return one possible value? But which? What is happening there?Right, exactly. Since you can’t get any information out of
f, it can’t usefully be used to parametrize any other function, so any function in terms of anfmust be constant.:-)