A fun example is zippers. A zipper over some structure is a purely functional way to keep track of your "position" inside the structure, which ideally lets you move around it easily.
Normally, when we use lists, we do something to the head and recurse on the tail. This allows us to easily move forwards through the list, but what if we sometimes want to go backwards? It's very easy to come up with a structure that lets us do this: we just keep track of the previous elements of the list as well as the remaining ones. This is exactly what a zipper over a list is:
zipper [a] <=> ([a], [a])
So if we have the list [1,2,3,4], the zipper would let us represent [1,2,^3,4] where ^ is our position; it would look something like ([2, 1], [3, 4]). We could then move forwards to ([3,2,1], [4]) or backwards to ([1], [2,3,4]).
This is a very simple and elegant idea, but also very easy to come up with yourself; no need for any algebra. However, there is an interesting observation to be made: a zipper corresponds to the derivative of a type! I think crntaylor is going to cover the mechanics of this in a future post.
This gives us a couple of useful insights. For one, it means we can apply the derivative operation repeatedly to get as many "cursors" into our type as we want. We could have a zipper with two positions in the list, or three positions in the list, or whatever. Additionally, it also tells us how to generalize zippers to other types like trees. At least to me, this is not obvious and the algebra really helps here.
So we can go from the very simple structure of using ([a], [a]) to represent a position in [a] to having an arbitrary number of positions in arbitrary types like trees. I think that's pretty cool.
Another fun example is packing seven binary trees into one, using complex numbers. This is a bit more involved, so I'll let much better writers than me cover it: there's the original paper[1] as well as a nice blog post[2] about it. I think it's a very cool demonstration of how this sort of algebraic reasoning can be useful even with a fairly trivial algebraic structure.
Also, recognizing this sort of structure can help us organize our programs. Often, even trivial abstractions are useful just for organizing code even if you don't get any especial insight from them. For example, monoids are very trivial, but are extremely useful for writing libraries.
Also, I think this is exactly the sort of abstraction which would make writing generic programs much easier, but I do not know enough about generic programming to be sure. (Here it's "generic" in the Haskell sense--programs that operate based on a type's structure and apply to many different types rather than generic in the Java sense, which is just parametric polymorphism.) Just something else to look into if you're curious.
Do you know of any more of this cool stuff? I've already looked at 'Seven Trees In One' and zippers and want to go further. I'm just learning combinatorics and classes and want to relate it to programming structure.
You can read Huet's seminal paper on zippers [1]. I found that Edward Z Yang's article[2] explains well the more general zippers.
The generic operation of differentiation to create the the type of zipper is explained in this article[3] from Conor McBride.
Another fun fact about zippers is that they have a comonadic structure, ie from a zipper you can build a zipper of zippers that reifies the concept of moving the cursor. That comonadic structure can express "locality of rules" in cellular automata. This classic article[4] by Dan Piponi uses a 1D automaton. As an exercise, I described an implementation of Conway's game of life in a comonadic manner in [5].
Normally, when we use lists, we do something to the head and recurse on the tail. This allows us to easily move forwards through the list, but what if we sometimes want to go backwards? It's very easy to come up with a structure that lets us do this: we just keep track of the previous elements of the list as well as the remaining ones. This is exactly what a zipper over a list is:
So if we have the list [1,2,3,4], the zipper would let us represent [1,2,^3,4] where ^ is our position; it would look something like ([2, 1], [3, 4]). We could then move forwards to ([3,2,1], [4]) or backwards to ([1], [2,3,4]).This is a very simple and elegant idea, but also very easy to come up with yourself; no need for any algebra. However, there is an interesting observation to be made: a zipper corresponds to the derivative of a type! I think crntaylor is going to cover the mechanics of this in a future post.
This gives us a couple of useful insights. For one, it means we can apply the derivative operation repeatedly to get as many "cursors" into our type as we want. We could have a zipper with two positions in the list, or three positions in the list, or whatever. Additionally, it also tells us how to generalize zippers to other types like trees. At least to me, this is not obvious and the algebra really helps here.
So we can go from the very simple structure of using ([a], [a]) to represent a position in [a] to having an arbitrary number of positions in arbitrary types like trees. I think that's pretty cool.
Another fun example is packing seven binary trees into one, using complex numbers. This is a bit more involved, so I'll let much better writers than me cover it: there's the original paper[1] as well as a nice blog post[2] about it. I think it's a very cool demonstration of how this sort of algebraic reasoning can be useful even with a fairly trivial algebraic structure.
[1]: http://www.cs.toronto.edu/~yuvalf/7trees.pdf
[2]: http://blog.sigfpe.com/2007/09/arboreal-isomorphisms-from-nu...
Also, recognizing this sort of structure can help us organize our programs. Often, even trivial abstractions are useful just for organizing code even if you don't get any especial insight from them. For example, monoids are very trivial, but are extremely useful for writing libraries.
Also, I think this is exactly the sort of abstraction which would make writing generic programs much easier, but I do not know enough about generic programming to be sure. (Here it's "generic" in the Haskell sense--programs that operate based on a type's structure and apply to many different types rather than generic in the Java sense, which is just parametric polymorphism.) Just something else to look into if you're curious.