State Monad, dãy số ngẫu nhiên và mã đơn điệu

Question

Tôi đang cố gắng nắm bắt State Monad và với mục đích này, tôi muốn viết một mã đơn lẻ sẽ tạo ra một chuỗi các số ngẫu nhiên bằng cách sử dụng Trình tạo đồng phân tuyến tính (có thể không tốt , nhưng ý định của tôi là học Monad State, không xây dựng một thư viện RNG tốt.

Các máy phát điện chỉ này (Tôi muốn tạo ra một chuỗi các Bool s vì đơn giản):

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 

Đừng lo lắng về những con số, đây chỉ là một nguyên tắc cập nhật những hạt giống đó (theo để Công thức số) nên tạo một chuỗi giả ngẫu nhiên là Int s. Bây giờ, nếu tôi muốn tạo số ngẫu nhiên liên tục anh sẽ làm:

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

Ok, vì vậy tôi có thể tránh được soạn sẵn này bằng cách sử dụng một đơn nguyên nhà nước:

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 

Và cuối cùng:

getNRandSt n = replicateM n nextVal 

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

Ok, điều này làm việc tốt và cho tôi một danh sách n giả ngẫu nhiên Bool s cho mỗi hạt giống đã cho. Nhưng ...

Tôi có thể đọc những gì tôi đã làm (chủ yếu dựa trên ví dụ này: http://www.haskell.org/pipermail/beginners/2008-September/000275.html) và nhân rộng để thực hiện những việc khác. Nhưng tôi không nghĩ rằng tôi có thể hiểu những gì thực sự xảy ra đằng sau các chức năng ghi chú và đơn điệu (như replicateM).

Có ai có thể giúp tôi với một số nghi ngờ này không?

1 - Tôi đã cố gắng desugar chức năng nextVal để hiểu những gì nó làm, nhưng tôi không thể. Tôi có thể đoán nó chiết xuất trạng thái hiện tại, cập nhật nó và sau đó vượt qua trạng thái phía trước để tính toán tiếp theo, nhưng điều này chỉ dựa trên việc đọc đường này như thể nó là tiếng anh.

Làm cách nào để thực sự desugar chức năng này với các hàm >> = và trả về ban đầu?

2 - Tôi không thể hiểu chính xác các chức năng của put và get. Tôi có thể đoán rằng họ "đóng gói" và "giải nén" nhà nước. Nhưng cơ chế đằng sau đường do vẫn còn khó nắm bắt với tôi.

Vâng, mọi nhận xét chung khác về mã này đều được hoan nghênh. Thỉnh thoảng tôi gặp Haskell mà tôi có thể tạo ra một mã hoạt động và làm những gì tôi mong đợi, nhưng tôi không thể "làm theo đánh giá" như tôi đã quen với các chương trình bắt buộc.

Answer 1

Trình đơn tiểu bang trông có vẻ khó hiểu lúc đầu; chúng ta hãy làm như Norman Ramsey đề nghị, và đi qua làm thế nào để thực hiện từ đầu. Cảnh báo, điều này khá dài!

Trước tiên, Tiểu bang có hai thông số loại: loại chứa dữ liệu trạng thái và loại kết quả cuối cùng tính toán. Chúng tôi sẽ sử dụng tương ứng stateData và result làm biến loại cho chúng tại đây. Điều này có ý nghĩa nếu bạn nghĩ về nó; đặc tính xác định của một tính toán dựa trên trạng thái là nó thay đổi trạng thái trong khi tạo ra một đầu ra.

Ít rõ ràng là các nhà xây dựng kiểu mất một chức năng từ một trạng thái sang trạng thái biến đổi và kết quả, như vậy:

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

Vì vậy, trong khi các đơn nguyên được gọi là "Nhà nước", giá trị thực tế được bao bọc bởi đơn nguyên là tính toán dựa trên trạng thái, không phải giá trị thực tế của trạng thái được chứa. Lưu ý rằng, chúng ta không nên ngạc nhiên khi thấy rằng hàm runState được sử dụng để thực thi tính toán trong trạng thái đơn vị thực sự không có gì khác ngoài một trình truy cập cho chính hàm được bao bọc và có thể được định nghĩa như sau:

runState (State f) = f 

Vì vậy, điều đó có nghĩa là gì khi bạn xác định hàm trả về giá trị trạng thái? Chúng ta hãy bỏ qua một thời điểm thực tế rằng Nhà nước là một đơn nguyên, và chỉ cần nhìn vào các loại cơ bản. Đầu tiên, hãy xem xét chức năng này (mà không thực sự làm bất cứ điều gì với nhà nước):

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

Nếu bạn nhìn vào định nghĩa của Nhà nước, chúng ta có thể thấy rằng đây là loại stateDataInt, và loại result là Bool, do đó hàm được bao bọc bởi trình tạo dữ liệu phải có loại Int -> (Bool, Int). Bây giờ, hãy tưởng tượng một phiên bản không nhà nước của len2State - rõ ràng, nó sẽ có loại String -> Bool. Vì vậy, làm thế nào bạn sẽ đi về chuyển đổi một chức năng như vậy thành một trong những trở về một giá trị phù hợp với một wrapper Nhà nước?

Vâng, rõ ràng, hàm được chuyển đổi sẽ cần tham số thứ hai, một Int biểu thị giá trị trạng thái. Nó cũng cần trả lại giá trị trạng thái, một giá trị khác là Int. Vì chúng tôi không thực sự làm bất cứ điều gì với nhà nước trong chức năng này, chúng ta hãy chỉ làm điều hiển nhiên - vượt qua đó int ngay trên thông qua. Dưới đây là một chức năng của Nhà nước, được định nghĩa theo điều khoản của phiên bản Tiểu bang ít hơn:

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

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

Nhưng đó là loại ngớ ngẩn và dư thừa. Hãy khái quát hóa chuyển đổi để chúng ta có thể chuyển giá trị kết quả và biến bất kỳ thứ gì thành một hàm giống như trạng thá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) 

Điều gì xảy ra nếu chúng ta muốn một hàm thay đổi trạng thái? Rõ ràng chúng tôi không thể xây dựng một cái với convert, vì chúng tôi đã viết rằng để vượt qua trạng thái thông qua. Hãy giữ cho nó đơn giản, và viết một hàm để ghi đè lên trạng thái với một giá trị mới. Những loại loại nó sẽ cần? Nó sẽ cần một Int cho giá trị trạng thái mới, và tất nhiên sẽ phải trả về một hàm stateData -> (result, stateData), bởi vì đó là những gì mà trình bao bọc của chúng ta cần. Ghi đè giá trị trạng thái không thực sự có giá trị result hợp lý ngoài tính toán của Nhà nước, do đó kết quả của chúng tôi ở đây sẽ chỉ là (), bộ phần tử không có yếu tố đại diện cho "không có giá trị" trong Haskell.

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

Điều đó thật dễ dàng! Bây giờ, hãy thực sự làm điều gì đó với dữ liệu trạng thái đó. Hãy viết lại len2State từ trên vào một cái gì đó hợp lý hơn: chúng ta sẽ so sánh độ dài chuỗi với giá trị trạng thái hiện tại.

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

Chúng ta có thể khái quát hóa điều này thành công cụ chuyển đổi và chức năng của Tiểu bang, như trước đây không? Không hoàn toàn dễ dàng. Chức năng len của chúng tôi sẽ cần lấy trạng thái làm đối số, nhưng chúng tôi không muốn nó "biết" trạng thái. Lúng túng, thực sự. Tuy nhiên, chúng ta có thể viết một hàm trợ giúp nhanh để xử lý mọi thứ cho chúng ta: chúng ta sẽ cung cấp cho nó một hàm cần sử dụng giá trị trạng thái và nó sẽ chuyển giá trị vào và sau đó đóng gói mọi thứ trở lại thành một hàm trạng thái để lại len không ai khôn ngoan hơn.

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) 

