हास्केल: मानचित्र runST

Question

मैं एक एक प्रकार [ST s (Int, [Int])] के लिए बाध्यकारी है और मैं मानचित्र का उपयोग इस प्रकार प्रत्येक तत्व को runST लागू करने के लिए कोशिश कर रहा हूँ:

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

यह मैं एक त्रुटि संदेश देता है

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 

मुझे कुछ गलत समझना चाहिए। मुझे runST and function composition के बारे में पता है, लेकिन यह लागू होने पर अनिश्चित है।

हर किसी के लिए धन्यवाद!

Answer 1

प्रत्येक बार जब आप runST के साथ एक राज्य ट्रांसफॉर्मर चलाते हैं, तो यह कुछ स्थानीय राज्यों पर चलता है जो अन्य सभी राज्य ट्रांसफार्मर से अलग होते हैं। runST एक नया राज्य प्रकार बनाता है और उस प्रकार के साथ इसके तर्क को कॉल करता है। तो, उदाहरण के लिए, आप

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

तो पहले return() निष्पादित और दूसरा return() विभिन्न प्रकार होगा यदि: ST s1() और ST s2(), किसी अज्ञात प्रकार s1 और s2runST द्वारा बनाई गई हैं कि के लिए।

आप runST पर एक तर्क के साथ कॉल करने का प्रयास कर रहे हैं जिसमें राज्य प्रकार s है। यह राज्य प्रकार नहीं है कि runST बनाता है, न ही कोई अन्य प्रकार जिसे आप चुन सकते हैं। runST पर कॉल करने के लिए, आपको एक तर्क पारित करना होगा जिसमें कोई राज्य प्रकार हो सकता है। यहाँ एक उदाहरण है:

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

क्योंकि r1 बहुरूपी है, अपने राज्य सहित जो भी प्रकार runST से चयनित होता है किसी भी प्रकार, हो सकता है। आप (-XImpredicativeTypes के साथ) बहुरूपी r1 रों की एक सूची से अधिक runST मैप कर सकते हैं:

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

हालांकि, अगर आप गैर बहुरूपी r1 रों की एक सूची से अधिक runST मैप नहीं कर सकते।

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

प्रकार forall t. [ST t()] कहना है कि सभी सूची तत्वों राज्य प्रकार t है। लेकिन उन्हें सभी स्वतंत्र राज्य प्रकारों की आवश्यकता है क्योंकि प्रत्येक पर runST कहा जाता है। त्रुटि संदेश का मतलब यही है।

यदि सभी सूची तत्वों को एक ही स्थिति देना ठीक है, तो आप नीचे दिखाए गए अनुसार runST पर कॉल कर सकते हैं। स्पष्ट प्रकार हस्ताक्षर की आवश्यकता नहीं है।

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

Answer 2

आपका name पर्याप्त पॉलिमॉर्फिक नहीं है। अपने बयान

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

का अर्थ है '(इंट, [इंट]) लौटने स्टेटफुल संगणना की एक सूची है जो है ठीक उसीs'।लेकिन runST के प्रकार को देखो:

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

इस प्रकार का अर्थ है 'एक समारोह जो स्टेटफुल गणना जहां sकुछ भी आप कभी भी कल्पना कर सकते हैं हो सकता है लेता है'। गणना के इन प्रकार एक ही बात नहीं है। और अंत में:

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

आप देखते हैं कि आपकी सूची में अब से अधिक पॉलिमॉर्फिक मान होना चाहिए। s प्रकार सूची के प्रत्येक तत्व में भिन्न हो सकता है, यह name जैसा ही नहीं हो सकता है। name के प्रकार हस्ताक्षर बदलें, और सभी ठीक होना चाहिए। इसे कुछ एक्सटेंशन सक्षम करने की आवश्यकता हो सकती है, लेकिन जीएचसी आपको कौन सा बताने में सक्षम होना चाहिए।

Answer 3

मैं runST के प्रकार के लिए तर्क समझाने की कोशिश करेंगे:

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

और क्यों यह पसंद नहीं है यह सरल एक:

alternativeRunST :: ST s a -> a 

ध्यान दें कि यह alternativeRunST काम किया था होगा आपके कार्यक्रम के लिए

alternativeRunST भी हमें ST इकाई से बाहर चर लीक करने के लिए अनुमति होगी था:

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) 

तो फिर तुम GHCi में जा सकते हैं और कार्य करें:

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

evilFunction referentially पारदर्शी नहीं है!

Btw, यह अपने आप को बाहर की कोशिश करने के लिए यहाँ "बुरा अनुसूचित जनजाति" ढांचे ऊपर कोड चलाने के लिए आवश्यक है:

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

असली runST हमें इस तरह के "" बुराई कार्यों के निर्माण के लिए अनुमति नहीं है। इसे यह कैसे करना है? यह थोड़े मुश्किल है, नीचे देखें:

को चलाने के लिए कोशिश कर रहा है:

>>> 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"(forall s. ST s a) फिट नहीं करता है। यह भी एक भी सरल उदाहरण का उपयोग देखा जा सकता है, जहां GHC हमें एक बहुत अच्छा त्रुटि देता है:

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 

ध्यान दें कि हम भी

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

लिख सकते हैं और यह हम के रूप में forall a. को छोड़ते हुए के बराबर है पहले किया था

ध्यान दें कि a के दायरे s की तुलना में बड़ा है, लेकिन newSTRef "Hi" के मामले में अपने मूल्य s पर निर्भर होना चाहिए। प्रकार प्रणाली इस अनुमति नहीं देता है।