Mónada ST en Haskell: STRef, STArray

Haskell tiene una librería muy completa, con muchas estructuras de datos y, en este caso, mónadas muy interesantes. En este caso vamos a hablar de la mónada ST. ST son las siglas de State Threads. Fueron definidas por Simon Peyton-Jones en un paper de 1994 y son una forma muy curiosa que tiene Haskell de permitirnos escribir código con estructuras de datos mutables. La gracia está en que se garantiza que es imposible que la mutabilidad interna que hay dentro de la mónada ST salga al exterior, de modo que de cara al exterior son funciones puras igualmente. Esta mónada no sirve para comunicarse con el exterior como sí sirve IO pero si podemos usar ST antes que IO, mejor.

STRef

La estructura más fundamental es STRef, que permite tener una variable mutable dentro de Haskell. Las funciones que permiten su manejo son newSTRef, readSTRef, writeSTRef y modifySTRef. Creo que es bastante evidente para qué sirve cada una, pero veamos un ejemplo práctico.

Vamos a hacer una función que sume todos los elementos de una lista. Existen varias formas de hacerlo de forma pura en Haskell:

sumar :: Num a => [a] -> a
sumar [] = 0
sumar (x:xs) = x+sumar xs

Una versión recursiva

sumar :: Num a => [a] -> a
sumar = foldr1 (+)

Una versión más compacta

En un lenguaje de programación imperativo sin embargo posiblemente haríamos algo parecido a esto:

int sumar(int[] nums){
    int suma = 0;
    for(int i=0;i<nums.length;i++){
        suma += nums[i];
    }
    return suma;
}

Con ST podemos hacer código que se parezca a la versión imperativa, lo cuál es útil en determinados algoritmos y también si queremos ganar eficiencia.

import Control.Monad.ST
import Control.Monad
import Data.STRef

sumar :: Num a => [a] -> a
sumar xs = runST $ do
	x <- newSTRef 0
	
	forM_ xs $ \n -> 
		modifySTRef x $ \x -> x+n

	readSTRef x

Lo primero que tenemos que hacemos es ejecutar la mónada ST con runST y a continuación la función. Allí creamos una variable mutable con valor inicial 0. Después lanzamos forM_ que itera sobre cada elemento de la lista xs ejecutando para cada elemento la función que llama a modifySTRef que ejecuta a su vez la función que suma el valor del acumulador con el valor del elemento actual de la lista.

Por último, la función finaliza devolviendo el valor de x.

Como veis, el código no tiene nada que ver a las otras versiones de Haskell y tiene un gran parecido con la versión de Java. No obstante, el código sigue siendo puro, sin efectos colaterales.

STArray

Pero no solo tenemos STRef, también tenemos STArray que es un array de tamaño fijo con estas mismas propiedades. Las funciones básicas son newListArray, readArray, writeArray y getElems.

Por ejemplo, podemos implementar el algoritmo de Bubble Sort de forma imperativa con STArray:

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

bubblesort :: [Int] -> [Int]
bubblesort xs = runST $ do
	let l = length xs
	temp <- newSTRef $ head xs
	array <- ST.newListArray (0,l-1) xs :: ST s (ST.STArray s Int Int)

	forM_ [0..l] $ \i -> do
		forM_ [1..(l-1)] $ \j -> do
			prev <- ST.readArray array (j-1)
			actual <- ST.readArray array j	
			if prev > actual then do
				writeSTRef temp prev
				ST.writeArray array (j-1) actual
				t <- readSTRef temp
				ST.writeArray array j t
			else do
				return ()

	ST.getElems array
			
main :: IO ()
main = do
	let orden = bubblesort [3,4,1,2]			
	putStrLn ("Orden: "++(show orden))

La mónada ST junto con las funciones de Control.Monad nos permiten escribir código que parece imperativo y con mutabilidad, sin perder la pureza y la seguridad de Haskell.