import Control.Monad.ST
import Control.Monad
import Control.Applicative

import Data.Array.ST
import Data.STRef
import Data.Array
import Data.List

mkArray :: Ix i => (i -> e) -> (i, i) -> Array i e
mkArray f bounds = runSTArray $ do
    arr <- newArray_ bounds
    forM_ (range bounds) $ \i -> writeArray arr i (f i)
    return arr

-- | apply function to value at given index of array
modifyArray :: Ix i => STArray s i e -> i -> (e -> e) -> ST s ()
modifyArray arr ix f = do
    v <- readArray arr ix
    writeArray arr ix (f v)

-- | replace each element of array with sum of values up to this element
-- (inclusive)
sumArray :: (Ix i, Num n) => STArray s i n -> ST s ()
sumArray arr = getBounds arr >>= mksum . range
  where
    mksum (i:j:is) = do
        x <- readArray arr i
        modifyArray arr j (+ x)
        mksum (j:is)
    mksum _ = return ()