Category theory and abstract algebra deal with the way functions can be combined with other functions. Complexity theory deals with how hard a function is to compute. It's weird to me that I haven't seen anyone combine these fields of study, since they seem like such natural pairs. Has anyone done this before?
As a motivating example, let's take a look at monoids. It's well known that if an operation is a monoid, then we can parallelize the operation.
For example in Haskell, we can trivially define that addition is a monoid over the integers like this:
instance Monoid Int where
mempty = 0
mappend = (+)
Now if we want to compute the sum of 0 to 999, we could do it sequentially like:
foldl1' (+) [0..999]
or we could do it in parallel
mconcat [0..999] -- for simplicity of the code, I'm ignoring that this doesn't *actually* run in parallel
But parallelizing this monoid makes sense only because mappend runs in constant time. What if this weren't the case? Lists, for example, are monoids where mappend does not run inconstant time (or space!). I'm guessing this is why there is no default parallel mconcat function in Haskell. The best implementation depends on the complexity of the monoid.
It seems like there should be a convenient way to describe the differences between these two monoids. We should then be able to annotate our code with these differences and have programs automatically choose the best algorithms to use depending on a monoid's complexity.