Haskell: карта runST

Каждый раз, когда вы запускаете преобразователь состояния с помощью runST, он работает с некоторым локальным состоянием, которое отделено от всех других преобразователей состояния. runST создает новый тип состояния и вызывает свой аргумент с этим типом. Так, например, если вы выполните

let x = runST (return ())
    y = runST (return ())
in (x, y)

тогда первый return () и второй return () будут иметь разные типы: ST s1 () и ST s2 (), для некоторых неизвестных типов s1 и s2 которые созданы runST.

Вы пытаетесь вызвать runST с аргументом, который имеет тип состояния s. Это не тот тип состояния, который создает runST, и не любой другой тип, который вы можете выбрать. Чтобы вызвать runST, вы должны передать аргумент, который может иметь любой тип состояния. Вот пример:

r1 :: forall s. ST s ()
r1 = return ()

Поскольку r1 является полиморфным, его состояние может иметь любой тип, включая любой тип, выбранный runST. Вы можете сопоставить runST со списком полиморфных r1 (с -XImpredicativeTypes):

map runST ([r1, r1] :: [forall t. ST t ()])

Однако вы не можете сопоставить runST со списком неполиморфных r1.

map runST ([r1, r1] :: forall t. [ST t ()]) -- Not polymorphic enough

Тип forall t. [ST t ()] говорит о том, что все элементы списка имеют тип состояния t. Но все они должны иметь независимые типы состояний, потому что для каждого из них вызывается runST. Вот что означает сообщение об ошибке.

Если можно присвоить одинаковое состояние всем элементам списка, вы можете вызвать runST один раз, как показано ниже. Явная подпись типа не требуется.

runST (sequence ([r1, r1] :: forall t. [ST t ()]))

Ваш name недостаточно полиморфен. Ваше заявление

name :: [ST s (Int, [Int])]

означает «список возвращаемых вычислений с отслеживанием состояния (Int, [Int]), которые имеют точно такие же s». Но посмотрите на тип runST:

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

Этот тип означает «функцию, которая выполняет вычисление с отслеживанием состояния, где s может быть все, что вы можете себе представить». Эти типы вычислений не одно и то же. И наконец:

map runST :: [forall s. ST s a] -> [a]

Видите ли, ваш список должен содержать больше полиморфных значений, чем сейчас. Тип s может быть разным в каждом элементе списка, он может не совпадать с типом name. Измените подпись типа name, и все должно быть в порядке. Для этого может потребоваться включить некоторые расширения, но GHC сможет сказать вам, какие из них.

Я попытаюсь объяснить причины для типа runST:

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

И почему это не похоже на этот простой:

alternativeRunST :: ST s a -> a

Обратите внимание, что это alternativeRunST сработало бы для вашей программы.

alternativeRunST также позволил бы нам выводить переменные из монады ST:

leakyVar :: STRef s Int
leakyVar = alternativeRunST (newSTRef 0)

evilFunction :: Int -> Int
evilFunction x =
  alternativeRunST $ do
    val <- readSTRef leakyVar
    writeSTRef leakyVar (val+1)
    return (val + x)

Затем вы можете пойти в ghci и сделать:

>>> map evilFunction [7,7,7]
[7,8,9]

evilFunction не является ссылочно прозрачным!

Кстати, чтобы попробовать это самостоятельно, вот "плохая" среда ST, необходимая для запуска кода выше:

{-# LANGUAGE GeneralizedNewtypeDeriving #-}
import Control.Monad
import Data.IORef
import System.IO.Unsafe
newtype ST s a = ST { unST :: IO a } deriving Monad
newtype STRef s a = STRef { unSTRef :: IORef a }
alternativeRunST :: ST s a -> a
alternativeRunST = unsafePerformIO . unST
newSTRef :: a -> ST s (STRef s a)
newSTRef = ST . liftM STRef . newIORef
readSTRef :: STRef s a -> ST s a
readSTRef = ST . readIORef . unSTRef
writeSTRef :: STRef s a -> a -> ST s ()
writeSTRef ref = ST . writeIORef (unSTRef ref)

Настоящий runST не позволяет нам создавать такие "злые" функции. Как это делается? Это довольно сложно, см. ниже:

Пытаюсь запустить:

>>> runST (newSTRef "Hi")
error:
    Couldn't match type `a' with `STRef s [Char]'
...

>>> :t runST
runST :: (forall s. ST s a) -> a
>>> :t newSTRef "Hi"
newSTRef "Hi" :: ST s (STRef s [Char])

newSTRef "Hi" не подходит (forall s. ST s a). Как можно увидеть и на еще более простом примере, где GHC выдает довольно симпатичную ошибку:

dontEvenRunST :: (forall s. ST s a) -> Int
dontEvenRunST = const 0

>>> dontEvenRunST (newSTRef "Hi")
<interactive>:14:1:
    Couldn't match type `a0' with `STRef s [Char]'
      because type variable `s' would escape its scope

Обратите внимание, что мы также можем написать

dontEvenRunST :: forall a. (forall s. ST s a) -> Int

И это эквивалентно пропуску forall a., как мы делали раньше.

Обратите внимание, что область действия a больше, чем у s, но в случае newSTRef "Hi" его значение должно зависеть от s. Система типов этого не позволяет.