ST est une monade dans laquelle un type limité d'effets secondaires est autorisé, à savoir les références mutables et les tableaux mutables. Elle vous permet donc d'implémenter des fonctions qui sont pures vues de l'extérieur, mais qui utilisent la mutation en interne.
Ceci est différent de State qui ne fait que simuler une mutation en faisant passer l'état dans votre calcul sous forme d'entrées et de sorties supplémentaires. La différence est importante lors de la mise en œuvre de certains algorithmes impératifs, car ils nécessitent parfois une mutation pour être mis en œuvre efficacement. Par exemple, l'utilisation d'un tableau régulier dans un State vous ne pouvez le modifier qu'en faisant une copie, alors qu'avec la monade ST vous pouvez avoir une véritable mutation en place.
La raison pour laquelle nous avons à la fois ST y IO c'est que ST offre des garanties plus solides que IO à savoir :
-
ST ne permet pas d'effets secondaires arbitraires comme, par exemple, l'accès au système de fichiers.
- Nous pouvons garantir que les effets secondaires
ST fait ne peut pas échapper à la portée de runST et il peut donc être considéré comme pur par rapport au monde extérieur.
La raison pour laquelle nous pouvons garantir que les effets secondaires ne peuvent pas s'échapper est liée à la variable de type s . Puisque toute action ST doit être polymorphe en s vous ne pouvez pas écrire de code qui permette à des références mutables d'entrer ou de sortir du champ d'application d'un fichier de type runST car le vérificateur de type se plaindra qu'il ne peut pas garantir que l'option s de votre action et celle de la référence ou du tableau sont les mêmes sauf si ils viennent du même runST l'étendue.
À titre d'exemple d'utilisation du ST avec des tableaux mutables, voici une implémentation du tamis d'Erathostenes :
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
<code>runSTUArray</code> est une forme spécialisée de <code>runST</code> qui vous permet de construire un tableau en utilisant la mutation à l'intérieur, avant de le geler et de le retourner sous forme de tableau immuable. <code>newArray</code> , <code>readArray</code> y <code>writeArray</code> font ce que l'on attend d'eux.
Comme vous pouvez le voir, la signature de type de sieve indique qu'il s'agit d'une fonction pure, et c'est le cas. Cependant, elle utilise fortement la mutation à l'intérieur pour l'implémenter efficacement.
