Federico Squartini writes: > Hello dear Haskellers, > > Could someone be kind and explain with some detail what are the > differences between the two monads: > > Control.Monad.ST > And > Control.Monad.State > ? > > They are both meant to model stateful computation but they are not the > same monad. The first one represents state with in place update?
Conceptually, the difference is in the API. State can be thought of as an ST with a single, implicit reference cell. Alternately, ST can be thought of as a State which manipulates a store of values. Here's a simple implementation of State using ST: newtype State s a = State { unState :: forall r. ReaderT (STRef r s) (ST r) a } runState :: State s a -> s -> (a,s) runState m s0 = runST (do r <- newSTRef s0 a <- runReaderT (unState m) r s <- readSTRef r return (a,s)) instance Monad (State s) where return a = State (return a) m >>= f = State (unState m >>= unState . f) instance MonadState s (State s) where get = State (ask >>= lift . readSTRef) put x = State (ask >>= \s -> lift (writeSTRef s x)) It's also possible to write ST in terms of State. Assume we have a Store ADT with this interface: data Store r data STRef r a withStore :: (forall r. Store r -> a) -> a newRef :: a -> Store r -> (STRef r a, Store r) readRef :: STRef r a -> Store r -> a writeRef :: STRef r a -> a -> Store r -> Store r (The 'r' parameter is to make sure that references are only used with the Store that created them. The signature of withStore effectively gives every Store a unique value for r.) Then we can define ST like so: newtype ST r a = ST { unST :: State (Store r) a } deriving Monad runST :: (forall r. ST r a) -> a runST m = withStore (evalState (unST m)) newSTRef :: a -> ST r (STRef r a) newSTRef a = ST $ do s <- get let (r,s') = newRef a s put s' return r readSTRef :: STRef r a -> ST r a readSTRef r = ST $ gets (readRef r) writeSTRef :: STRef r a -> a -> ST r () writeSTRef r a = ST $ modify (writeRef r a) There are two subtleties. The first is that you can't implement Store without cheating at some level (e.g., unsafeCoerce). The second is that the real ST implementation uses in-place update, which is only safe because the Store is implicit and used single-threadedly. -- David Menendez <[EMAIL PROTECTED]> | "In this house, we obey the laws <http://www.eyrie.org/~zednenem> | of thermodynamics!" _______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell