Recursive, single-pass, constant space solution to the watershed problem.

Water.hs

import Data.Array

waterVolume :: Array Int Int -> Int
waterVolume arr = go 0 minB maxB where
    (minB,maxB) = bounds arr

    go !acc lpos rpos
        | lpos >= rpos             = acc
        | leftHeight < rightHeight = segment leftHeight    1  acc lpos contLeft
        | otherwise                = segment rightHeight (-1) acc rpos contRight
        where
            leftHeight          = arr ! lpos
            rightHeight         = arr ! rpos
            contLeft  acc' pos' = go acc' pos' rpos
            contRight acc' pos' = go acc' lpos pos'

    segment limit move !acc' !pos cont
        | delta <= 0 = cont acc' pos'
        | otherwise  = segment limit move (acc' + delta) pos' cont
        where
            delta = limit - arr ! pos'
            pos'  = pos + move