制約の種類を持つ多態性STUArraysの再訪

Question

スコア型で動的プログラミングアルゴリズム多相を実装したいと思います。境界条件のない簡略化された1Dバージョンです：

{-# LANGUAGE ConstraintKinds, FlexibleContexts, RankNTypes, ScopedTypeVariables #-} 

import Control.Monad 
import Control.Monad.ST.Strict 
import Data.Array.ST 
import Data.Array.Unboxed 

dynamicProgrammingSTU 
    :: forall e i . (
    IArray UArray e, 
    forall s. MArray (STUArray s) e (ST s), 
    Ix i 
) 
    => (forall m . Monad m => (i -> m e) -> (i -> m e)) 
    -> (i, i) 
    -> (i -> e) 
dynamicProgrammingSTU prog bnds = (arr !) where 
    arr :: UArray i e 
    arr = runSTUArray resultArrayST 

    resultArrayST :: forall s . ST s (STUArray s i e) 
    resultArrayST = do 
    marr <- newArray_ bnds 
    forM_ (range bnds) $ \i -> do 
     result <- prog (readArray marr) i 
     writeArray marr i result 
    return marr 

制約は機能しません。

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 - 
> m e) -> i -> m e) 
              -> (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 s i e) 
     or the type signature for 
      dynamicProgrammingSTU :: (IArray UArray e, 
             forall s. MArray (STUArray s) e (ST s), I 
x i) => 
             (forall (m :: * -> *). Monad m => (i -> m 
e) -> i -> m e) 
             -> (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. 

要約すると、Could not deduce (MArray (STUArray s) e (ST s)) from the context forall s. MArray (STUArray s) e (ST s i)。 resultArraySTに制約を追加すると、問題はrunSTUArrayにプッシュされます。

私は現在、4つの欠陥のある解決策を知っている：

1. おそらく結果としてメモリの問題を緩和するためにseqと強打のパターンを使用して、箱入りSTArray Sまたは単に非モナドArray sの問題を回避します。
2. unsafeFreezeとunsafePerformIOで型システムを打ち切っています。そのためには、制約条件MArray IOUArray e IOが問題なく動作します。
3. This同様の問題を解決するには、型クラスを使用し、インスタンスを 'unboxable'型ごとに記述します。
4. This GHC書き換えルールを使用して、それぞれのタイプごとに異なる機能（および一般的なSTArrayバージョン）を選択するものです。

しかし、私はConstraintKindsのような近代的な言語拡張は私がforall s. MArray (STUArray s) e (ST s)の私の元のコードの意図を表現できるようにすることができますことを期待して、この質問をしています。

Answer 1

ハスケルコミュニティの伝説的な有用性を考えれば、現時点での答えの欠如は、現在のタイプのシステムには良い解決策がないという強い示唆です。

私は既に問題の欠陥のある解決法を概説しているので、私は私の例の完全なバージョンを投稿します。これは、基本的に私がロザリンドで最も問題になっていた問題を解決するために使用したものです：

{-# 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