موناد الدولة ، تسلسل الأرقام العشوائية والرمز الأحادي

Question

أحاول أن أفهم موناد الدولة ، وبهذا الغرض أردت أن أكتب رمزًا أحاديًا من شأنه أن يولد سلسلة من الأرقام العشوائية باستخدام مولد متطابق خطي (ربما لم يكن جيدًا ، لكن نيتي هي مجرد تعلم موناد الدولة ، وليس بناء مكتبة RNG جيدة).

المولد هو هذا فقط (أريد توليد سلسلة من Boolق للبساطة):

type Seed = Int

random :: Seed -> (Bool, Seed)
random seed = let (a, c, m) = (1664525, 1013904223, 2^32)  -- some params for the LCG
                  seed' = (a*seed + c) `mod` m
              in  (even seed', seed')   -- return True/False if seed' is even/odd 

لا تقلق بشأن الأرقام ، فهذه مجرد قاعدة تحديث للبذور (وفقًا للوصفات العددية) يجب أن تولد تسلسل عشوائي زائف من Intس. الآن ، إذا أردت إنشاء أرقام عشوائية بشكل متتابع سأفعل:

rand3Bools :: Seed -> ([Bool], Seed)
rand3Bools seed0  = let (b1, seed1) = random seed0
                        (b2, seed2) = random seed1
                        (b3, seed3) = random seed2
                    in  ([b1,b2,b3], seed3)

حسنًا ، لذلك يمكنني تجنب هذا الغلاية باستخدام موناد الدولة:

import Control.Monad.State

data Random {seed :: Seed, value :: Bool}

nextVal = do 
   Random seed val <- get 
   let seed' = updateSeed seed
       val'  = even seed'
   put (Random seed' val')
   return val'

updateSeed seed = let (a,b,m) = (1664525, 1013904223, 2^32) in (a*seed + c) `mod` m

وأخيرا:

getNRandSt n = replicateM n nextVal 

getNRand :: Int -> Seed -> [Bool]
getNRand   n seed = evalState (getNRandStates n) (Random seed True)

حسنًا ، هذا يعمل بشكل جيد ويعطيني قائمة من عشاق N n BoolS لكل بذرة معينة. لكن...

