Water collected between towers

Water collected between towers is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Task

In a two-dimensional world, we begin with any bar-chart (or row of close-packed 'towers', each of unit width), and then it rains, filling any convex enclosures in the chart with water.

9               ██           9               ██    
8               ██           8               ██    
7     ██        ██           7     ██░░░░░░░░██    
6     ██  ██    ██           6     ██░░██░░░░██    
5 ██  ██  ██  ████           5 ██░░██░░██░░████    
4 ██  ██  ████████           4 ██░░██░░████████    
3 ██████  ████████           3 ██████░░████████    
2 ████████████████  ██       2 ████████████████░░██
1 ████████████████████       1 ████████████████████

In the example above, a bar chart representing the values [5, 3, 7, 2, 6, 4, 5, 9, 1, 2] has filled, collecting 14 units of water.

Write a function, in your language, from a given array of heights, to the number of water units that would be collected in this way, by a corresponding bar chart.

(See, for example, Water collected between towers on Stack Overflow, from which this example is taken).

JavaScript

ES6

Following cdk's Haskell solution at Stack Overflow:

<lang JavaScript>(() => {

   'use strict';

   const waterCollected = xs => {
       const maxToRight = scanr(max, 0, xs),
             maxToLeft = scanl(max, 0, xs),
             levels = zipWith(min, init(maxToLeft), tail(maxToRight));

       return zipWith((a, b) => a - b, levels, xs)
           .filter(x => x > 0)
           .reduce((a, b) => a + b, 0);
   }

   // GENERIC FUNCTIONS ----------------------------------------

   // zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
   const zipWith = (f, xs, ys) => {
       const ny = ys.length;
       return (xs.length <= ny ? xs : xs.slice(0, ny))
           .map((x, i) => f(x, ys[i]));
   }

   // scanl :: (b -> a -> b) -> b -> [a] -> [b]
   const scanl = (f, startValue, xs) => {
       const lst = [startValue];
       return (
           xs.reduce((a, x) => {
               const v = f(a, x);
               return (lst.push(v), v);
           }, startValue),
           lst
       );
   };

   // scanr :: (b -> a -> b) -> b -> [a] -> [b]
   const scanr = (f, startValue, xs) => {
       const lst = [startValue];
       return (
           xs.reduceRight((a, x) => {
               const v = f(a, x);
               return (lst.push(v), v);
           }, startValue),
           lst.reverse()
       );
   };

   // max :: Ord a => a -> a -> a
   const max = (a, b) => a > b ? a : b;

   // min :: Ord a => a -> a -> a
   const min = (a, b) => b < a ? b : a;

   // init :: [a] -> [a]
   const init = xs => xs.length ? xs.slice(0, -1) : undefined;

   // tail :: [a] -> [a]
   const tail = xs => xs.length ? xs.slice(1) : undefined;

   // TEST ---------------------------------------------------
   return [
       [1, 5, 3, 7, 2],
       [5, 3, 7, 2, 6, 4, 5, 9, 1, 2],
       [5, 5, 5, 5],
       [5, 6, 7, 8],
       [8, 7, 7, 6],
       [6, 7, 10, 7, 6]
   ].map(waterCollected);

   //--> [2, 14, 0, 0, 0, 0]

})();</lang>

Output:

<lang>[2, 14, 0, 0, 0, 0]</lang>