Có cách nào hợp lý để giải nén đơn nguyên trạng thái không?

Question

Tôi muốn có một chức năng như:

unzipState :: (MonadState s m) => m (a, b) -> (m a, m b) 

trong đó sẽ có một (stateful) tính toán rằng trả về một tuple, và sẽ quay trở lại hai phép tính (phụ thuộc).

Khó khăn là tất nhiên trong đó trích xuất các giá trị từ một hoặc các tính toán khác nên cập nhật trạng thái trong khác.

Một hữu ích (và động cơ thúc đẩy) ứng dụng là đơn nguyên ngẫu nhiên, thể hiện dưới dạng

{-# LANGUAGE Rank2types #-} 
import qualified System.Random as SR 
import Control.Monad.State 

type Random a = forall r. (State RandomGen r) => State r a 

và giả sử bạn có:

normal :: Random Double 
-- implementation skipped 

correlateWith :: Double -> Random (Double, Double) -> Random (Double, Double) 
correlateWith rho w = do 
         (u, v) <- w 
         return $ (u, p * u + (1 - p * p) * v) 

nó sẽ là khá tự nhiên để có thể viết:

let x = normal 
    y = normal 
    (u, v) = unzipState $ correlateWith 0.5 $ liftM2 (,) x y 
    ... now I am able to perform computation on u and v as correlated random variables 

Có cách nào hợp lý để thực hiện việc này không? Tôi đã vật lộn một chút, nhưng không xoay sở được gì cả. Hoogle cũng chẳng giúp được gì.

chỉnh sửa

câu trả lời lớn đã cho tôi thấy vấn đề của tôi là mập mờ. Tuy nhiên, ai đó có thể giải thích cho tôi lý do tại sao thực hiện sau đây trong python (mà tôi tin là đúng, nhưng chưa được thử nghiệm nhiều) không thể dịch được trong Haskell (với sự kỳ diệu của STrefs, đóng cửa và những thứ khác tôi thừa nhận tôi không nắm ;-)):

def unzipState(p): 
    flist, glist = [], [] 
    def f(state): 
     if not flist: 
      (fvalue, gvalue), newstate = p(state) 
      glist.insert(0, gvalue) 
      return (fvalue, newstate) 
     else: 
      fvalue = flist.pop() 
      return (fvalue, state) 
    def g(state): 
     if not glist: 
      (fvalue, gvalue), newstate = p(state) 
      flist.insert(0, fvalue) 
      return (fvalue, newstate) 
     else: 
      gvalue = glist.pop() 
      return (gvalue, state) 
    return (f, g) 

không phải là tôi nói rằng mã stateful có thể được dịch trong Haskell, nhưng tôi cảm thấy như sự hiểu biết lý do tại sao và khi (ngay cả trên một ví dụ) nó không thể được thực hiện sẽ nâng cao hiểu biết của tôi rất nhiều.

edit2

Bây giờ nó là tinh thể rõ ràng. Các functons f và g rõ ràng là không thuần túy, vì đầu ra của chúng không chỉ phụ thuộc vào giá trị của trạng thái.

Cảm ơn bạn lần nữa!

Answer 1

Đó là không thể để tạo chức năng chung unzipState thực hiện những gì bạn muốn, nếu chỉ vì bạn có thể không cung cấp đặc điểm chính thức cho hiệu quả dự định của nó. Nói cách khác, giả sử rằng bạn đã thực hiện một số chức năng unzipState. Làm thế nào để bạn biết rằng nó là chính xác? Bạn sẽ phải chứng minh rằng nó đáp ứng một số luật/phương trình, nhưng vấn đề ở đây là tìm những luật này ngay từ đầu.

Trong khi tôi nghĩ rằng tôi hiểu những gì bạn muốn làm, đơn vị Random cũng làm cho nó rõ ràng lý do tại sao nó không thể được thực hiện. Để thấy rằng, bạn phải bỏ cái dự án thực hiện cụ thể type Random a = ... và xem xét việc giải thích trừu tượng do

