Dokumentacja STArray dla początkujących i pytania związane z State/ST

Question

Mam trudności z zrozumieniem STArray z dokumentacji i innych poradników/dyskusji znalezionych przez Google. Mam poniżej kilka powiązanych pytań.

Zgodnie z dokumentacją, STArray s są

Zmienne ramkach i Rozpakowanych tablice w monady ST.

To dało mi wrażenie, że STArray ma być używany jako państwowej przekazywane są wokół między funkcjami (wyobrazić masz wektor, który musi być często aktualizowane).

Widocznie ten stosowany jest inaczej choć:

ST s (STArray s a e) 

Jaki jest stan s tutaj? Jeśli jest używany wewnętrznie, dlaczego nie jest ukryty przed użytkownikiem?

Oznacza to również, jeśli chcemy użyć STArray s Int Int były przekazywane wokół jako państwa, należałoby zdefiniować

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

który wydaje się dość kłopotliwe.

Wreszcie

• jaka jest różnica między ST i State?
• Jaka jest różnica między STArray a IOArray, jeśli ST i są przeznaczone do użytku "wewnętrznego"?

Dziękuję!

Answer 1

ST to monada, w której dozwolony jest ograniczony typ skutków ubocznych, mianowicie zmienne odniesienia i zmienne tablice. W ten sposób można realizować funkcje, które są czyste, jak widać ze świata zewnętrznego, ale które wykorzystują wewnętrznie mutację.

To różni się od State, który tylko podrabia mutację poprzez gwintowanie stanu przez twoje obliczenia jako dodatkowe wejścia i wyjścia. Różnica jest ważna przy wdrażaniu pewnych imperatywnych algorytmów, ponieważ czasami potrzebują one skutecznej implementacji mutacji. Na przykład używając zwykłej tablicy w monadzie State, możesz ją modyfikować tylko wykonując kopię, podczas gdy z ST możesz mieć prawdziwą mutację w miejscu.

Powodem mamy zarówno ST i IO że ST zapewnia mocniejsze gwarancje niż IO, a mianowicie:

1. ST nie pozwala na dowolne efekty uboczne, takie jak na przykład dostępu do systemu plików.
2. Możemy zagwarantować, że efekty uboczne STczy allow nie mogą wymknąć się z zakresu runST, a więc mogą być postrzegane jako czyste ze świata zewnętrznego.

Powód, dla którego możemy zagwarantować, że skutki uboczne nie mogą uciec, jest powiązany ze zmienną typu s. Ponieważ każde działanie ST musi być polimorficzne w s, nie można pisać kodu, który pozwala dowolnymi zmiennymi odniesieniami wejść lub wyjść z zakresu runST, ponieważ kontroler typu będzie narzekał, że nie może zagwarantować, że s Twojego działania i odniesienia lub tablica są takie same , chyba że pochodzą z tego samego zakresu .

Jako przykład używając ST monady z modyfikowalnych tablic, tutaj jest wdrożenie sito 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 jest wyspecjalizowaną formą runST który pozwala zbudować tablicę używając mutację w środku, przed zamrożeniem go i zwróceniem go jako niezmienny układ. newArray, readArray i writeArray rób to, czego oczekujesz.}

Jak widać, sygnatura typu sieve wskazuje, że jest to czysta funkcja i tak właśnie jest. Jednak silnie wykorzystuje mutację wewnątrz, aby skutecznie ją wdrożyć.