Revision of polymorphic STUArrays with limitations

Question

I want to implement a dynamic programming algorithm that is polymorphic in the type of evaluation; here is a simplified version of 1D without boundary conditions:

{-# LANGUAGE ConstraintKinds, FlexibleContexts, RankNTypes, ScopedTypeVariables #-} import Control.Monad import Control.Monad.ST.Strict import Data.Array.ST import Data.Array.Unboxed dynamicProgrammingSTU :: forall ei . ( IArray UArray e, forall s. MArray (STUArray s) e (ST s), Ix i ) => (forall m . Monad m => (i -> me) -> (i -> me)) -> (i, i) -> (i -> e) dynamicProgrammingSTU prog bnds = (arr !) where arr :: UArray ie arr = runSTUArray resultArrayST resultArrayST :: forall s . ST s (STUArray sie) resultArrayST = do marr <- newArray_ bnds forM_ (range bnds) $ \i -> do result <- prog (readArray marr) i writeArray marr i result return marr 

The restriction does not work;

  Could not deduce (MArray (STUArray s) e (ST s)) arising from a use of `newArray_' from the context (IArray UArray e, forall s. MArray (STUArray s) e (ST s), Ix i) bound by the type signature for dynamicProgrammingSTU :: (IArray UArray e, forall s. MArray (STUArray s) e (ST s ), Ix i) => (forall (m :: * -> *). Monad m => (i - > me) -> i -> me) -> (i, i) -> i -> e at example2.hs:(17,1)-(27,15) Possible fix: add (MArray (STUArray s) e (ST s)) to the context of the type signature for resultArrayST :: ST s (STUArray sie) or the type signature for dynamicProgrammingSTU :: (IArray UArray e, forall s. MArray (STUArray s) e (ST s), I xi) => (forall (m :: * -> *). Monad m => (i -> m e) -> i -> me) -> (i, i) -> i -> e or add an instance declaration for (MArray (STUArray s) e (ST s)) In a stmt of a 'do' block: marr <- newArray_ bnds In the expression: do { marr <- newArray_ bnds; forM_ (range bnds) $ \ i -> do { ... }; return marr } In an equation for `resultArrayST': resultArrayST = do { marr <- newArray_ bnds; forM_ (range bnds) $ \ i -> ...; return marr } Failed, modules loaded: none. 

To summarize, Could not deduce (MArray (STUArray s) e (ST s)) from the context forall s. MArray (STUArray s) e (ST si) Could not deduce (MArray (STUArray s) e (ST s)) from the context forall s. MArray (STUArray s) e (ST si) . Note that adding a constraint to resultArrayST just pushes the problem to runSTUArray .

Currently, I know of four erroneous decisions:

• Avoid problems with the STArray box or just non-monodic Array s, possibly using seq and bang patterns to alleviate the memory problems that arise.
• Violation of the type system with unsafeFreeze and unsafePerformIO , for which the restriction of protection MArray IOUArray e IO works fine.
• This is a solution to a similar problem using an instance of typeclass and an entry for each type of "unboxable".
• This one uses GHC rewrite rules to select a different function for each type (and the generic version of STArray ).

However, I ask this question in the hope that modern language extensions such as ConstraintKinds can allow me to express my original intention for the forall s. MArray (STUArray s) e (ST s) code forall s. MArray (STUArray s) e (ST s) forall s. MArray (STUArray s) e (ST s) .

Answer 1

Given the legendary utility of the Haskell community, the lack of an answer at the moment is convincing evidence of the lack of a good solution in the current type of system.

I have already outlined the erroneous decisions in the question, so I will just post the full 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 sie) readSTUArray :: forall s i. Ix i => STUArray sie -> i -> ST se writeSTUArray :: forall s i. Ix i => STUArray sie -> 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 eij . ( Unboxable e, Ix i, Ix j, Enum i, Enum j ) => (forall m . (Monad m, Applicative m) => (i -> j -> me) -> (i -> j -> me)) -> (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