Elegant solution for waterfall problem based on time traveling.

waterfall.hs

import Control.Monad.Tardis
import Data.Traversable

water :: Traversable t => t Int -> Int
water = foldr (+) 0 . flip evalTardis (0, 0) . traverse (go 0) where

    go :: Int -> Int -> Tardis Int Int Int
    go total height = do
        modifyForwards $ max height
        (leftmax, rightmax) <- (,) <$> getPast <*> getFuture
        modifyBackwards $ max height
        return $ total + min leftmax rightmax - height

main = print $ water [2,5,1,2,3,4,7,7,6]