Bây giờ, phần phức tạp - nếu chúng ta muốn kết hợp các chức năng này với nhau thì sao? Giả sử chúng ta muốn sử dụng lenState trên một chuỗi, sau đó tăng gấp đôi giá trị trạng thái nếu kết quả là false, sau đó kiểm tra chuỗi một lần nữa và cuối cùng trả về true nếu kiểm tra đã thực hiện. Chúng tôi có tất cả các phần chúng tôi cần cho công việc này, nhưng viết ra tất cả sẽ là một nỗi đau. Chúng ta có thể tạo ra một hàm tự động kết nối hai hàm với nhau mà mỗi hàm trả về các hàm giống như trạng thái không? Chắc chắn rồi! Chúng ta chỉ cần đảm bảo nó lấy làm đối số hai điều: hàm trạng thái được trả về bởi hàm đầu tiên và hàm nhận hàm result của hàm trước đó làm đối số. Hãy xem cách nó chỉ ra:

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

Tất cả những việc này đang áp dụng hàm thứ nhất cho một số dữ liệu trạng thái, sau đó áp dụng hàm thứ hai cho kết quả và dữ liệu trạng thái đã sửa đổi. Đơn giản, phải không?

Bây giờ, phần thú vị: Giữa chainStates và convert, chúng ta hầu như có thể biến bất kỳ sự kết hợp các chức năng nào của Nhà nước thành một chức năng được nhà nước kích hoạt! Điều duy nhất chúng ta cần bây giờ là một sự thay thế cho useState trả về dữ liệu trạng thái như là kết quả của nó, để chainStates có thể truyền nó cùng với các hàm không biết bất cứ điều gì về mẹo mà chúng ta đang kéo chúng.Ngoài ra, chúng tôi sẽ sử dụng lambdas để chấp nhận kết quả từ các chức năng trước đó và cung cấp cho họ tên tạm thời. Được rồi, chúng ta hãy làm điều này xảy ra:

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) 

