Tài liệu STArray cho người mới và các câu hỏi liên quan đến tiểu bang/ST

Question

Tôi có một thời gian khó khăn để hiểu được STArray từ tài liệu và các thảo luận/thảo luận khác mà tôi đã tìm thấy thông qua Google. Tôi có thêm một số câu hỏi liên quan bên dưới.

Theo tài liệu, STArray s là

mảng đóng hộp và không có hộp bọc Mutable trong ST đơn nguyên.

này đã cho tôi ấn tượng, đó STArray có nghĩa là để được sử dụng như một bang được thông qua xung quanh giữa chức năng (tưởng tượng bạn có một vector mà đã được cập nhật thường xuyên).

Rõ ràng đây được sử dụng khác nhau mặc dù:

ST s (STArray s a e) 

tình trạng s ở đây là gì? Nếu nó được sử dụng trong nội bộ, thì tại sao điều này không bị ẩn khỏi người dùng?

này cũng có nghĩa, nếu chúng ta muốn sử dụng một STArray s Int Int được thông qua xung quanh như nhà nước, người ta sẽ xác định

type StateArray a = Control.Monad.State (ST s (STArray s Int Int)) a 

mà có vẻ khá cồng kềnh.

Cuối cùng,

• sự khác biệt giữa ST và State là gì?
• sự khác biệt giữa STArray và IOArray, nếu ST và IO có nghĩa là gì để sử dụng "nội bộ"?

Cảm ơn bạn !!

Answer 1

ST là một đơn vị trong đó một loại giới hạn tác dụng phụ được cho phép, cụ thể là các tham chiếu có thể thay đổi và mảng có thể thay đổi. Do đó, nó cho phép bạn thực hiện các chức năng thuần túy như được nhìn thấy từ thế giới bên ngoài, nhưng sử dụng các đột biến bên trong.

Điều này khác với State, điều này chỉ giả tạo đột biến bằng cách phân luồng trạng thái thông qua tính toán của bạn dưới dạng đầu vào và đầu ra bổ sung. Sự khác biệt là quan trọng khi thực hiện một số thuật toán bắt buộc, bởi vì đôi khi chúng cần đột biến để được triển khai hiệu quả. Ví dụ bằng cách sử dụng một mảng thông thường trong một đơn nguyên State, bạn chỉ có thể sửa đổi nó bằng cách tạo bản sao, trong khi với ST bạn có thể có đột biến thực sự tại chỗ.

Lý do tại sao chúng tôi có cả ST và IO là ST cung cấp đảm bảo mạnh hơn IO, cụ thể là:

1. ST không cho phép phản ứng phụ tùy ý ví dụ như truy cập vào hệ thống tập tin.
2. Chúng tôi có thể đảm bảo rằng các tác dụng phụ STkhông cho phép không thể thoát khỏi phạm vi runST và vì vậy nó có thể được xem là tinh khiết từ thế giới bên ngoài.

Lý do tại sao chúng tôi có thể đảm bảo rằng các tác dụng phụ không thể thoát có liên quan đến biến loại s. Vì bất kỳ hành động ST nào phải đa hình trong s, bạn không thể viết mã cho phép bất kỳ tham chiếu có thể thay đổi nào nhập hoặc rời khỏi phạm vi runST, vì trình kiểm tra loại sẽ phàn nàn rằng nó không thể đảm bảo rằng s của hành động của bạn và tham chiếu hoặc mảng giống nhau trừ khi chúng đến từ cùng một phạm vi runST.

Như một ví dụ về cách sử dụng đơn nguyên ST với mảng có thể thay đổi, đây là một thực hiện các Sieve of Erathostenes:

import Control.Monad 
import Control.Monad.ST 
import Data.Array.ST 
import Data.Array.Unboxed 

primesUpto :: Int -> [Int] 
primesUpto n = [p | (p, True) <- assocs $ sieve n] 

sieve :: Int -> UArray Int Bool 
sieve n = runSTUArray $ do 
    sieve <- newArray (2, n) True 
    forM_ [2..n] $ \p -> do 
     isPrime <- readArray sieve p 
     when isPrime $ do 
      forM_ [p*2, p*3 .. n] $ \k -> do 
       writeArray sieve k False 
    return sieve 

_{runSTUArray là một hình thức chuyên ngành của runST cho phép bạn xây dựng một mảng sử dụng đột biến bên trong, trước khi đóng băng và trả lại nó như một mảng bất biến. newArray, readArray và writeArray làm những gì bạn mong đợi.}

Như bạn có thể thấy, chữ ký loại sieve cho biết rằng đó là một hàm thuần túy, đúng vậy. Tuy nhiên, nó sử dụng đột biến ở bên trong để thực hiện nó một cách hiệu quả.