Jak działa ST monad?

Question

Jak działa ST monad?

Rozumiem, że monada ST jest czymś w rodzaju młodszego brata IO, który z kolei jest monadą stanu z dodatkiem magii RealWorld. Mogę sobie wyobrazić stany i wyobrażam sobie, że RealWorld jest jakoś umieszczony w IO, ale za każdym razem, gdy piszę podpis typu ST s z monady św.

Weźmy na przykład ST s (STArray s a b). Jak tam działa s? Czy jest on po prostu używany do budowania jakiejś sztucznej zależności danych między obliczeniami bez możliwości odwoływania się jak stany w monadzie stanowej (ze względu na forall)?

Po prostu wyrzucam pomysły i byłbym naprawdę wdzięczny komuś bardziej kompetentnemu niż ja, aby mi to wyjaśnić.

64

haskell monads

Author: stites, 2012-09-18

Source

2 answers

s jest tylko hack, który sprawia, że system typu zatrzymać robienie rzeczy, które byłyby niebezpieczne. Nie "robi" nic w czasie wykonywania; po prostu sprawia, że kontroler typu odrzuca programy, które robią wątpliwe rzeczy. (Jest to tak zwany typ phantom , rzecz, która istnieje tylko w głowicy kontrolera typu i nie wpływa na nic w czasie wykonywania.)

25

Author: MathematicalOrchid,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2013-01-26 15:00:26

score 69 · Accepted Answer

s utrzymuje obiekty wewnątrz ST monady przed wyciekiem Na zewnątrz ST monady.

-- This is an error... but let's pretend for a moment...
let a = runST $ newSTRef (15 :: Int)
    b = runST $ writeSTRef a 20
    c = runST $ readSTRef a
in b `seq` c

OK, to jest błąd typu (co jest dobrą rzeczą! nie chcemy przecieku poza oryginalnymi obliczeniami!). Jest to błąd typu z powodu dodatkowego s. Pamiętaj, że runST ma podpis:

runST :: (forall s . ST s a) -> a

Oznacza to, że s przy obliczaniu, które uruchamiasz, nie musi mieć żadnych ograniczeń. Więc kiedy próbujesz ocenić a:

a = runST (newSTRef (15 :: Int) :: forall s. ST s (STRef s Int))

Wynik miałby typ STRef s Int, co jest błędne, ponieważ s "uciekł" poza forall w runST. Zmienne typu zawsze muszą pojawiać się wewnątrz forall, a Haskell pozwala na implicit forall kwantyfikatory wszędzie. Po prostu nie ma reguły, która pozwala na wymowne określenie typu zwracanego a.

Kolejny przykład z forall: aby jasno pokazać, dlaczego nie można pozwolić rzeczy uciec forall, Oto prostszy przykład:

f :: (forall a. [a] -> b) -> Bool -> b
f g flag =
  if flag
  then g "abcd"
  else g [1,2]

> :t f length
f length :: Bool -> Int

> :t f id
-- error --

Oczywiście f id jest błędem, ponieważ zwraca listę Char lub listę Int w zależności od tego, czy wartość logiczna jest true czy false. To jest po prostu złe, tak jak przykład z ST.

Z drugiej strony, jeśli nie posiadasz parametru type s, wszystko sprawdziłoby się poprawnie, nawet jeśli kod jest oczywiście dość fałszywy.

Jak faktycznie działa ST: implementacja, ST monada jest właściwie taki sam jak monada IO, ale z nieco innym interfejsem. Kiedy używasz monady ST, dostajesz unsafePerformIO lub jej odpowiednika, za kulisami. Powodem, dla którego możesz to zrobić bezpiecznie, jest podpis typu wszystkich funkcji związanych z ST, zwłaszcza części z forall.