Given the legendary helpfulness of the Haskell community, the lack of an answer at this point is a strong indication that there's no good solution in the current type system.
I've already outlined the flawed solutions in the question, so I'll just post a complete version of my example. This is basically what I used to solve most alignment problems on Rosalind:
{-# LANGUAGE FlexibleContexts, RankNTypes, ScopedTypeVariables #-}
import Control.Applicative
import Control.Monad
import Control.Monad.ST
import Data.Maybe
import Data.Array.ST
import Data.Array.Unboxed
class IArray UArray e => Unboxable e where
newSTUArray_ :: forall s i. Ix i => (i, i) -> ST s (STUArray s i e)
readSTUArray :: forall s i. Ix i => STUArray s i e -> i -> ST s e
writeSTUArray :: forall s i. Ix i => STUArray s i e -> i -> e -> ST s ()
instance Unboxable Bool where
newSTUArray_ = newArray_
readSTUArray = readArray
writeSTUArray = writeArray
instance Unboxable Double where
newSTUArray_ = newArray_
readSTUArray = readArray
writeSTUArray = writeArray
{-
Same for Char, Float, (Int|Word)(|8|16|32|64)...
-}
{-# INLINE dynamicProgramming2DSTU #-}
dynamicProgramming2DSTU
:: forall e i j . (
Unboxable e,
Ix i,
Ix j,
Enum i,
Enum j
)
=> (forall m . (Monad m, Applicative m) => (i -> j -> m e) -> (i -> j -> m e))
-> (i -> j -> Maybe e)
-> (i, i)
-> (j, j)
-> (i -> j -> e)
dynamicProgramming2DSTU program boundaryConditions (xl, xh) (yl, yh) = arrayLookup where
arrayLookup :: i -> j -> e
arrayLookup xi yj = fromMaybe (resultArray ! (xi, yj)) $ boundaryConditions xi yj
arrB :: ((i, j), (i, j))
arrB = ((xl, yl), (xh, yh))
resultArray :: UArray (i, j) e
resultArray = runSTUArray resultArrayST
resultArrayST :: forall s. ST s (STUArray s (i, j) e)
resultArrayST = do
arr <- newSTUArray_ arrB
let acc xi yj = maybe (readSTUArray arr (xi, yj)) return $ boundaryConditions xi yj
forM_ [xl..xh] $ \xi -> do
forM_ [yl..yh] $ \yj -> do
result <- program acc xi yj
writeSTUArray arr (xi, yj) result
return arr