Документация STArray для новичков и вопросы штата / ST - PullRequest
Новая
       41

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

39 голосов
/ 20 ноября 2011

Мне трудно понять STArray из документации и других статей / обсуждений, которые я нашел через Google.У меня есть еще несколько связанных вопросов ниже.

Согласно документации, STArray s

Изменяемые в штучной упаковке и распакованные массивы в монаде ST.

Это создало у меня впечатление, что STArray предназначено для использования в качестве состояния , передаваемого между функциями (представьте, что у вас есть вектор, который нужно часто обновлять).

Очевидно, что это используется по-другому, хотя: 

ST s (STArray s a e)

Каково состояние s здесь?Если он используется внутри, то почему он не скрыт от пользователя?

Это также означает, что если мы хотим использовать STArray s Int Int, передаваемый как состояние, можно определить 

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

что кажется довольно громоздким.

Наконец,

  • в чем разница между ST и State?
  • в чем разница между STArray и IOArray, если ST и IO предназначены для «внутреннего» использования?

Спасибо !!

1 Ответ

72 голосов
/ 20 ноября 2011

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 указывает, что это чистая функция, и это так.Тем не менее, он использует мутацию внутри для эффективной реализации.

...