[Haskell-cafe] Question about ST arrays

[Will Yager]

> On Dec 29, 2017, at 11:05 AM, Jean-Marc Alliot <jm at alliot.org> wrote:
> 
> 
> 
> Now if I use IO Arrays, I will have to live in the IO Monad if I understand correctly how the IO Monad works, while using ST Arrays seems to give me the possibility to hide all the non functional code in my hash module, and keep my main code almost purely functional.

Just as IO arrays require you to live in the IO monad anywhere you want to read/write a mutable IO array, ST arrays require you to live in the ST monad anywhere you want to read/write an ST array. 

Your earlier code of the form

(forall s . ST s (Array Int Int)) -> Int -> Int

Actually runs the ST action which creates the mutable array every time you call the function. So you’re not sharing the same mutable array; you’re creating it from scratch every time. This is probably not what you intend. 

The ST monad is good for when you really need the speed boost of a locally mutable operation in an otherwise immutable program. It is not good for keeping track of a mutable state, which is what you are doing with the hash table. 

What you probably want is the State monad. It takes functions of the form

state -> (state, result)

And provides convenient syntax and abstractions for combining these functions. In this case, the state would be your hash table. So the function that checks for an existing solution would have type

Hashtbl -> (Hashtbl, Maybe Soln)

AKA

State Hashtbl (Maybe Soln)

And the function that writes a new solution would have type 

Soln -> Hashtbl -> (Hashtbl, ())

AKA

Soln -> State Hashtbl ()

Compare these types to those of the functions for reading and writing ST arrays. 

The downside of State is that its state type must be an immutable structure, which will have some overhead compared to a mutable array. However, structures such as the Hashmap are pretty fast even though they’re immutable. 

-Will