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:

Una versión recursiva

Una versión más compacta

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

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.

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:

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.

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *