Пересмотр полиморфных 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,

В настоящее время я знаю о четырех некорректных решениях:

1. Как избежать проблемы с коробкой STArrayс или просто не монадический Arrayс, возможно, используя seq и взрывные образцы, чтобы ослабить возникающие проблемы с памятью.
2. Взлом системы типов с unsafeFreeze а также unsafePerformIO, для которого чертово ограничение MArray IOUArray e IO работает отлично.
3. Это решение аналогичной проблемы с использованием класса типов и написанием экземпляров для каждого типа "unboxable".
4. Этот с использованием правил перезаписи GHC, чтобы выбрать разные функции для каждого типа (и общий STArray версия).

Однако я задаю этот вопрос в надежде, что современные языковые расширения, такие как ConstraintKinds может позволить мне выразить намерение моего исходного кода forall s. MArray (STUArray s) e (ST s),

Answer 1

Учитывая легендарную полезность сообщества Haskell, отсутствие ответа на данный момент является ярким свидетельством того, что в нынешней системе типов нет хорошего решения.

Я уже обрисовал в общих чертах ошибочные решения в этом вопросе, поэтому я просто опубликую полную версию моего примера. Это в основном то, что я использовал для решения большинства проблем выравнивания на Розалинд:

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