Xem lại STUArrays đa hình với các loại ràng buộc

Question

Tôi muốn thực hiện một thuật toán lập trình động đa hình trong loại điểm số; đây là phiên bản 1D được đơn giản hóa không có điều kiện biên:

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

Ràng buộc không hoạt động;

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. 

Để tóm tắt, Could not deduce (MArray (STUArray s) e (ST s)) from the context forall s. MArray (STUArray s) e (ST s i). Lưu ý rằng việc thêm ràng buộc vào resultArrayST chỉ cần đẩy vấn đề đến runSTUArray.

Tôi hiện biết của bốn giải pháp sai lầm:

1. Tránh các vấn đề với đóng hộp STArray s hoặc đơn giản là không monadic Array s, có lẽ sử dụng seq và tiếng nổ mô hình để giảm bớt những vấn đề bộ nhớ kết quả.
2. Phá vỡ hệ thống kiểu với unsafeFreeze và unsafePerformIO, mà ràng buộc đe dọa MArray IOUArray e IO hoạt động tốt.
3. This giải pháp cho một vấn đề tương tự bằng cách sử dụng một kiểu chữ và chữ viết cho mỗi loại 'không thể mở hộp'.
4. This một quy tắc viết lại GHC để chọn chức năng khác cho từng loại (và phiên bản STArray chung).

Tuy nhiên, tôi đặt câu hỏi này với hy vọng rằng tiện ích mở rộng ngôn ngữ hiện đại như ConstraintKinds có thể cho phép tôi thể hiện ý định mã ban đầu của mình là forall s. MArray (STUArray s) e (ST s).

Answer 1

Với sự hữu ích huyền thoại của cộng đồng Haskell, việc thiếu câu trả lời vào thời điểm này là một dấu hiệu mạnh mẽ cho thấy không có giải pháp tốt trong hệ thống kiểu hiện tại.

Tôi đã phác thảo các giải pháp thiếu sót trong câu hỏi, vì vậy tôi sẽ đăng phiên bản hoàn chỉnh của ví dụ của mình. Điều này về cơ bản là những gì tôi đã sử dụng để giải quyết hầu hết các vấn đề liên kết trên 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