Haskell: bản đồ runST

Question

Tôi có một ràng buộc cho một loại [ST s (Int, [Int])] và tôi đang cố gắng áp dụng runST để mỗi phần tử sử dụng bản đồ như sau:

name :: [ST s (Int, [Int])] --Of Course there is a real value here 
map runST name 

này mang lại cho tôi một thông báo lỗi

Couldn't match expected type `forall s. ST s b0' 
    with actual type `ST s0 (Int, [Int])' 
Expected type: [forall s. ST s b0] 
    Actual type: [ST s0 (Int, [Int])] 
In the second argument of `map', namely `name' 
In the expression: map runST name 

Phải có điều gì đó tôi hiểu lầm. Tôi biết về runST and function composition, nhưng tôi không chắc liệu điều này có áp dụng hay không.

Cảm ơn mọi người!

Answer 1

Mỗi khi bạn chạy biến áp trạng thái với runST, nó hoạt động trên một số trạng thái cục bộ tách biệt với tất cả các biến thế bang khác. runST tạo một loại trạng thái mới và gọi đối số của nó với loại đó. Vì vậy, ví dụ, nếu bạn thực hiện

let x = runST (return()) 
    y = runST (return()) 
in (x, y) 

thì return() đầu tiên và thứ hai return() sẽ có các loại khác nhau: ST s1() và ST s2(), đối với một số loại chưa biết s1 và s2 đó được tạo ra bởi runST.

Bạn đang cố gắng gọi runST với đối số có loại trạng thái s. Đó không phải là loại trạng thái mà runST tạo, cũng không phải là bất kỳ loại nào khác mà bạn có thể chọn. Để gọi số runST, bạn phải chuyển một đối số có thể có bất kỳ loại trạng thái nào. Dưới đây là một ví dụ:

r1 :: forall s. ST s() 
r1 = return() 

Vì r1 là đa hình, trạng thái của nó có thể có bất kỳ loại, bao gồm bất cứ loại được chọn theo runST. Bạn có thể lập bản đồ runST qua một danh sách các đa hình r1 s (với -XImpredicativeTypes):

map runST ([r1, r1] :: [forall t. ST t()]) 

Tuy nhiên, bạn không thể ánh xạ runST qua một danh sách các phi đa hình r1 s.

map runST ([r1, r1] :: forall t. [ST t()]) -- Not polymorphic enough 

Loại forall t. [ST t()] nói rằng tất cả các thành phần danh sách đều có loại trạng thái t. Nhưng họ cần phải có tất cả các loại trạng thái độc lập bởi vì runST được gọi trên mỗi loại. Đó là ý nghĩa của thông báo lỗi.

Nếu có thể cung cấp cùng trạng thái cho tất cả các phần tử danh sách, thì bạn có thể gọi runST một lần như được hiển thị bên dưới. Không yêu cầu chữ ký loại rõ ràng.

runST (sequence ([r1, r1] :: forall t. [ST t()])) 

Answer 2

name của bạn không đủ đa hình. tuyên bố của bạn

name :: [ST s (Int, [Int])] 

có nghĩa là 'một danh sách các tính stateful trở về (Int, [Int]) có giống hệt nhaus'.Nhưng nhìn vào loại runST:

runST :: (forall s. ST s a) -> a 

loại này có nghĩa là 'một chức năng mà phải mất một tính toán stateful nơi scó thể bất cứ điều gì bạn đã bao giờ có thể tưởng tượng'. Những loại tính toán này không giống nhau. Và cuối cùng:

map runST :: [forall s. ST s a] -> [a] 

Bạn thấy đấy, danh sách của bạn nên chứa nhiều giá trị đa hình hơn hiện tại. s loại có thể khác nhau trong mỗi phần tử của danh sách, có thể không cùng loại như trong name. Thay đổi chữ ký loại name và tất cả đều phải OK. Nó có thể yêu cầu một số mở rộng để được kích hoạt, nhưng GHC sẽ có thể cho bạn biết cái nào.

Answer 3

tôi sẽ cố gắng giải thích lý do cho runST 's loại:

runST :: (forall s. ST s a) -> a 

Và tại sao nó không giống như này đơn giản:

alternativeRunST :: ST s a -> a 

Lưu ý rằng điều này sẽ alternativeRunST đã từng làm việc cho chương trình của bạn.

alternativeRunST cũng đã cho phép chúng tôi bị rò rỉ biến ra khỏi ST đơn nguyên:

leakyVar :: STRef s Int 
leakyVar = alternativeRunST (newSTRef 0) 

evilFunction :: Int -> Int 
evilFunction x = 
    alternativeRunST $ do 
    val <- readSTRef leakyVar 
    writeSTRef leakyVar (val+1) 
    return (val + x) 

Sau đó, bạn có thể đi trong ghci và làm:

>>> map evilFunction [7,7,7] 
[7,8,9] 

evilFunction không referentially minh bạch!

Btw, để thử nó ra cho mình đây là "xấu ST" khuôn khổ cần thiết để chạy đoạn code trên:

{-# LANGUAGE GeneralizedNewtypeDeriving #-} 
import Control.Monad 
import Data.IORef 
import System.IO.Unsafe 
newtype ST s a = ST { unST :: IO a } deriving Monad 
newtype STRef s a = STRef { unSTRef :: IORef a } 
alternativeRunST :: ST s a -> a 
alternativeRunST = unsafePerformIO . unST 
newSTRef :: a -> ST s (STRef s a) 
newSTRef = ST . liftM STRef . newIORef 
readSTRef :: STRef s a -> ST s a 
readSTRef = ST . readIORef . unSTRef 
writeSTRef :: STRef s a -> a -> ST s() 
writeSTRef ref = ST . writeIORef (unSTRef ref) 

Các thực runST không cho phép chúng tôi xây dựng như "ma quỷ" chức năng. Nó làm như thế nào? Nó kinda khó khăn, xem dưới đây:

Đang cố gắng để chạy:

>>> runST (newSTRef "Hi") 
error: 
    Couldn't match type `a' with `STRef s [Char]' 
... 

>>> :t runST 
runST :: (forall s. ST s a) -> a 
>>> :t newSTRef "Hi" 
newSTRef "Hi" :: ST s (STRef s [Char]) 

newSTRef "Hi" không phù hợp (forall s. ST s a). Như cũng có thể được nhìn thấy sử dụng một ví dụ thậm chí đơn giản hơn, nơi GHC cho chúng ta một lỗi khá đẹp:

dontEvenRunST :: (forall s. ST s a) -> Int 
dontEvenRunST = const 0 

>>> dontEvenRunST (newSTRef "Hi") 
<interactive>:14:1: 
    Couldn't match type `a0' with `STRef s [Char]' 
     because type variable `s' would escape its scope 

Lưu ý rằng chúng ta cũng có thể viết

dontEvenRunST :: forall a. (forall s. ST s a) -> Int 

Và nó tương đương với bỏ qua forall a. như chúng ta đã làm trước đó.

Lưu ý rằng phạm vi của a lớn hơn so với s, nhưng trong trường hợp của newSTRef "Hi" giá trị của nó nên phụ thuộc vào s. Hệ thống kiểu không cho phép điều này.