This post is another gruop of fun algorithms (and data structures). These particular techniques are fun because they are a core concept that can be applied to many different situations by simply changing some structure that the algorithm is parameterized by. I won't go into much detail here, but rather provide links to articles with more depth.

The first one is the Guass-Jordan-Floyd-Warshall-McNaughton-Yamada algorithm. This algorithm solves a variety of problems, including finding shortest (max capcacity, most reliable, etc) pathes in a graph, finding an automata for a regular expression, and solving linear equations. I like the linked article because it takes some bits of abstract algebra and frames these problems in a general way, and then shows how you can see each problem as a special case of a single concept (asteration of a matrix). It also shows how these positive ring structures appear to be common in computer science. They also appear in systems of algebraic data structures, so naturally I wonder if these algorithm can be used to solve any problems in that realm.

# Finger Trees

The next algorithm is the fingertree, which is parameterized by a monoid. One introduction can be found here. This data structure has good asymptotics for a range of operations, and can be used for a wide range of applications. The implementation and uses are also described here. The thing I have used this structure for is simply as a sequence structure that supports log(n) update to an index, and log(n) splitting and concatenation, but there is more to it then just that.

The core ability that this structure gives you is that it takes a computation that you would like to do over a data set, and performs your calculation incrementally. This can be the calculation of indices, as when you use it as a sequence, but can also be for statistics on data that is updated over time, without recalculating over the whole data set. It can be used to get constant time access and log time update to properties of your tree, like its size, depth, the value of a predicate over its leaves, the greatest or least element (as in a priority queue), incremental regular expression matching

A couple other notes- there is a Haskell implementation here for the general structure, and the specific use as a random-access sequence here. There is also a Haskell package implementing a tree that accumulates both upwards (from the leaves) and downwards (from the root) found here.

# Lenses

The concept of a lens is a fascinating exploration into structure and computation, but there are plenty of resources on lenses, and I won't be able to do it justice here. The implementation here is the main one to look at, although there are a number of others, usually much simplier then the lens package. There are also implementations in other languages of course, I'm just more familiar with Haskell. One particularly good introduction starts here.

To tie this into the common thread in this post, the properties of a lens depends on the choice of constraints on the type- in the type `Lens s t a b = forall f. (Functor f) => (a -> f b) -> s -> f t` the type constructor "f" must be a functor, and this gives you a lens. If you constrain this type with Applicative, you get a traversal, and so on.

You can even take this further and go up to the Optic type of this library, `Optic p f s t a b = p a (f b) -> p s (f t)`, and look at what structure you get with a different profunctor. This can give you back lens when p is the function arrow, or Prisms with it is constrained by Choice, for example. This can lead you to different universes of lens- I once used this to create lens that could pass data between each other, although I admit I abandended that approach as too complex. This might be easier with profunctor lenses, I'm not sure.

I find this interesting because it seems like all of these universes of structures have their place, you just have to discover them.