Và thử nó ra:

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

Tất nhiên, chúng ta không thể quên nhà nước mà thực sự là một đơn nguyên mà kết thúc tốt đẹp các chức năng Nhà nước giống như và giữ chúng tôi cách xa họ, vì vậy không có chức năng tiện lợi nào của chúng tôi mà chúng tôi đã xây dựng sẽ giúp chúng tôi thực sự. Hay là họ? Trong một twist gây sốc, nó quay ra rằng đơn nguyên nhà nước thực cung cấp tất cả các chức năng tương tự, dưới tên gọi khác nhau:

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) 

Lưu ý rằng >> = là gần như giống hệt nhau để chainStates, nhưng không có cách nào tốt để định nghĩa nó bằng cách sử dụng chainStates. Vì vậy, để quấn thứ lên, chúng ta có thể viết lại ví dụ cuối cùng bằng thực Nhà nước:

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) 

Hoặc, tất cả kẹo lên với tương đương làm ký hiệu:

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

Trước hết, ví dụ của bạn quá phức tạp vì không cần lưu trữ val trong đơn nguyên trạng thái; chỉ hạt giống là trạng thái dai dẳng. Thứ hai, tôi nghĩ rằng bạn sẽ có may mắn hơn nếu thay vì sử dụng đơn nguyên trạng thái chuẩn, bạn thực hiện lại tất cả các đơn nguyên trạng thái và các hoạt động của nó, với các loại của chúng. Tôi nghĩ bạn sẽ học nhiều hơn theo cách này.Dưới đây là một vài tờ khai để giúp bạn bắt đầu:

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

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

Sau đó, bạn có thể viết từ nối của riêng bạn:

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

Cuối cùng

data Seed = Seed Int 
nextVal :: Mystate Seed Bool 

---

Đối với rắc rối desugaring của bạn, ký hiệu do bạn đang sử dụng khá tinh vi. Nhưng desugaring là một thủ tục cơ khí tại một thời điểm. Khi gần như tôi có thể làm ra, mã của bạn nên desugar như thế này (sẽ trở lại với các loại bạn gốc và mã, mà tôi không đồng ý với):

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

Để thực hiện cơ cấu tổ một chút rõ ràng hơn, tôi đã lấy những quyền tự do lớn với sự thụt đầu dòng.

Answer 3

Bạn đã có một vài câu trả lời tuyệt vời. Những gì tôi làm khi làm việc với các đơn vị nhà nước là trong tâm trí của tôi thay thế State s a với s -> (s,a) (sau khi tất cả, đó thực sự là những gì nó được).

Sau đó, bạn có được một kiểu cho ràng buộc mà trông giống như:

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

và bạn thấy rằng ràng buộc chỉ là một loại chuyên ngành của nhà khai thác hàm hợp, như (.)

Tôi đã viết một blog/hướng dẫn về trạng thái đơn nguyên here. Nó có lẽ không phải là đặc biệt tốt, nhưng đã giúp tôi grok điều tốt hơn một chút bằng cách viết nó.