Документация STArray для новичков и вопросы, связанные с состоянием/ST

ST — это монада, в которой разрешен ограниченный тип побочных эффектов, а именно изменяемые ссылки и изменяемые массивы. Таким образом, он позволяет вам реализовывать функции, которые выглядят чистыми с точки зрения внешнего мира, но которые используют мутацию внутри.

Это отличается от State, который только имитирует мутацию, пропуская состояние через ваши вычисления в качестве дополнительных входов и выходов. Разница важна при реализации некоторых императивных алгоритмов, потому что иногда для их эффективной реализации требуется мутация. Например, используя обычный массив в монаде State, вы можете изменить его, только сделав копию, тогда как с ST вы можете иметь настоящую мутацию на месте.

Причина, по которой у нас есть и ST, и IO, заключается в том, что ST обеспечивает более сильные гарантии, чем IO, а именно:

1. ST не допускает произвольных побочных эффектов, таких как, например, доступ к файловой системе.
2. Мы можем гарантировать, что побочные эффекты, которые ST действительно допускают, не могут выйти за рамки runST, и поэтому их можно рассматривать как чистые от внешнего мира.

Причина, по которой мы можем гарантировать, что побочные эффекты не исчезнут, связана с переменной типа s. Поскольку любое действие ST должно быть полиморфным в s, вы не можете написать код, который позволяет любым изменяемым ссылкам входить или выходить из области действия runST, потому что средство проверки типов будет жаловаться, что не может гарантировать, что s вашего действия и действия ссылки или массив являются одними и теми же, если только они не относятся к одной и той же области runST.

В качестве примера использования монады ST с изменяемыми массивами, вот реализация Решета Эратосфена:

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 — это специализированная форма runST, которая позволяет вам создавать массив, используя мутацию внутри, прежде чем заморозить его и вернуть как неизменяемый массив. newArray, readArray и writeArray делают то, что вы ожидаете.}

Как видите, сигнатура типа sieve указывает на то, что это чистая функция, и так оно и есть. Тем не менее, он активно использует мутацию внутри для эффективной реализации.