Jak mogę zebrać listę działań ST wewnątrz?

Question

Jak mogę przekonwertować numer [Either ST] na Either [ST], a następnie kolejno wykonywać akcje? Wydaje się, że poniższy kod działa przy uruchamianiu listy działań ST, jednak podczas próby wygenerowania listy działań w Either (zamiana definicji test) typy nie są już zgodne. Spodziewałbym się, że rodzaje list będą identyczne, więc bardzo doceniam każde wyjaśnienie różnic.

{-# LANGUAGE RankNTypes #-} 

import qualified Data.STRef as ST 
import qualified Control.Monad.ST as ST 

run :: (forall s. [ST.STRef s Int -> ST.ST s Int]) -> Int 
run fs = 
    ST.runST $ do 
    x <- ST.newSTRef 0 
    mapM_ (\f -> 
     f x >>= ST.writeSTRef x 
    ) fs 
    ST.readSTRef x 

action :: ST.STRef s Int -> ST.ST s Int 
action = \x -> ST.readSTRef x >>= \y -> return (y + 1) 

-- test :: Either String Int 
-- test = mapM (const (return action)) [0..5] >>= \fs -> return (run fs) 

test :: Int 
test = run (map (const action) [0..5]) 

main = print test 

Answer 1

Wnioskowanie typu w przypadku typów wyższego rzędu jest nierozstrzygalne. Algorytm wnioskowania typu GHC tworzy pewne uproszczone założenia, które powodują, że jest on niepełny. Należą do nich:

• GHC przyjmie zmienna związana lambda jest monotypia (? Nie zawiera (prowadząca) forall s)

• Podczas korzystania polimorficzny funkcji GHC zakłada, że wolne zmienne typu w swoim rodzaju będzie instancja w monotypie

Oba te założenia mogą być nadpisane jeśli zapytać gHC grzecznie do korzystania z konkretnego polytype zamiast.

Teraz, jak można się spodziewać, że program będzie sprawdzać?

• Aby run fs na typ kontroli, mieliśmy lepiej mieć fs :: forall s. [ST.STRef s Int -> ST.ST s Int]
• Tak więc, zgodnie z pierwszym punktem powyżej musimy napisać ten podpis typu na lambda, która wiąże go: \(fs :: forall s. [ST.STRef s Int -> ST.ST s Int]) -> ... (używając ScopedTypeVariables)

• Teraz rozważ użycie >>=. Jego typ to Monad m => m a -> (a -> m b) -> m b. Ale potrzebujemy a = forall s. [ST.STRef s Int -> ST.ST s Int]. Tak więc, według drugiego punktu powyżej musimy dać ten >>= podpis typu, jak w

  ... `op` (\(fs :: forall s. [ST.STRef s Int -> ST.ST s Int]) -> ...) 
      where op :: Monad m 
        => m (forall s. [ST.STRef s Int -> ST.ST s Int]) 
        -> ((forall s. [ST.STRef s Int -> ST.ST s Int]) -> m b) 
        -> m b 
        op = (>>=) 
  

• Teraz napotkasz nowego rodzaju problemu. W tej aplikacji op pierwszy argument ma typ Either String (forall s. [ST.STRef s Int -> ST.ST s Int]). Stosowanie konstruktora typu (innego niż (->)) do typu poliseksu jest niedozwolone, chyba że włączysz (zepsute) ImpredicativeTypes. Jednak możemy go włączyć i kontynuować ...
• Zaniżając pierwszy argument, widzimy, że będziemy potrzebować return :: Monad m => a -> m a z instancją a = forall s. ST.STRef s Int -> ST.ST s Int. Tak więc, musimy dodać kolejny podpis typu do return
• Podobnie musimy mapM :: Monad m => (a -> m b) -> [a] -> m [b] instancja w b = forall s. ST.STRef s Int -> ST.ST s Int

• Jeśli uważnie można zauważyć jeszcze jeden problem: wynik mapM ma typ

  Either String [forall s. ST.STRef s Int -> ST.ST s Int] 
  

  ale argument (>>=) musi być typu

  Either String (forall s. [ST.STRef s Int -> ST.ST s Int]) 
  

  i będzie musiał przekonwertować między nimi.W rzeczywistości jest to nie-op, ale GHC nie jest wystarczająco silny, aby to wiedzieć, więc trzeba będzie zrobić konwersję liniowy w czasie, coś

  liftM (\x -> map (\(y :: forall s. ST.STRef s Int -> ST.ST s Int) -> y) x) 
  

  (z wyjątkiem liftM będą musiały kolejny podpis typ)

Morał z opowieści: Możesz to zrobić, ale nie powinieneś.

Będziesz generalnie mają łatwiej, jeśli ukryć forall s wewnątrz newtypes jak

newtype S s = S { unS :: forall s. ST.STRef s Int -> ST.ST s Int } 

co sprawia, że ​​punkty, w których polimorfizm jest wprowadzone bardziej wyraźne w programie (poprzez wystąpień S i unS).

Answer 2

Musisz zawinąć funkcje w newtype, aby zachować egzystencjalne oznaczenie ilościowe bez konieczności używania ImpredicativeTypes.

{-# LANGUAGE RankNTypes #-} 

import qualified Data.STRef as ST 
import qualified Control.Monad.ST as ST 

newtype STFunc = STFunc (forall s. ST.STRef s Int -> ST.ST s Int) 

run :: [STFunc] -> Int 
run fs = ST.runST $ do 
    x <- ST.newSTRef 0 
    mapM_ (\(STFunc f) -> 
     f x >>= ST.writeSTRef x 
    ) fs 
    ST.readSTRef x 

action :: STFunc 
action = STFunc $ \x -> ST.readSTRef x >>= \y -> return (y + 1) 

test :: Either String Int 
test = mapM (const (return action)) [0..5] >>= \fs -> return (run fs) 

main = print test