haskell - 制約の種類を持つポリモーフィック STUArray の再検討

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. STArrayボックス化されたs または単に非モナドs の問題を回避しArray、おそらくseqand bang パターンを使用して、結果として生じるメモリの問題を緩和します。
2. unsafeFreezeとを使用して型システムを壊します。unsafePerformIOこれには、ひどい制約が正常にMArray IOUArray e IO機能します。
3. タイプクラスを使用し、すべての「ボックス化できない」タイプのインスタンスを作成する同様の問題に対するこのソリューション。
4. これは GHC 書き換えルールを使用して、各タイプ (および汎用STArrayバージョン) ごとに異なる関数を選択します。

ConstraintKindsただし、最新の言語拡張により、元のコードの意図を表現できるようになることを期待して、この質問をしていforall s. MArray (STUArray s) e (ST s)ます。