Monad/ST
From HaskellWiki
BrettGiles (Talk | contribs) (Adding standard class template) |
(explanation by Stefan O'Rear) |
||
Line 17: | Line 17: | ||
* DapperDan2: it strikes me that ST is like a lexical scope, where all the variables/state disappear when the function returns. |
* DapperDan2: it strikes me that ST is like a lexical scope, where all the variables/state disappear when the function returns. |
||
[[Category:Standard classes]] [[Category:Monad]] |
[[Category:Standard classes]] [[Category:Monad]] |
||
+ | |||
+ | |||
+ | ==An explanation in Haskell-Cafe== |
||
+ | |||
+ | The ST monad lets you use update-in-place, but is escapable (unlike IO). |
||
+ | ST actions have the form: |
||
+ | |||
+ | <haskell> |
||
+ | ST s α |
||
+ | </haskell> |
||
+ | |||
+ | Meaning that they return a value of type α, and execute in "thread" s. |
||
+ | All reference types are tagged with the thread, so that actions can only |
||
+ | affect references in their own "thread". |
||
+ | |||
+ | Now, the type of the function used to escape ST is: |
||
+ | |||
+ | <haskell> |
||
+ | runST :: forall α. (forall s. ST s α) -> α |
||
+ | </haskell> |
||
+ | |||
+ | The action you pass must be universal in s, so inside your action you |
||
+ | don't know what thread, thus you cannot access any other threads, thus |
||
+ | <hask>runST</hask> is pure. This is very useful, since it allows you to implement |
||
+ | externally pure things like in-place quicksort, and present them as pure |
||
+ | functions ∀ e. Ord e ⇒ Array e → Array e; without using any unsafe |
||
+ | functions. |
||
+ | |||
+ | But that type of <hask>runST</hask> is illegal in Haskell-98, because it needs a |
||
+ | universal quantifier *inside* the function-arrow! In the jargon, that |
||
+ | type has rank 2; haskell 98 types may have rank at most 1. |
||
+ | |||
+ | See http://www.haskell.org/pipermail/haskell-cafe/2007-July/028233.html |
Revision as of 07:27, 12 July 2007
import Control.Monad.ST |
The ST monad provides support for strict state threads.
1 A discussion on the Haskell irc
From #haskell (see 13:05:37 in the log ):
- TuringTest: ST lets you implement algorithms that are much more efficient with mutable memory used internally. But the whole "thread" of computation cannot exchange mutable state with the outside world, it can only exchange immutable state.
- TuringTest: chessguy: You pass in normal Haskell values and then use ST to allocate mutable memory, then you initialize and play with it, then you put it away and return a normal Haskell value.
- sjanssen: a monad that has mutable references and arrays, but has a "run" function that is referentially transparent
- emu: in-place qsort within ST monad: http://hpaste.org/274
- DapperDan2: it strikes me that ST is like a lexical scope, where all the variables/state disappear when the function returns.
2 An explanation in Haskell-Cafe
The ST monad lets you use update-in-place, but is escapable (unlike IO). ST actions have the form:
ST s α
Meaning that they return a value of type α, and execute in "thread" s. All reference types are tagged with the thread, so that actions can only affect references in their own "thread".
Now, the type of the function used to escape ST is:
runST :: forall α. (forall s. ST s α) -> α
The action you pass must be universal in s, so inside your action you don't know what thread, thus you cannot access any other threads, thus
externally pure things like in-place quicksort, and present them as pure functions ∀ e. Ord e ⇒ Array e → Array e; without using any unsafe functions.
But that type ofuniversal quantifier *inside* the function-arrow! In the jargon, that type has rank 2; haskell 98 types may have rank at most 1.
See http://www.haskell.org/pipermail/haskell-cafe/2007-July/028233.html