발생합니다. (코드로 두 번째 문제가 생겼다 : 변경 가능한 ST 배열은 ST 모나드 외부에 의미있게 존재할 수 없으므로, runST 내부에서 하나를 반환하는 것은 불가능하며, 순수 함수로 전달하는 것은 불가능하다. "흥미롭지 않지만"독자적으로 혼란 스러울 수도 있습니다.이 답변의 최하단 부분을 참조하십시오.
에서 오는 것입니다. 일반적으로
유형으로 제한했습니다. 여기서 일어나는 것은
람다 임). 국번이 괄호 안에
입니다. 그래서 때 유형
입니다. 오류가 공평합니다. 특정 s에 대해 MArray a e (ST s)이 해당한다고 주장했습니다. 그러나 runST은 에 대해 각각s에 해당해야합니다. 그러나 오류는 매우 불분명합니다. 실제로 참조 할 수없는 새로운 유형의 변수를 도입하기 때문에 (어쨌든 결코 도움이되지는 않지만 "가능한 수정"은 의미가 없습니다).
명백한 질문은 "올바른 형식 서명을 쓸 수 있습니까?"입니다. 대답은 "... 일종의." (하지만 당신은 아마 싶지 않아.) 원하는 유형은 다음과 같을 것이다
ghci> :set -XConstraintKinds -XRank2Types
ghci> let bounds :: (forall s. MArray a e (ST s), Ix i) => a i e -> (i,i)
ghci| bounds arr = runST (getBounds arr)
ghci|
<interactive>:170:25:
Could not deduce (MArray a e (ST s))
arising from a use of `getBounds'
from the context (forall s. MArray a e (ST s), Ix i)
...
이 제약이 MArray a e (ST s)이 모든s을 위해 보유하고 있다고하지만, 우리는 여전히 유형의 오류가 발생합니다. "GHC does not support polymorphic constraints to the left of an arrow"이 나타나고 그 정보를 찾으려고 노력하면서 실제로 동일한 문제가 발생하여 오류를 설명하고 다음 해결 방법을 제공하는 an excellent blog post at "Main Is Usually A Function"을 발견했습니다. (그들은 또한 잘못된 일이 불가능하다는 것을 분명하게 보여주는 "잘못된 클래스 선언"이라는 우수한 오류 메시지를 얻었습니다. 이것은 아마도 GHC 버전이 다르기 때문일 것입니다.)
아이디어는 우리가 더 많은 것을 원할 때 일반적인 것입니다. 이제
ghci> :set -XNoFlexibleContexts -XNoConstraintKinds
ghci> -- We still need -XRank2Types, though
ghci> :set -XGADTs
ghci> data MArrayE a e m where
ghci| MArrayE :: MArray a e m => MArrayE a e m
ghci|
ghci>
, 우리는의 값을 가질 때마다하십시오 GADT 사용하여 우리가 (AB)에 의한 이러한 유형 클래스의 존재에 대한 명시적인 증거를 제공하기 위해, GHC에 내장 된 시스템에서 얻을 수있는 유형의 클래스 제약의 MArrayE a e m을 입력하면 값이 MArrayE 생성자로 구성되어야합니다. 이 생성자는 MArray a e m 제약 조건이있을 때만 호출 할 수 있으므로 MArrayE의 패턴 일치는 해당 제약 조건을 다시 사용할 수있게합니다. (유일한 다른 가능성은 해당 유형의 값이 정의되지 않았기 때문에 패턴 일치가 실제로 필요한 이유입니다.) 이제 우리는이를 bounds 함수에 대한 명시적인 인수로 제공 할 수 있으므로 bounds MArrayE arr :
ghci> :set -XScopedTypeVariables
ghci> let bounds :: forall a e i.
ghci| Ix i => (forall s. MArrayE a e (ST s)) -> a i e -> (i,i)
ghci| bounds evidence arr = runST (go evidence)
ghci| where go :: MArrayE a e (ST s) -> ST s (i,i)
ghci| go MArrayE = getBounds arr
ghci|
ghci> -- Hooray!
본문을 자체 기능으로 분해하고 거기에서 패턴 일치해야하는 기이함에 유의하십시오. 당신이 bounds의 인수 목록에서 패턴 일치하면 evidence의 s이 특정 값으로 너무 일찍 고정되므로이 값을 지정해야합니다. 그리고 더 높은 순위 타입에 대한 추론이 어렵 기 때문에 go에 대한 명시 적 타입을 제공해야합니다. 이는 범위가 지정된 타입 변수를 필요로합니다.
그리고 마지막으로, 원래의 코드로 돌아 : 내가 처음에 말했듯이
는 ghci> let randShuffleST :: forall a e i g. Ix i => (forall s. MArrayE a e (ST s))
ghci| -> a i e
ghci| -> g
ghci| -> (a i e, g)
ghci| randShuffleST evidence arr gen = runST $ go evidence
ghci| where go :: MArrayE a e (ST s) -> ST s (a i e,g)
ghci| go MArrayE = do _ <- getBounds arr
ghci| return (arr, gen)
ghci|
ghci> -- Hooray again! But...
이제 하나의 문제가 해결 남아있다. 위 코드에서 forall s. MArray a e (ST s) 제약 조건을 만족할 수 없기 때문에 forall s. MArrayE a e (ST s) 유형의 값을 생성하는 방법이 절대로 존재하지 않습니다.같은 이유로 원래 코드에서 STArray을 ST 외부로 반환하는 함수를 작성할 수 없기 때문에 유형 오류 없이도 randShuffleST을 쓸 수 없습니다.
이러한 두 가지 문제의 이유는 동일합니다 : an STArray's first parameter is the state thread it lives on. STArray에 대한 MArray 인스턴스는 instance MArray (STArray s) e (ST s)이므로 항상 유형이 ST s (STArray s i e)입니다. runST :: (forall s. ST s a) -> a 이후로 runST mySTArrayAction을 실행하면 s이 "누출"될 수 있습니다.
runSTArray :: Ix i => (forall s. ST s (STArray s i e)) -> Array i e
로보고 그 언 박싱 친구
runSTUArray :: Ix i => (forall s. ST s (STUArray s i e)) -> UArray i e.
당신은 또한 당신이 그 당신이 이제까지 당신의 변경 가능한 배열에 전화 할게 마지막 기능의 약속으로, 같은 일을
unsafeFreeze :: (Ix i, MArray a e m, IArray b e) => a i e -> m (b i e)
을 사용할 수 있습니다; freeze 함수는이 제한을 완화하지만 배열을 복사해야합니다. 똑같은 토큰으로,리스트가 아닌 배열을 함수의 순수한 버전으로 전달하고자한다면, 아마도 또한
thaw :: (Ix i, IArray a e, MArray b e m) => a i e -> m (b i e);
을 사용하면 unsafeThaw을 사용하면 제어 할 수없는 변경 불가능한 배열을 전달하기 때문에 여기에서 재앙이 될 것입니다. 이것은 우리 모두에게 같은 것을 제공하기 위해 결합합니다 :
ghci> :set -XNoRank2Types -XNoGADTs
ghci> -- We still need -XScopedTypeVariables for our use of `thaw`
ghci> import Data.Array.IArray
ghci> let randShuffleST :: forall ia i e g. (Ix i, IArray ia e)
ghci| => ia i e
ghci| -> g
ghci| -> (Array i e, g)
ghci| randShuffleST iarr gen = runST $ do
ghci| marr <- thaw iarr :: ST s (STArray s i e)
ghci| _ <- getBounds marr
ghci| iarr' <- unsafeFreeze marr
ghci| return (iarr', gen)
ghci|
ghci> randShuffleST (listArray (0,2) "abc" :: Array Int Char) "gen"
(array (0,2) [(0,'a'),(1,'b'),(2,'c')],"gen")
이 소요 O (N) 입력 불변의 배열을 복사하는 시간이 있지만-와 가 O (1) 시간을 동결 최적화-소요 STArray과 Array이 후드에서 같기 때문에 출력을위한 가변 배열. 특히 문제이 적용
, 우리는 다음과 같은 한 :
{-# LANGUAGE FlexibleContexts #-}
import System.Random
import Control.Monad
import Control.Applicative
import Control.Monad.ST
import Data.Array.ST
import Data.STRef
import Data.Array.IArray
updateSTRef :: STRef s a -> (a -> (b,a)) -> ST s b
updateSTRef r f = do
(b,a) <- f <$> readSTRef r
writeSTRef r a
return b
swapArray :: (MArray a e m, Ix i) => a i e -> i -> i -> m()
swapArray arr i j = do
temp <- readArray arr i
writeArray arr i =<< readArray arr j
writeArray arr j temp
shuffle :: (MArray a e (ST s), Ix i, Random i, RandomGen g)
=> a i e -> g -> ST s g
shuffle arr gen = do
rand <- newSTRef gen
[email protected](low,_) <- getBounds arr
when (rangeSize bounds > 1) .
forM_ (reverse . tail $ range bounds) $ \i ->
swapArray arr i =<< updateSTRef rand (randomR (low,i))
readSTRef rand
-- Two different pure wrappers
-- We need to specify a specific type, so that GHC knows *which* mutable array
-- to work with. This replaces our use of ScopedTypeVariables.
thawToSTArray :: (Ix i, IArray a e) => a i e -> ST s (STArray s i e)
thawToSTArray = thaw
shufflePure :: (IArray a e, Ix i, Random i, RandomGen g)
=> a i e -> g -> (a i e, g)
shufflePure iarr g = runST $ do
marr <- thawToSTArray iarr
g' <- shuffle marr g
iarr' <- freeze marr
return (iarr',g')
shufflePure' :: (IArray a e, Ix i, Random i, RandomGen g)
=> a i e -> g -> (Array i e, g)
shufflePure' iarr g =
let (g',g'') = split g
iarr' = runSTArray $ do
marr <- thaw iarr -- `runSTArray` fixes the type of `thaw`
void $ shuffle marr g'
return marr
in (iarr',g'')
을 다시 말하지만, 당신이 shufflePure에 Data.Array.Unsafe.unsafeFreeze와 동결을 대체 할 수; Array i e 인 경우 배열을 복사 할 필요가 없기 때문에 속도가 빨라집니다. runSTArray 함수는 unsafeFreeze을 안전하게 랩하므로 에는 문제가되지 않습니다. (두 개는 동일하며 PRNG 분할에 대한 세부 정보를 제공합니다.)
여기에서 무엇을 볼 수 있습니까? 중요한 것은 변경 가능한 코드 만이 변경 가능한 배열을 참조하며 가변적 인 배열 (즉)이 안에있는 내용을 반환합니다. shuffle은 내부 셔플을 수행하므로 PRNG 만 배열을 반환 할 필요가 없습니다. 순수한 인터페이스를 구축하려면, thaw 가변 배열에 변경 불가능한 배열을 넣고 을으로 바꾸고 그 다음에 freeze을 불변의 배열로 되 돌린다. 이는 중요합니다. 변경된 데이터가 순수한 세계로 다시 유출되는 것을 방지합니다.전달 된 배열은 변경할 수 없기 때문에 직접 변경할 수 없습니다. 반대로 가변 변경할 수 있기 때문에 변경할 수없는 배열로 변경할 수있는 배열을 직접 반환 할 수는 없으며 누군가 변경할 수 있다면 어떨까요?
위의 오류는 모두 runST의 부적절한 사용으로 인해 발생하기 때문에 위의 오류는 발생하지 않습니다. runST의 사용을 제한하고 순수한 결과를 얻은 후에 만 실행하면 모든 내부 상태 스레딩이 자동으로 발생할 수 있습니다. runST은 등급 2 유형의 유일한 기능이므로 심각한 유형의 이상 함을 유발할 수있는 유일한 곳입니다. 다른 모든 것들은 표준 타입 기반 추론을 필요로합니다. 아마도 s 상태 스레드 매개 변수를 일관성있게 유지하려고 생각할 지 모르지만 말입니다.
및 LO와 보라 :
*Main> let arr10 = listArray (0,9) [0..9] :: Array Int Int
*Main> elems arr10
[0,1,2,3,4,5,6,7,8,9]
*Main> elems . fst . shufflePure arr10 <$> newStdGen
[3,9,0,5,1,2,8,7,6,4]
*Main> elems . fst . shufflePure arr10 <$> newStdGen
[3,1,0,5,9,8,4,7,6,2]
*Main> elems . fst . shufflePure' arr10 <$> newStdGen
[3,9,2,6,8,4,5,0,7,1]
*Main> elems . fst . shufflePure' arr10 <$> newStdGen
[8,5,2,1,9,4,3,0,7,6]
성공, 긴 지속! (길이가 너무 길어서 정말이 답변의 길이는 유감입니다.)
+1 작업 솔루션입니다. 정확히 내가 요구 한 것은 아니지만 (runST 사용), 실제적이고 간결하며 실제적인 예제를 숭배한다. –