Question about ST arrays

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
9 messages Options
Reply | Threaded
Open this post in threaded view
|

Question about ST arrays

Jean-Marc Alliot
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
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: Question about ST arrays

Paul
Hello!

I found this -
https://mail.haskell.org/pipermail/haskell-cafe/2011-May/091622.html

I'm not sure is it helpful.

PS. As I understand, `get2` signature has own `forall s`, but `runST`
is `(forall s. ST s a) -> a` which "escapes" top `s`.

Somebody else? :)

===
Best regards, Paul

> 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
> Only members subscribed via the mailman list are allowed to post.
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: Question about ST arrays

Paul
In reply to this post by Jean-Marc Alliot
Also there is https://en.wikibooks.org/wiki/Haskell/Mutable_objects
May be it will help.

/Regards

> 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
> Only members subscribed via the mailman list are allowed to post.
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: Question about ST arrays

Jean-Marc Alliot
In reply to this post by Paul
Yes, thanks, it's exactly the same question, and the same trick works,
using:
{-# LANGUAGE RankNTypes #-}
and
get2 :: (forall s.ST s (STArray s Int Int)) -> Int -> Int

In fact, Rank-2 types are enough here, we don't need Rank-N types.
I suppose the ST Array module uses the Rank-N extension, so using them
requires also enabling Rank-N.

Thanks again.

Le 29/12/2017 à 16:11, Baa a écrit :

> Hello!
>
> I found this -
> https://mail.haskell.org/pipermail/haskell-cafe/2011-May/091622.html
>
> I'm not sure is it helpful.
>
> PS. As I understand, `get2` signature has own `forall s`, but `runST`
> is `(forall s. ST s a) -> a` which "escapes" top `s`.
>
> Somebody else? :)
>
> ===
> Best regards, Paul
>
>> 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
>> Only members subscribed via the mailman list are allowed to post.
> _______________________________________________
> Haskell-Cafe mailing list
> To (un)subscribe, modify options or view archives go to:
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
> Only members subscribed via the mailman list are allowed to post.


_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: Question about ST arrays

Ramin Honary
In reply to this post by Jean-Marc Alliot
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

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 <[hidden email]> 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
Only members subscribed via the mailman list are allowed to post.


_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: Question about ST arrays

Jean-Marc Alliot
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

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 <[hidden email]> 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
Only members subscribed via the mailman list are allowed to post.



_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: Question about ST arrays

Ramin Honary
(re-sending with "reply to all")

If I understand you correctly, you want to create updates to your hash function throughout execution of your program. If this is the case, based on my own experience, I believe the ST monad was not designed for this purpose and so I think it is probably impossible. You must use the IO monad for a hash table that receives regular updates during program execution.

ST is designed for doing rapid construction of a large immutable data by evaluating many stateful updates to structure during the time before it is made immutable. When monad evaluation terminates, the data structure becomes immutable. Furthermore, you may not use the immutable data structure until the ST evaluation terminates, producing the pure value.

For something like a game, you need to take input then update a hash in an event loop. The IO monad is a good model of this sort of behavior, but the ST monad is not.

Another possibility is that you can use a pure binary tree structure such as Data.Map, if you would prefer to maintain purity, and pass this Map structure around in a State monad transformer. If your State monad transformer is of type (StateT (Map k v) IO a), you can use "liftIO" to take inputs, and the "modify" function to update the Map state after each input.


On Sat, Dec 30, 2017 at 1:05 AM, Jean-Marc Alliot <[hidden email]> wrote:
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

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 <[hidden email]> 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
Only members subscribed via the mailman list are allowed to post.



_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.


_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: Question about ST arrays

Brandon Allbery
In reply to this post by Jean-Marc Alliot
Rank2Types has been an alias for RankNTypes for several years.

In theory, rank-2 types allow some things that aren't possible for general rank-N types (e.g. decidable typechecking). In practice, ghc does not and probably never will implement those as special cases for rank-2 types, so it no longer distinguishes them.

On Fri, Dec 29, 2017 at 10:31 AM, Jean-Marc Alliot <[hidden email]> wrote:
Yes, thanks, it's exactly the same question, and the same trick works, using:
{-# LANGUAGE RankNTypes #-}
and
get2 :: (forall s.ST s (STArray s Int Int)) -> Int -> Int

In fact, Rank-2 types are enough here, we don't need Rank-N types.
I suppose the ST Array module uses the Rank-N extension, so using them requires also enabling Rank-N.

Thanks again.


Le 29/12/2017 à 16:11, Baa a écrit :
Hello!

I found this -
https://mail.haskell.org/pipermail/haskell-cafe/2011-May/091622.html

I'm not sure is it helpful.

PS. As I understand, `get2` signature has own `forall s`, but `runST`
is `(forall s. ST s a) -> a` which "escapes" top `s`.

Somebody else? :)

===
Best regards, Paul

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
Only members subscribed via the mailman list are allowed to post.
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.


_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.



--
brandon s allbery kf8nh                               sine nomine associates
[hidden email]                                  [hidden email]
unix, openafs, kerberos, infrastructure, xmonad        http://sinenomine.net

_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: Question about ST arrays

Will Yager
In reply to this post by Jean-Marc Alliot


> On Dec 29, 2017, at 11:05 AM, Jean-Marc Alliot <[hidden email]> 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


_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.