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? Regards, Federico
federico.squartini:
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?
Very very different. The former is for filling memory blocks in a pure manner, the latter models threaded state. -- Don
But they are very similar! At least superficially. They are both based on the notion of state transformer. Moreover in the original paper about the ST monad: http://www.dcs.gla.ac.uk/fp/papers/lazy-functional-state-threads.ps.Z The authors say: "In this paper we describe a way to express stateful algorithms in non-strict, purely functional languages". And almost everywhere in the paper looks as if they are talking about a normal State monad. I suppose there is something "under the hood" which makes them different, but I cannot figure out what. Federico
Very very different.
-- Don
Hi Frederico, I had the exact same problem when I first started with Haskell. Quite simply, State uses get/put to handle passing state, whereas ST uses STRefs and STArrays. In State s a, the s has meaning, for example it could be a random number generator or key-value mapping you want to pass around. However in ST s a, the s only exists in the type. The actual state is stored in references and arrays. Perhaps someone more knowledgeable should add something to the Haddock comments; I think this confuses a lot of people at first. Joel
On May 30, 2007, at 5:59 , Federico Squartini wrote:
I suppose there is something "under the hood" which makes them different, but I cannot figure out what.
For one thing, ST uses existential types to prevent values from leaking outside the monad. -- brandon s. allbery [solaris,freebsd,perl,pugs,haskell] allbery@kf8nh.com system administrator [openafs,heimdal,too many hats] allbery@ece.cmu.edu electrical and computer engineering, carnegie mellon university KF8NH
Am Mittwoch, 30. Mai 2007 14:09 schrieb Brandon S. Allbery KF8NH:
On May 30, 2007, at 5:59 , Federico Squartini wrote:
I suppose there is something "under the hood" which makes them different, but I cannot figure out what.
For one thing, ST uses existential types to prevent values from leaking outside the monad.
ST uses universally-quantified types. Also note that an important difference between State and ST is that State can be implemented in pure Haskell while ST has to be hard-wired into the compiler/interpreter or implemented in Haskell using unsafe features. Best wishes, Wolfgang
I thought the types were *existentially* quantified because the constructor arguments were *universally* quantified. Or did I get it backwards? Dan Wolfgang Jeltsch wrote:
Am Mittwoch, 30. Mai 2007 14:09 schrieb Brandon S. Allbery KF8NH:
On May 30, 2007, at 5:59 , Federico Squartini wrote:
I suppose there is something "under the hood" which makes them different, but I cannot figure out what. For one thing, ST uses existential types to prevent values from leaking outside the monad.
ST uses universally-quantified types.
Also note that an important difference between State and ST is that State can be implemented in pure Haskell while ST has to be hard-wired into the compiler/interpreter or implemented in Haskell using unsafe features.
Best wishes, Wolfgang _______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
On 31/05/07, Dan Weston <westondan@imageworks.com> wrote:
I thought the types were *existentially* quantified because the constructor arguments were *universally* quantified. Or did I get it backwards?
That'd be right, if the situation actually involved constructors. I.e., when people talk about existential types, they normally mean: data Foo = forall a. F a Which is isomorphic to: data Foo = F (exists a. a) Hence 'existential'. However, in this instance, it's just the higher-rank polymorphism that makes things work. For further detail, you might want to check out the Wikibook chapter on existentials (yes, it's a stupid place for such an explanation, as I've just realised!), which has a section on ST: http://en.wikibooks.org/wiki/Haskell/Existentially_quantified_types#Example:... -- -David House, dmhouse@gmail.com
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 <zednenem@psualum.com> | "In this house, we obey the laws <http://www.eyrie.org/~zednenem> | of thermodynamics!"
David Menendez writes:
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.)
Rats. The rank-2 type isn't enough to guarantee type-safety. You need a monad (or linear types) to make sure that the Store is used single-threadedly. Using the API above, you can defeat the type checker. coerce :: a -> b coerce a = withStore (\s0 -> let (r1,s1) = newRef a s0 (r2,s2) = newRef undefined s0 in readRef r2 s1) (Of course, you would have needed a function like coerce to implement the API in the first place.) -- David Menendez <zednenem@psualum.com> | "In this house, we obey the laws <http://www.eyrie.org/~zednenem> | of thermodynamics!"
participants (8)
-
Brandon S. Allbery KF8NH -
Dan Weston -
David House -
David Menendez -
dons＠cse.unsw.edu.au -
Federico Squartini -
Joel Koerwer -
Wolfgang Jeltsch