On Thu, Aug 04, 2005 at 10:40:01PM +0200, Till Mossakowski wrote: > Remi Turk wrote: > >MonadState needs multi-parameter type classes, State and StateT > >don't. And ST needs rank-2 types (or at least one rank-2 > >constant) and, to be implemented _efficiently_, also needs > >something like unsafePerformIO (or even lower-level unsafe > >mutable state primitives). > > >I think one could call the ST monad a safe yet still efficient > >variant of unsafePerformIO + IORef's + IOArray's. > > No, the point of ST is that it is safe (as opposed to unsafePerformIO), > but still has the advantages of being both efficient and allowing > purely functional encapsulation via runST (as oppesed to IORefs > and IOArrays). The only price is that you need rank-2 polymorphism > and new language primitives for creating, reading and writing > references. But using these primitives is much better than using > unsafePerformIO - the latter entails a lot of harmful things.
As I agree with everything after the "No" I guess there is a new
misunderstanding in the world :) I'll try to clarify what I
meant:
Occasionally, one would like to write a piece of code which
performs updates in place. As an example I'll use a function
hist :: [Char] -> [(Char, Int)]
which returns a histogram of (lowercase) letters. The most
efficient (and to many also most obvious) way to implement this
function is using an mutable array of letters to occurrence
counts.
One way to implement "hist" is then something like:
hist str = unsafePerformIO (do
arr <- newArray ...
mapM_ (\x -> ...) str
getAssocs arr
)
which is safe, as it does not have observable side-effects and
always yields the same value for a given argument.
Still, the proof obligation that it actually is safe lies with
the programmer, each time he implements something like "hist".
In general, if some IO-action "foo" is pure except for its use of
IORef's and IOArray's, and it only uses ones it created itself,
and doesn't return any of them, it _cannot_ have observable
side-effects and will always yield the same value and hence
"unsafePerformIO foo" _will always be safe_.
This can be abstracted into a "design pattern" ;), called "the ST
monad", thus only requiring the programmer to give a "this use of
unsafePerformIO is safe"-proof once for runST, instead of each
time he implements a "hist"-like function. (See attached modules.)
Hm, I'm not sure whether this can meaningfully be called a
"clarification". Oh well :)
In a final attempt to convince someone of I'm not exactly sure
what, I attached a simple implementation of the ST monad in terms
of unsafePerformIO + IORef + IOArray.
And as a really-I-mean-it final remark,
> >I think one could call the ST monad a safe yet still efficient
> >variant of unsafePerformIO + IORef's + IOArray's.
, could probably be phrased better as the "ST monad can be seen
as a safe subset of the functionality of unsafePerformIO +
IORef + IOArray."
Cheers,
Remi
--
Nobody can be exactly like me. Even I have trouble doing it.
{-# OPTIONS_GHC -fglasgow-exts #-}
module MyST (ST, runST
,STRef, newSTRef, readSTRef, writeSTRef
,STArray
,module Data.Array.MArray
) where
import Monad
import Data.IORef
import Data.Array.Base (unsafeRead, unsafeWrite)
import Data.Array.MArray
import Data.Array.IO (IOArray)
import System.IO.Unsafe (unsafePerformIO)
--- ST ---
newtype ST s a = ST {unST :: IO a}
runST :: (forall s. ST s a) -> a
runST = unsafePerformIO . unST
instance Monad (ST s) where
return = ST . return
ST a >>= f = ST (a >>= unST . f)
--- STRef ---
newtype STRef s a = STRef {unSTRef :: IORef a}
newSTRef :: a -> ST s (STRef s a)
newSTRef = ST . liftM STRef . newIORef
readSTRef :: STRef s a -> ST s a
readSTRef = ST . readIORef . unSTRef
writeSTRef :: STRef s a -> a -> ST s ()
writeSTRef r = ST . writeIORef (unSTRef r)
--- STArray ---
newtype STArray s i e = STArray {unSTArray :: IOArray i e}
instance HasBounds (STArray s) where
bounds = bounds . unSTArray
instance MArray (STArray s) e (ST s) where
newArray b = ST . liftM STArray . newArray b
unsafeRead a = ST . unsafeRead (unSTArray a)
unsafeWrite a i = ST . unsafeWrite (unSTArray a) i
module Foo where
import Monad
import System.IO.Unsafe (unsafePerformIO)
import Data.Array.MArray
import Data.Array.IO
import MyST
hist f xs = do
arr <- f $ newArray ('a','z') 0
flip mapM_ xs $ \x -> do
n <- readArray arr x
writeArray arr x (n+1)
filter ((/=0) . snd) `liftM` getAssocs arr
idSTArray :: ST s (STArray s i e) -> ST s (STArray s i e)
idSTArray = id
idIOArray :: IO (IOArray i e) -> IO (IOArray i e)
idIOArray = id
histST, histIO :: [Char] -> [(Char, Int)]
histST xs = runST (hist idSTArray xs)
histIO xs = unsafePerformIO (hist idIOArray xs)
pgpTLIudH9wsD.pgp
Description: PGP signature
_______________________________________________ Haskell mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell
