Solution for an "island filled with rain" problem from Google or "walls filled with rain" from Twitter. Uses Data.Sequence to actually find a solution in one pass. http://b.ja.rtur.me/twitter-interview-question-solution/

island.hs

module Main where

import Data.Sequence

--     *
-- *ww**w*
-- **w****
-- *******
sq = fromList [3,2,1,3,4,2,3]

-- This is the function you would call.
waterVolume :: (Num a, Ord a) => Seq a -> a
waterVolume xs = wv' 0 xs
    where wv' acc xs = 
            case move (smin xs) 0 of
             (n, rs)  | Data.Sequence.null rs || Data.Sequence.length rs == 1 -> acc + n
                      | otherwise -> wv' (n+acc) rs

-- Find minimum of two ends. Sequence must be non-empty.
smin :: (Num a, Ord a) => Seq a -> (a, Either (ViewL a) (ViewR a))
smin xs = case (viewl xs, viewr xs) of
    (x :< rs, rs' :> x') | x <= x' -> (x, Left $ viewl rs)
                         | otherwise -> (x', Right $ viewr rs')

-- Move from specified end to the opposite. Reduces sequence. 
-- Will fail if sequence ends in the specified direction before encountering an
-- element greater or equals to the current level. This is intentional.
move :: (Num a, Ord a) => (a, Either (ViewL a) (ViewR a)) -> a -> (a, Seq a)
move (n, xxs) acc = 
    case xxs of 
        Left (x :< xs) -> move' (Left $ viewl xs) x (x <| xs)
        Right (xs :> x) -> move' (Right $ viewr xs) x (xs |> x)
    where move' xs x whole
             | x >= n = (acc, whole)
             | otherwise = move (n, xs) (acc + (n - x))