v :: Random a nghĩa là v là một phân phối khả các giá trị của loại a

Các "ràng buộc" hoạt động (>>=) :: Random a -> (a -> Random b) -> Random b chỉ đơn giản là cách để xây dựng phân bố xác suất mới từ phân phối xác suất cũ.

Bây giờ, điều này có nghĩa là unzipState chỉ đơn giản trả về một cặp phân phối xác suất, có thể được sử dụng để xây dựng các bản phân phối xác suất khác. Vấn đề là trong khi cú pháp do có vẻ rất gợi ý, nhưng bạn không thực sự lấy mẫu các biến ngẫu nhiên, bạn chỉ tính toán phân phối xác suất. Các biến ngẫu nhiên có thể được tương quan, nhưng phân phối xác suất không thể.

Lưu ý rằng có thể tạo một đơn nguyên khác nhau RandomVariable a tương ứng với các biến ngẫu nhiên. Tuy nhiên, bạn phải sửa không gian mẫu Ω trước. Việc thực hiện là

type RandomVariable a = Ω -> a 

---

Nếu bạn muốn cả hai biến ngẫu nhiên và khả năng mở rộng không gian mẫu tự động, bạn có thể cần hai thao tác bind

bind1 :: Random Ω a -> (a -> Random Ω b) -> Random Ω b 
bind2 :: Random Ω1 a -> (a -> Random Ω2 b) -> Random (Ω1,Ω2) b 

và một số phụ thuộc loại ma thuật để đối phó với sự gia tăng của các sản phẩm như (Ω1,(Ω2,Ω3)).

Answer 2

Tôi không hoàn toàn rõ ràng về cách bạn muốn điều này hoạt động - kể từ khi correlateWith hoạt động trên bộ dữ liệu, các biến tương quan có ý nghĩa gì độc lập? Giả sử bạn làm điều này:

let x = normal 
    y = normal 
    (u, v) = unzipState $ correlateWith 0.5 $ liftM2 (,) x y 
in do u1 <- u 
     v1 <- v 
     u2 <- u 
     u3 <- u 
     -- etc... 

mối quan hệ gì nên tồn tại giữa u1, u2, và u3?

Ngoài ra, một "biến ngẫu nhiên" như thế này có thể được chuyển đổi thành luồng lười vô hạn theo cách đơn giản. Ý nghĩa của những điều sau đây sẽ là gì?

let x = normal 
    y = normal 
    (u, v) = unzipState $ correlateWith 0.5 $ liftM2 (,) x y 
in do vs <- generateStream v 
     u1 <- u 
     if someCondition u1 then u else return u1 
     -- etc... 

Vì số lượng các giá trị lấy mẫu từ u thay đổi dựa trên u1, điều này dường như cho thấy rằng giá trị phi monadic ràng buộc để vs sẽ hồi tố phụ thuộc phần nào vào u1 là tốt, mà âm thanh nghi ngờ giống như các loại ma quái hành động ở khoảng cách mà Haskell tránh được.

Tôi sẽ nguy hiểm khi đoán rằng những gì bạn đang cố gắng hoàn thành không thể đơn giản được trang bị thêm trên đơn vị trạng thái PRNG đơn giản, nhưng có thể có các tùy chọn khác.

Answer 3

Có rất nhiều thứ liên quan đến các mones Bayes ở Haskell.Dưới đây là một tài liệu tham khảo: http://www.randomhacks.net/articles/2007/02/22/bayes-rule-and-drug-tests

Xem thêm "Hoàn toàn chức năng lười biếng lập trình không xác định" có sẵn từ trang này: http://www.cs.rutgers.edu/~ccshan/

Chỉnh sửa: Tôi cũng không hiểu tại sao bạn không thể chỉ cho correlateWith chữ ký loại sau đây, và chạy nó bên trong khối lệnh trực tiếp thay vì cố gắng "đẩy" trạng thái ngẫu nhiên trong một ràng buộc cho phép. correlateWith :: Double -> Random Double -> Random Double -> Random (Double, Double)