제약 종류가있는 다형성 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)) from the context forall s. MArray (STUArray s) e (ST s i). resultArrayST에 제약 조건을 추가하면 문제가 runSTUArray으로 푸시됩니다.

나는 현재 네 개의 결함이 솔루션을 알고 :

1. 아마도 그 결과 메모리 문제를 완화 seq와 강타 패턴을 사용하여, 박스 STArray s 또는 단순히 비 모나드 Array들과 함께 문제를 방지.
2. unsafeFreeze 및 unsafePerformIO을 사용하여 유형 시스템을 위반 했으므로 여기에는 구속 조건 MArray IOUArray e IO이 잘 적용됩니다.
3. This 비슷한 문제에 대한 typeclass를 사용하고 모든 '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