[Haskell-cafe] Question about ST arrays
Jean-Marc Alliot
jm at alliot.org
Fri Dec 29 16:05:44 UTC 2017
Well I am going to try to explain why I want to use STArrays and the
runST function (and I am absolutely ready to be proven wrong, and
directed to a better way to do it).
I have, as a simple way to learn the language, implemented an Awele
program in Haskell (I have been programming games for years). It was
easy, elegant (around 70 lines, 150 with the graphical interface) and
completely functional, but I soon stumbled upon one problem. While
implementing a vanilla alpha-beta is easy in functional style,
implementing hash-tables (I mean hash-tables of the kind we use in game
programming, not exactly regular hash-tables) is not that easy, and hash
tables are mandatory to have a fast alpha-beta.
Currently, my idea is to create a module which will hide the
implementation, and have only two functions in its interface:
1) A test_and_retrieve which take as only parameter a position and
return a Maybe object which contains Nothing if the position has never
been evaluated or (Just v) if there is already an evaluation for it (I
know that I need more information than just a value, but for the sake of
simplicity let's stick with just a value)
2) A store function which will take a position and its evaluation and
store it in the table.
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.
Le 29/12/2017 à 16:36, Ramin Honary a écrit :
> You should use "runSTArray" or "runSTUArray" instead of "runST" to
> convert your STArray to an immutable array:
> https://hackage.haskell.org/package/array-0.5.2.0/docs/Data-Array-ST.html#v:runSTUArray
> <https://hackage.haskell.org/package/array-0.5.2.0/docs/Data-Array-ST.html#v:runSTUArray>
>
> Or another option is to use "stToIO" to convert the "STArray" to an
> "IOArray."
> https://hackage.haskell.org/package/base-4.10.1.0/docs/Control-Monad-ST-Lazy.html#v:stToIO
> but if you want to build an IOArray, it is better to just start with
> an IOArray rather than converting an STArray to an IOArray.
>
> The design of ST arrays is to allow you to construct them quickly and
> then make them immutable once you are done constructing it.
>
> An immutable array must have the whole array copied after every single
> update, but ST arrays allow you to make many updates without copying,
> then when you have completed constructing the ST array, you must
> freeze it to an immutable array using the "runSTUArray" function.
> Freezing happens without copying the array, after that it is immutable
> and may not be made into an STArray again unless you unfreeze it using
> "thaw", which creates a copy of it:
> https://hackage.haskell.org/package/array-0.5.2.0/docs/Data-Array-MArray.html#v:thaw
>
>
> Once you have constructed your immutable array, you can access it
> arbitrarily using the immutable operator (!).
>
> If you want to make multiple updates at multiple times, you must use
> an IOArray or IOUArray. The ST monad is designed for you to construct
> pure, referentially transparent, immutable values in an isolated and
> strictly evaluated "environment" that lets you perform strict updates
> during construction. Once evaluation of the "ST" monad is complete,
> the returned value becomes pure, immutable, and referentially
> transparent. The for-all'd "s" parameter of the "runST" function
> ensures you do not mix separate "environments," and this is the reason
> you got your type error. Using "runSTArray" or "runSTUArray" does not
> have this restriction.
>
> I am not sure of the reason for this design decision, but I know it
> has something to do with the compiler guaranteeing that pure immutable
> referentially transparent types are constructed without effecting each
> other, preventing race conditions. There is discussion of this on the
> Haskell wiki:
> https://wiki.haskell.org/Monad/ST#An_explanation_in_Haskell-Cafe
>
>
> On Fri, Dec 29, 2017 at 11:36 PM, Jean-Marc Alliot <jm at alliot.org
> <mailto:jm at alliot.org>> wrote:
>
> Hi,
>
> This is my first post to this list so I apologize in advance if I
> don't use it properly, or if my question is too simple or
> inapropriate.
>
> I come from the Caml world and I am quite new to Haskell (but not
> to functional programming). I am currently trying to get the hang
> of Haskell arrays. I have gone through regular arrays, IO Arrays
> and I am now working with ST Arrays.
>
> This is the problem I am currently stuck with. I write the
> following code:
>
> arr = newArray (-1, 1) 0 :: ST s (STArray s Int Int)
> get :: Int -> Int
> get i = runST (arr >>= (\b -> readArray b i))
>
> Here everything is perfectly OK.
>
> Now I want a more general version that could deal with any array
> like arr. So I write:
>
> get2 :: ST s (STArray s Int Int) -> Int -> Int
> get2 tab i = runST (tab >>= (\b -> readArray b i))
>
> And the compiler is clearly very upset by my code:
>
> Couldn't match type ‘s’ with ‘s1’
> ‘s’ is a rigid type variable bound by
> the type signature for:
> get2 :: forall s. ST s (STArray s Int Int) -> Int -> Int
> at testst.hs:17:9
> ‘s1’ is a rigid type variable bound by
> a type expected by the context:
> forall s1. ST s1 Int
> at testst.hs:18:14
> Expected type: ST s1 Int
> Actual type: ST s Int
> I am pretty sure that the compiler is right and I am wrong, but I
> don't get why... Anyone could help?
>
> Thanks
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> To (un)subscribe, modify options or view archives go to:
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
> <http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe>
> Only members subscribed via the mailman list are allowed to post.
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20171229/9730e7ef/attachment.html>
More information about the Haskell-Cafe
mailing list