يمكنني قراءة ما قمت به (بناءً على هذا المثال بشكل رئيسي: http://www.haskell.org/pipermail/beginners/2008-Sepmbember/000275.html ) وتكرارها للقيام بأشياء أخرى. لكنني لا أعتقد أنني أستطيع أن أفهم ما يحدث بالفعل وراء الوظائف المسلحة والماجستية (مثل النسخ المتماثل).

هل يمكن لأي شخص مساعدتي في بعض هذه الشكوك؟

1 - لقد حاولت desugar وظيفة Nextval لفهم ما يفعله ، لكنني لم أستطع. يمكنني أن أخمن أنها تستخرج الحالة الحالية ، وتحديثها ، ثم تمرير الحالة إلى الأمام إلى الحساب التالي ، ولكن هذا يعتمد فقط على قراءة هذا السكر كما لو كان الإنجليزية.

كيف يمكنني حقًا أن أتخلص من هذه الوظيفة إلى الأصل >> = وإرجاع وظائف خطوة بخطوة؟

2 - لم أستطع فهم ما بالضبط put و get الوظائف تفعل. أستطيع أن أخمن أنهم "حزمة" و "فك" الدولة. لكن الميكانيكا وراء السكر لا تزال بعيدة المنال بالنسبة لي.

حسنًا ، أي ملاحظات عامة أخرى حول هذا الرمز مرحب بها للغاية. لقد سقطت أحيانًا مع Haskell أنه يمكنني إنشاء رمز يعمل ويفعل ما أتوقع أن يفعله ، لكن لا يمكنني "متابعة التقييم" لأنني اعتدت على القيام به بالبرامج الضرورية.

Answer 1

موناد الدولة تبدو نوعا من الإرباك في البداية ؛ دعونا نفعل كما اقترح نورمان رامزي ، ونمر عبر كيفية التنفيذ من الصفر. تحذير ، هذا طويل جدا!

أولاً ، تحتوي الحالة على معلمات نوعين: نوع بيانات الدولة ونوع النتيجة النهائية للحساب. سنستخدم stateData و result على التوالي كمتغيرات نوع بالنسبة لهم هنا. هذا منطقي إذا كنت تفكر في ذلك ؛ السمة المميزة للحساب القائم على الدولة هي أنه يعدل حالة أثناء إنتاج الناتج.

أقل وضوحًا هو أن منشئ النوع يأخذ ملف وظيفة من دولة إلى حالة معدلة ونتيجة ، مثل ذلك:

newtype State stateData result = State (stateData -> (result, stateData))

لذا ، بينما يطلق على الموناد اسم "الدولة" ، فإن القيمة الفعلية ملفوفة من قبل الموناد حساب قائم على الدولة, وليس القيمة الفعلية للحالة الواردة.

مع وضع ذلك في الاعتبار ، لا ينبغي أن نتفاجأ عندما نجد هذه الوظيفة runState يستخدم لتنفيذ حساب في موناد الحالة ليس في الواقع أكثر من ملحق لوظيفة ملفوفة نفسها ، ويمكن تعريفها على هذا النحو:

runState (State f) = f

إذن ماذا يعني ذلك عندما تحدد وظيفة تُرجع قيمة الحالة؟ دعونا نتجاهل للحظة حقيقة أن الدولة هي موناد ، وننظر فقط إلى الأنواع الأساسية. أولاً ، ضع في اعتبارك هذه الوظيفة (التي لا تفعل أي شيء في الواقع مع الدولة):

len2State :: String -> State Int Bool
len2State s = return ((length s) == 2)

إذا نظرت إلى تعريف الحالة ، يمكننا أن نرى هنا stateData النوع هو Int, ، و ال result النوع هو Bool, ، لذلك يجب أن يكون للوظيفة ملفوفة بواسطة مُنشئ البيانات النوع Int -> (Bool, Int). الآن ، تخيل نسخة أقل من الدولة len2State-على نحو مفعم بالحيوية ، سيكون له نوع String -> Bool. فكيف يمكنك تحويل مثل هذه الوظيفة إلى إحدى القيمة التي تناسب غلاف الحالة؟

حسنًا ، من الواضح أن الوظيفة المحولة ستحتاج إلى أخذ معلمة ثانية ، Int تمثيل قيمة الدولة. كما يحتاج إلى إرجاع قيمة الدولة ، والآخر Int. نظرًا لأننا لا نفعل أي شيء في الواقع مع الحالة في هذه الوظيفة ، دعنا نفعل الشيء الواضح-تمريرة من خلالها. فيما يلي وظيفة على شكل دولة ، محددة من حيث النسخة الخالية من الدولة:

len2 :: String -> Bool
len2 s = ((length s) == 2)

len2State :: String -> (Int -> (Bool, Int))
len2State s i = (len2' s, i)

ولكن هذا نوع من سخيفة ومتكررة. دعونا نعمم التحويل حتى نتمكن من تمرير قيمة النتيجة ، وتحويل أي شيء إلى وظيفة تشبه الحالة.

convert :: Bool -> (Int -> (Bool, Int))
convert r d = (r, d)

len2 s = ((length s) == 2)

len2State :: String -> (Int -> (Bool, Int))
len2State s = convert (len2 s)

ماذا لو كنا نريد وظيفة تغير الدولة؟ من الواضح أننا لا نستطيع بناء واحدة مع convert, ، منذ أن كتبنا ذلك لتمرير الدولة من خلال. دعنا نبقي الأمر بسيطًا ، ونكتب وظيفة للكتابة فوق الحالة بقيمة جديدة. ما نوع النوع الذي ستحتاجه؟ سوف تحتاج إلى Int بالنسبة لقيمة الدولة الجديدة ، وبالطبع سيتعين على وظيفة إرجاع وظيفة stateData -> (result, stateData), ، لأن هذا ما تحتاجه غلاف ولايتنا. الكتابة فوق قيمة الحالة لا تحتوي حقًا على عقلانية result القيمة خارج حساب الحالة ، لذلك ستكون النتيجة هنا فقط (), ، tuple عنصر الصفري الذي يمثل "لا قيمة" في هاسكل.

overwriteState :: Int -> (Int -> ((), Int))
overwriteState newState _ = ((), newState)

كان ذلك سهلا! الآن ، دعونا في الواقع قم بعمل ما مع بيانات الحالة. دعنا نعيد كتابة len2State من الأعلى إلى شيء أكثر عقلانية: سنقارن طول السلسلة بقيمة الحالة الحالية.

lenState :: String -> (Int -> (Bool, Int))
lenState s i = ((length s) == i, i)

هل يمكننا تعميم هذا إلى محول ووظيفة أقل من الدولة ، كما فعلنا من قبل؟ ليس بنفس السهولة. لنا len ستحتاج الوظيفة إلى أخذ الدولة كحجة ، لكننا لا نريد أن "يعرف عن" حالة. محرج ، في الواقع. ومع ذلك ، يمكننا كتابة وظيفة مساعدة سريعة تتعامل مع كل شيء بالنسبة لنا: سنعطيها وظيفة تحتاج إلى استخدام قيمة الحالة ، وسوف تمرر القيمة ثم قم بتعبئة كل شيء احتياطيًا في وظيفة على شكل حالة مغادرة len لا شيء في حيرة.

useState :: (Int -> Bool) -> Int -> (Bool, Int)
useState f d = (f d, d)

len :: String -> Int -> Bool
len s i = (length s) == i

lenState :: String -> (Int -> (Bool, Int))
lenState s = useState (len s)

الآن ، الجزء الصعب-ما إذا كنا نريد أن نربط هذه الوظائف معًا؟ دعنا نقول أننا نريد استخدام lenState في سلسلة ، ثم مضاعفة قيمة الحالة إذا كانت النتيجة خاطئة ، ثم تحقق من السلسلة مرة أخرى ، وأخيراً العودة إلى حد ما إذا كان هناك أي إجراء. لدينا جميع الأجزاء التي نحتاجها لهذه المهمة ، لكن كتابة كل شيء ستكون ألمًا. هل يمكننا عمل وظيفة تقوم تلقائيًا بتجميع وظيفتين تعيد كل وظائف تشبه الحالة؟ بالتأكيد شيء! نحتاج فقط إلى التأكد من أن الأمر يتطلب أمرينًا: وظيفة الحالة التي يتم إرجاعها بواسطة الوظيفة الأولى ، ودالة تأخذ الوظيفة السابقة result اكتب كحجة. دعونا نرى كيف اتضح:

chainStates :: (Int -> (result1, Int)) -> (result1 -> (Int -> (result2, Int))) -> (Int -> (result2, Int))
chainStates prev f d = let (r, d') = prev d
                       in f r d'

كل هذا يفعل هو تطبيق وظيفة الحالة الأولى على بعض بيانات الحالة ، ثم تطبيق الوظيفة الثانية على النتيجة وبيانات الحالة المعدلة. بسيطة ، أليس كذلك؟

الآن ، الجزء المثير للاهتمام: بين chainStates و convert, ، يجب أن نكون قادرين تقريبًا على تحويل أي مزيج من الوظائف الأقل الدولة إلى وظيفة تدعم الدولة! الشيء الوحيد الذي نحتاجه الآن هو بديل ل useState هذا يعيد بيانات الحالة كنتيجة لها ، بحيث يمكن للسلسلة نقلها إلى الوظائف التي لا تعرف أي شيء عن الخدعة التي نسحبها عليها. أيضًا ، سنستخدم Lambdas لقبول النتيجة من الوظائف السابقة ومنحهم أسماء مؤقتة. حسنًا ، لنجعل هذا يحدث:

extractState :: Int -> (Int, Int)
extractState d = (d, d)

chained :: String -> (Int -> (Bool, Int))
chained str = chainStates  extractState         $ \state1 ->
              let check1 = (len str state1) in
              chainStates (overwriteState (
                  if check1 
                  then state1 
                  else state1 * 2))             $ \ _ ->
              chainStates  extractState         $ \state2 ->
              let check2 = (len str state2) in
              convert (check1 || check2)

وجربها:

> chained "abcd" 2
(True, 4)
> chained "abcd" 3
(False, 6)
> chained "abcd" 4
(True, 4)
> chained "abcdef" 5
(False, 10)

بالطبع ، لا يمكننا أن ننسى أن الدولة هي في الواقع موناد تلتف الوظائف الشبيهة بالدولة وتبقينا بعيدًا عنها ، لذلك لن تساعدنا أي من وظائفنا الأنيقة التي بنيناها في الشيء الحقيقي. أم أنهم؟ في تطور مروع ، اتضح أن موناد الحالة الحقيقية يوفر جميع الوظائف نفسها ، تحت أسماء مختلفة:

runState (State s) = s
return r = State (convert r)
(>>=) s f = State (\d -> let (r, d') = (runState s) d in
                         runState (f r) d')
get = State extractState
put d = State (overwriteState d)

لاحظ أن >> = متطابق تقريبًا مع Stainstates ، ولكن لم تكن هناك طريقة جيدة لتحديدها باستخدام Stainstates. لذلك ، لإنجاز الأشياء ، يمكننا إعادة كتابة المثال النهائي باستخدام حقيقة حالة:

chained str = get                               >>= \state1 ->
              let check1 = (len str state1) in
              put (if check1 
                  then state1 else state1 * 2)  >>= \ _ ->
              get                               >>= \state2 ->
              let check2 = (len str state2) in
              return (check1 || check2)

أو ، كل ملبس مع ما يعادل أبرز:

chained str = do
        state1 <- get
        let check1 = len str state1
        _ <- put (if check1 then state1 else state1 * 2)
        state2 <- get
        let check2 = (len str state2)
        return (check1 || check2)

Answer 2

بادئ ذي بدء ، مثالك معقد للغاية لأنه لا يحتاج إلى تخزين val في موناد الدولة ؛ فقط البذرة هي الحالة المستمرة. ثانياً ، أعتقد أنه سيكون لديك حظ أفضل إذا بدلاً من استخدام Monad Standard State ، فإنك تقوم بإعادة تنفيذ جميع موناد الدولة وعملياتها بنفسك ، مع أنواعها. أعتقد أنك سوف تتعلم المزيد بهذه الطريقة. فيما يلي بعض الإعلانات لتبدأ:

data MyState s a = MyState (s -> (s, b))

get :: Mystate s s
put :: s -> Mystate s ()

ثم يمكنك كتابة الاتصالات الخاصة بك:

unit :: a -> Mystate s a
bind :: Mystate s a -> (a -> Mystate s b) -> Mystate s b

أخيراً

data Seed = Seed Int
nextVal :: Mystate Seed Bool

---

أما بالنسبة لمشاكلك في التخلص من do التدوين الذي تستخدمه هو متطور للغاية. لكن Desugaring هو إجراء ميكانيكي في الوقت المناسب. بالقرب من القريب ، يجب أن يتجسد الكود الخاص بك مثل هذا (العودة إلى الأنواع والرمز الأصلي ، الذي لا أتفق معه):

 nextVal = get >>= \ Random seed val ->
                      let seed' = updateSeed seed
                          val'  = even seed'
                      in  put (Random seed' val') >>= \ _ -> return val'

من أجل جعل هيكل التعشيش أكثر وضوحًا قليلاً ، أخذت حريات كبيرة مع المسافة البادئة.

Answer 3

لديك بضع ردود رائعة. ما أفعله عند العمل مع موناد الدولة في ذهني استبدل State s a مع s -> (s,a) (بعد كل شيء ، هذا هو حقا ما هو عليه).

يمكنك بعد ذلك الحصول على نوع لربط يشبه:

(>>=) :: (s -> (s,a)) ->
         (a -> s -> (s,b)) ->
         (s -> (s,b))

وترى أن الربط هو مجرد نوع متخصص من مشغل تكوين الوظائف ، مثل (.)

كتبت مدونة/تعليمي على موناد الولاية هنا. ربما لا يكون الأمر جيدًا بشكل خاص ، لكنه ساعدني في الحصول على الأشياء بشكل أفضل قليلاً من خلال كتابتها.