<p>I understand how Map is easily parallelizable - each computer/CPU can just operate on a small portion of the array.</p>

<p>Is Reduce/foldl parallelizable? It seems like each computation depends on the previous one. Is it just parallelizable for certain types of functions?</p>

Not sure what platform/language you're thinking of, but you can parallelize reduce operators like this:
```
```
// Original
result = null;
foreach(item in map) {
    result += item;
}

// Parallel
resultArray = array();
mapParts = map.split(numThreads);
foreach(thread) {
    result = null;
    foreach(item in mapParts[thread]) {
        result += item;
    }
    resultArray += result;    // Lock this!
}
waitForThreads();
reduce(resultArray);
```
```
As you can see, a parallel implementation is easily recursive.  You split the map up, operate on each part in its own thread, then perform another reduce once those threads are done to bring the pieces together.
(This is the programmatic reasoning behind
Piotr Lesnick's answer
.)