Parallel fold

In one of my previous posts about recursive morphisms I end the text with question: how to parallelize it? Consider one of list recursive morphisms application - left folding of lists. Each result depends on previous result and seems like non-paralellizable. It looks like:

foldl($, {a, b, c, d}) = ((a $ b) $ c) $ d

where $ is some abstract operation. But if <$, {a, b, c, d}> is semi-group then we can do next:

Let
    x = a $ b
    y = c $ d
(x $ c) $ d = x $ (c $ d) = x $ y

because $ is associative operation. So, we see that we have 2 sub-expressions: x and y which can be evaluated in parallel: (a $ b) $ (c $ d).

If $ is + it looks like, for example:

foldl(+, {1, 2, 3, 4})

1   2    3   4
  3   ||   7
      10

Can we parallelize more complex expressions (not special related to folding)? For example, a + b - c - d ? Yes. If {a, b, c, d} is group then we can replace any '.. - x' by '.. + (-x)' where (-x) is the opposite element: our parallelized function must do something like this:

<pre>if op is not associative: op = op-1 y = -y result <- x op y </pre> where op op-1 = id. Fo sum. groups +-1 is -, for prod. groups *~-1 is ~/.