I do not claim to be an expert on these subjects, but I might be able to shed some light on this idea.
Let's first consider category theory. Category theory is a study of mathematical structure at a very high level. The notion of a category is very general, and a great many mathematical objects form categories. Category theory was first considered to be incredibly pure and abstract, but as these things often go in mathematics, it turned out to have many uses in applied subjects, such as computer science and even quantum mechanics. Monads turned out to be of great use in reasoning about the semantics of functional programs, which are generally expressed denotationally (and hence do not force any kind of order to computation, just the result). From this it was also realised that the monad is also a very good design pattern for writing functional programs, and its usefulness has led to it being very prominent in the design of Haskell (ie the do notation etc). Functors, Applicatives, Monoids, all followed somewhat later as objects less powerful than monads but therefore also more applicative (no pun intended!).
However, category theory studies these kind of structures in a much more general way, which has turned out to be relevant in many areas of maths (and physics etc). As a non-expert it is not immediately clear how much of this might relate to complexity theory, but let's have a go.
Complexity theory is concerned with the feasibility of computation. Turing and others had showed that there were some functions that were not computable in general (for example the halting problem, the busy beaver problem etc), but the question of how easy a particular computation was in principle is a harder question in general. As you are probably aware, algorithms (which can be represented as Turing machines) can be put into complexity classes based on their asymptotic running time. There are a great many complexity classes that have been identified (see The Complexity Zoo) but comparatively little is known about the structure of these classes. The famous P = NP problem shows how difficult it is to reason about complexity.
From intuition about the nature of complexity classes and how difficult it is to prove relationships between them, I'd have thought it would be tricky to establish categories within complexity classes. Obviously the set of Turing machines forms a category, but the set of machines in O(n)? or the set of machines in P? This might well be a good research direction for complexity experts, and then again it may not! Personally I couldn't say without a lot more work.
Now lets consider your example of complexity within a Monoid, and parallelisation strategies. If it seems like this second section has little to do with the first, that is because I think these are very different concepts. First is the mathematics of categories and complexity, secondly there is the specifics of parallelising algorithms within certain design patterns.
If we know a certain type is a Monoid, what can we reason about the complexity of working with it? This is the class definition from Data.Monoid
class Monoid a where
mempty :: a
mappend :: a -> a -> a
mconcat :: [a] -> a
mconcat = foldr mappend mempty
Of course, we cannot say anything about the complexity because all we know is the type, as you surmised. The documentation has this to say about the default implementation of mconcat
within Data.Monoid:
-- ^ Fold a list using the monoid.
-- For most types, the default definition for 'mconcat' will be
-- used, but the function is included in the class definition so
-- that an optimized version can be provided for specific types.
The point I am trying to make is that mconcat
cannot necessarily be generalised from the complexity of the other operations. It would be difficult to prove in many cases that some, faster algorithm doesn't exist. mconcat
can be implemented manually in such a case.
You also mention automatically defining parallel strategies. Haskell certainly allows various different strategies to be defined, of which many useful ones are already in Control.Parallel.Strategies
. For example, parList applies a strategy in parallel to every element of a list:
parList :: Strategy a -> Strategy [a]
parList strat [] = ()
parList strat (x:xs) = strat x `par` (parList strat xs)
from this a parallel map function can be defined.
parMap :: Strategy b -> (a -> b) -> [a] -> [b]
parMap strat f xs = map f xs `using` parList strat
using :: a -> Strategy a -> a
using x s = s x `seq` x
Note that this allows for separation of implementation and parallelisation. I do not think that this kind of notion could be automated easily, especially just from annotations describing complexity of individual algorithms.
In summary then, it is possible that category theory might be a useful tool for future complexity research. However I do not think that this is likely to lead to automatic generation of parallelisation strategies.
mappend
forInteger
addition does not use constant time or space, with roughly the same implications formconcat
. Constant-time arithmetic is somewhat like Newtonian physics--a pleasant fiction that works if you only use small numbers. ;] Themappend
of a finite type--say, addition modulo 256 forWord8
--would better serve your point. – C. A. McCann