Re: [Haskell-cafe] (state) monad and CPS
Hello, Thank everybody for the answers. I must admit that I did not really emphasize the goal behind my initial question. Which is better expressed this way: 'walk' is written is CPS and is tail recursive. Unless I am wrong , if the continuation monad is used, the recursive calls to 'walk' are no longer in tail position. So my initial question was rather: is it possible to use the state monad and keeping the code tail recursive? I do not master all the subtilities of lazy evaluation yet and perhaps tail recursivity does not have the same importance (or does not offer the same guarantees) in a lazy language as it does in a strict language. But I am facing a similar problem with workflows in F# (F#'s monads). Thank you Regards J-C On Thu, Nov 12, 2009 at 8:17 AM, wren ng thornton w...@freegeek.org wrote: Nicolas Pouillard wrote: Excerpts from jean-christophe mincke's message of Tue Nov 10 21:18:34 +0100 2009: do acc - get put (acc+1) ... Since this pattern occurs often 'modify' is a combination of get and put: do modify (+1) ... Though the caveat about laziness applies here as well. modify is famously lazy which can lead to space leaks and stack overflows. Better would be to define and use your own strict version: modify' f = get = \x - put $! f x -- Live well, ~wren ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] (state) monad and CPS
Excerpts from wren ng thornton's message of Thu Nov 12 08:17:41 +0100 2009: Nicolas Pouillard wrote: Excerpts from jean-christophe mincke's message of Tue Nov 10 21:18:34 +0100 2009: do acc - get put (acc+1) ... Since this pattern occurs often 'modify' is a combination of get and put: do modify (+1) ... Though the caveat about laziness applies here as well. modify is famously lazy which can lead to space leaks and stack overflows. Better would be to define and use your own strict version: modify' f = get = \x - put $! f x However if you want a strict state you should better use Control.Monad.State.Strict [1]. Finally I'm wondering if [1] is strict enough... [1]: http://www.haskell.org/ghc/docs/latest/html/libraries/mtl/Control-Monad-State-Strict.html -- Nicolas Pouillard http://nicolaspouillard.fr ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] (state) monad and CPS
Excerpts from jean-christophe mincke's message of Tue Nov 10 21:18:34 +0100 2009: Hello, Hello, I would like to get some advice about state monad (or any other monad I guess) and CPS. Here is to remarks somewhat off topic: [...] walk Empty acc k = k acc walk (Leaf _) acc k = k (acc+1) walk (Node (l, _, r)) acc k = let k1 acc = walk r acc k in walk l (acc+1) k1 Remember that by default laziness and accumulators does not fits well together. Here you are probably building a chain of thunks. Making acc a strict argument (using !acc) or using 'seq' (acc `seq` ...) will cure this. [...] do acc - get put (acc+1) ... Since this pattern occurs often 'modify' is a combination of get and put: do modify (+1) ... About your CPS question, you should have a look at the 'transformers' package, in particular the Control.Monad.Trans.Cont [1] module. [1]: http://hackage.haskell.org/packages/archive/transformers/0.1.4.0/doc/html/Control-Monad-Trans-Cont.html Best regards, -- Nicolas Pouillard http://nicolaspouillard.fr ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] (state) monad and CPS
Nicolas Pouillard wrote: Excerpts from jean-christophe mincke's message of Tue Nov 10 21:18:34 +0100 2009: do acc - get put (acc+1) ... Since this pattern occurs often 'modify' is a combination of get and put: do modify (+1) ... Though the caveat about laziness applies here as well. modify is famously lazy which can lead to space leaks and stack overflows. Better would be to define and use your own strict version: modify' f = get = \x - put $! f x -- Live well, ~wren ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] (state) monad and CPS
Hello, I would like to get some advice about state monad (or any other monad I guess) and CPS. Let's take a simple exemple (see the code below) 'walk' is a function written in CPS that compute the number of nodes leaves in a tree. It use a counter which is explicitly passed through calls. 'walk2' is does the same using the state monad but is not written in CPS Is it possible to write a function 'walk3' written in CPS and using the state monad? Thank you Regards J-C module M where import Control.Monad.State data Node = Node (Node, Int, Node) |Leaf Int |Empty deriving (Show) walk Empty acc k = k acc walk (Leaf _) acc k = k (acc+1) walk (Node (l, _, r)) acc k = let k1 acc = walk r acc k in walk l (acc+1) k1 nb = Node (Leaf 1, 2, Leaf 3) nd = Node (nb, 4, Empty) nh = Node (Empty, 8, Leaf 9) ng = Node (Leaf 6, 7, nh) ne = Node (nd, 5, ng) r = walk ne 0 id walk2 Empty = return () walk2 (Leaf _ ) = do acc - get put (acc+1) return () walk2 (Node (l, _, r)) = do acc - get put (acc+1) walk2 l walk2 r return () r2 = runState (walk2 ne) 0 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] (state) monad and CPS
Yes; check out the module Control.Monad.Cont, which has a monad for continuation passing style. In particular, note that most of the monads in Control.Monad.* are stackable in that there is a version of the monad which you can stack on top of an existing monad. So for example, you could use ContT to stack the CPS monad on top of the State monad, or StateT to stack the State monad on top of the CPS monad. Hope this helps, Greg On Nov 10, 2009, at 12:18 PM, jean-christophe mincke wrote: Hello, I would like to get some advice about state monad (or any other monad I guess) and CPS. Let's take a simple exemple (see the code below) 'walk' is a function written in CPS that compute the number of nodes leaves in a tree. It use a counter which is explicitly passed through calls. 'walk2' is does the same using the state monad but is not written in CPS Is it possible to write a function 'walk3' written in CPS and using the state monad? Thank you Regards J-C module M where import Control.Monad.State data Node = Node (Node, Int, Node) |Leaf Int |Empty deriving (Show) walk Empty acc k = k acc walk (Leaf _) acc k = k (acc+1) walk (Node (l, _, r)) acc k = let k1 acc = walk r acc k in walk l (acc+1) k1 nb = Node (Leaf 1, 2, Leaf 3) nd = Node (nb, 4, Empty) nh = Node (Empty, 8, Leaf 9) ng = Node (Leaf 6, 7, nh) ne = Node (nd, 5, ng) r = walk ne 0 id walk2 Empty = return () walk2 (Leaf _ ) = do acc - get put (acc+1) return () walk2 (Node (l, _, r)) = do acc - get put (acc+1) walk2 l walk2 r return () r2 = runState (walk2 ne) 0 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] (state) monad and CPS
Something like this should work:
newtype ContState r s a = ContState { runCS :: s - (a - s - r) - r }
instance Monad (ContState r s) where
return a = ContState $ \s k - k a s
m = f = ContState $ \s0 k - runCS m s $ \a s1 - runCS (f a) s1 k
instance MonadState s (ContState r s) where
get = ContState $ \s k - k s s
put s = ContState $ \_ k - k () s
instance MonadCont (ContState r s) where
callCC f = ContState $ \s0 ka - runCS (f $ \a - ContState $ \s1
kb - ka a s1) s0 ka
There's a design choice as to whether the inner continuation should be
called with s0 or s1; it depends if you want the continuation from
callCC to abort any state changes or preserve them up to that point.
-- ryan
On Tue, Nov 10, 2009 at 12:18 PM, jean-christophe mincke
jeanchristophe.min...@gmail.com wrote:
Hello,
I would like to get some advice about state monad (or any other monad I
guess) and CPS.
Let's take a simple exemple (see the code below)
'walk' is a function written in CPS that compute the number of nodes
leaves in a tree. It use a counter which is explicitly passed through calls.
'walk2' is does the same using the state monad but is not written in CPS
Is it possible to write a function 'walk3' written in CPS and using the
state monad?
Thank you
Regards
J-C
module M where
import Control.Monad.State
data Node =
Node (Node, Int, Node)
|Leaf Int
|Empty
deriving (Show)
walk Empty acc k = k acc
walk (Leaf _) acc k = k (acc+1)
walk (Node (l, _, r)) acc k = let k1 acc = walk r acc k
in
walk l (acc+1) k1
nb = Node (Leaf 1, 2, Leaf 3)
nd = Node (nb, 4, Empty)
nh = Node (Empty, 8, Leaf 9)
ng = Node (Leaf 6, 7, nh)
ne = Node (nd, 5, ng)
r = walk ne 0 id
walk2 Empty = return ()
walk2 (Leaf _ ) = do acc - get
put (acc+1)
return ()
walk2 (Node (l, _, r)) = do acc - get
put (acc+1)
walk2 l
walk2 r
return ()
r2 = runState (walk2 ne) 0
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] State monad is missing Applicative instance
ouch, I was confusing the mtl and transformers package... so basically transformers is a better replacement for mtl? or does mtl offer things transformers does not? On Sun, Mar 15, 2009 at 12:04 AM, Henning Thielemann lemm...@henning-thielemann.de wrote: On Sat, 14 Mar 2009, Peter Verswyvelen wrote: I was using the transformers but still had to implement the Applicative instance of State This package contains an applicative instance for StateT but not for State In 'transformers' State is a type synonym for StateT Identity and thus does not need an own instance declaration. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] State monad is missing Applicative instance
Peter Verswyvelen schrieb: ouch, I was confusing the mtl and transformers package... so basically transformers is a better replacement for mtl? or does mtl offer things transformers does not? transformers and monad-fd are cleanly separated, transformers is Haskell 98 and monad-fd uses functional dependencies. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] State monad is missing Applicative instance
I was using the transformers but still had to implement the Applicative instance of State This package contains an applicative instance for StateT but not for State On Sat, Mar 14, 2009 at 3:05 AM, Henning Thielemann lemm...@henning-thielemann.de wrote: On Thu, 12 Mar 2009, Peter Verswyvelen wrote: I think. Or is it defined in some other package? The 'transformers' package has those instances. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] State monad is missing Applicative instance
On Sat, 14 Mar 2009, Peter Verswyvelen wrote: I was using the transformers but still had to implement the Applicative instance of State This package contains an applicative instance for StateT but not for State In 'transformers' State is a type synonym for StateT Identity and thus does not need an own instance declaration. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] State monad is missing Applicative instance
Am Freitag, 13. März 2009 05:09 schrieb Denis Bueno: This works because every monad induces an Applicative instance in a way I've ingested just enough wine to forget. =] pure = return (*) = ap Best wishes, Wolfgang ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] State monad is missing Applicative instance
On Thu, 12 Mar 2009, Peter Verswyvelen wrote: I think. Or is it defined in some other package? The 'transformers' package has those instances. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] State monad is missing Applicative instance
I think. Or is it defined in some other package? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] State monad is missing Applicative instance
Looks like it may be defined in the package applicative-extras: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/applicative-extras But I'm not positive about that, and the docs are... sparse. Matt 2009/3/12 Peter Verswyvelen bugf...@gmail.com: I think. Or is it defined in some other package? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] State monad is missing Applicative instance
2009/3/12 Peter Verswyvelen bugf...@gmail.com: I think. Or is it defined in some other package? There's an existing ticket about this: http://hackage.haskell.org/trac/ghc/ticket/2316 Note that the ticket links to some old threads on librar...@haskell.org about the issue. regards, Bas ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] State monad is missing Applicative instance
2009/3/12 Peter Verswyvelen bugf...@gmail.com: I think. Or is it defined in some other package? Note that you can get an Applicative instance for free by using WrapMonad in Control.Applicative. For example, just today I was writing a quickcheck Arbitrary instance, and the Gen monad doesn't have an Applicative instance. No problem: instance Gen MyDataType where arbitrary = MyDataConstructor $ arbitrary * arbitrary becomes instance Gen MyDataType where arbitrary = unWrapMonad (MyDataConstructor $ WrapMonad arbitrary * WrapMonad arbitrary) This works because every monad induces an Applicative instance in a way I've ingested just enough wine to forget. =] Denis ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] State Monad - using the updated state
Ryan gave some great advice about restructuring your program to do what you want, but I wanted to give a small explanation of why that's necessary. 2009/1/7 Phil pbeadl...@mail2web.com: I want to be able to do: Get_a_random_number a whole load of other stuff Get the next number as defined by the updated state in the first call some more stuff Get another number, and so on. The issue you're having is that you're trying to do the other stuff in your 'main', but main isn't inside the State monad. The only State computation you're calling from main is getRanq1, but you really need another State computation that does other stuff and calls getRanq1 itself. That's what Ryan's first suggestion implements. You need all your other stuff to be done inside the State monad so that it has read/update access to the current random state. So all your main does is run a State computation. That computation calls getRanq1 itself and then other stuff in between calls to getRanq1. Does that make sense? Kurt ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] State Monad - using the updated state
I think I've got this now - thanks to you all for the superb advice! The reason I cannot increment state inside main is because main is not a State monad (it's an IO monad). Thus in order to use my State Monad, I have execute inside a State monad as that the state is encapsulated in there. I'll have to have a think about how I'm going to structure the rest of my code inside something like Ryan's randomComputation example - the basic example works perfectly! I'm writing a Monte Carlo simulator for financial portfolios - it's something I've done in several languages so I often use it to test drive a new language. Most imperative implementations of this sort thing are very state-heavy, so I thought it would fun to re-think it a bit in Haskell. My initial thoughts before delving into Monads was to take advantage of Haskell's lazy evaluation and create an 'infinite' list of randoms using something like the below: ranq1List :: (Word64 - a ) - Word64 - [a] ranq1List converter state = converter newState : ranq1List converter newState where newState = ranq1Increment state This works fine - the converter is an extra parameter that carrys a partially defined function used to numerically translate from word64-whatever_type__we_want as stipulated in Numerical Recipes' C++ example. It was at this point I felt it was getting a bit ugly and started to look at Monads (plus I wanted to see what all 'fuss' was about with Monads too!). One more question on this - the other concern I had with the recursive list approach was that although lazy evaluation prevents me generating numbers before I 'ask' for them, I figured that if I was going to be asking for say 10 million over the course of one simulation, that although I request them one by one, over hours or even days, at the end of the simulation I will still have a list of 10 million word64s - each of which I could throw away within minutes of asking for it. This seemed like huge memory bloat, and thus probably I was taking the wrong approach. I'd be interested to know if you have any thoughts on the various solutions? Ryan's randomComputation strikes me as the most practical and there's an old adage that if a language provides a facility (i.e. The State Monad here), you shouldn't be rewriting similar functionality yourself unless there is a very very good reason to go it alone. Thus I figure that Haskell's State Monad used as described is always going to beat anything I come up with to do the same thing - unless I spend an awful lot of time tailoring a specific solution. If you think there is a nicer non-Monadic, pure solution to this type of problem, I'd be interested to hear them. Thanks again for all your help, Phil. On 08/01/2009 13:27, Kurt Hutchinson kelansli...@gmail.com wrote: Ryan gave some great advice about restructuring your program to do what you want, but I wanted to give a small explanation of why that's necessary. 2009/1/7 Phil pbeadl...@mail2web.com: I want to be able to do: Get_a_random_number a whole load of other stuff Get the next number as defined by the updated state in the first call some more stuff Get another number, and so on. The issue you're having is that you're trying to do the other stuff in your 'main', but main isn't inside the State monad. The only State computation you're calling from main is getRanq1, but you really need another State computation that does other stuff and calls getRanq1 itself. That's what Ryan's first suggestion implements. You need all your other stuff to be done inside the State monad so that it has read/update access to the current random state. So all your main does is run a State computation. That computation calls getRanq1 itself and then other stuff in between calls to getRanq1. Does that make sense? Kurt ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] State Monad - using the updated state
On Thu, Jan 8, 2009 at 12:56 PM, Phil pbeadl...@mail2web.com wrote: One more question on this - the other concern I had with the recursive list approach was that although lazy evaluation prevents me generating numbers before I 'ask' for them, I figured that if I was going to be asking for say 10 million over the course of one simulation, that although I request them one by one, over hours or even days, at the end of the simulation I will still have a list of 10 million word64s - each of which I could throw away within minutes of asking for it. This seemed like huge memory bloat, and thus probably I was taking the wrong approach. if you don't hold on to the whole list, i.e. you use the head of the list and then pass the tail around, the garbage collector will collect the unused prefix. In Haskell lists are used like loops. If a list is used in a sufficiently forgetful fashion, it will use constant space. Luke I'd be interested to know if you have any thoughts on the various solutions? Ryan's randomComputation strikes me as the most practical and there's an old adage that if a language provides a facility (i.e. The State Monad here), you shouldn't be rewriting similar functionality yourself unless there is a very very good reason to go it alone. Thus I figure that Haskell's State Monad used as described is always going to beat anything I come up with to do the same thing - unless I spend an awful lot of time tailoring a specific solution. If you think there is a nicer non-Monadic, pure solution to this type of problem, I'd be interested to hear them. Thanks again for all your help, Phil. On 08/01/2009 13:27, Kurt Hutchinson kelansli...@gmail.com wrote: Ryan gave some great advice about restructuring your program to do what you want, but I wanted to give a small explanation of why that's necessary. 2009/1/7 Phil pbeadl...@mail2web.com: I want to be able to do: Get_a_random_number a whole load of other stuff Get the next number as defined by the updated state in the first call some more stuff Get another number, and so on. The issue you're having is that you're trying to do the other stuff in your 'main', but main isn't inside the State monad. The only State computation you're calling from main is getRanq1, but you really need another State computation that does other stuff and calls getRanq1 itself. That's what Ryan's first suggestion implements. You need all your other stuff to be done inside the State monad so that it has read/update access to the current random state. So all your main does is run a State computation. That computation calls getRanq1 itself and then other stuff in between calls to getRanq1. Does that make sense? Kurt ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] State Monad - using the updated state
Hi, I¹m a newbie looking to get my head around using the State Monad for random number generation. I¹ve written non-monad code that achieves this no problem. When attempting to use the state monad I can get what I know to be the correct initial value and state, but can¹t figure out for the life of me how to then increment it without binding more calls there and then. Doing several contiguous calls is not what I want to do here and the examples I¹ve read all show this (using something like liftM2 (,) myRandom myRandom). I want to be able to do: Get_a_random_number a whole load of other stuff Get the next number as defined by the updated state in the first call some more stuff Get another number, and so on. I get the first number fine, but am lost at how to get the second, third, forth etc without binding there and then. I just want each number one at a time where and when I want it, rather than saying give 1,2,10 or even n¹ numbers now. I¹m sure it¹s blindly obvious! Note: I¹m not using Haskell¹s built in Random functionality (nor is that an option), I¹ll spare the details of the method I¹m using (NRC¹s ranq1) as I know it works for the non-Monad case, and it¹s irrelevent to the question. So the code is: ranq1 :: Word64 - ( Double, Word64 ) ranq1 state = ( output, newState ) where newState = ranq1Increment state output = convert_to_double newState ranq1Init :: Word64 - Word64 ranq1Init = convert_to_word64 . ranq1Increment . xor_v_init -- I¹ll leave the detail of how ranq1Increment works out for brevity. I know this bit works fine. Same goes for the init function it¹s just providing an initial state. -- The Monad State Attempt getRanq1 :: State Word64 Double getRanq1 = do state - get let ( randDouble, newState ) = ranq1 state put newState return randDouble _ And then in my main _ -- 124353542542 is just an arbitrary seed main :: IO() main = do let x = evalState getRanq1 (ranq1Init 124353542542) print (x) As I said this works fine; x gives me the correct first value for this sequence, but how do I then get the second and third without writing the giveMeTenRandoms style function? I guess what I want is a next() type function, imperatively speaking. Many thanks for any help, Phil. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] State Monad - using the updated state in an adhoc manner
Hi, I¹m a newbie looking to get my head around using the State Monad for random number generation. I¹ve written non-monad code that achieves this no problem. When attempting to use the state monad I can get what I know to be the correct initial value and state, but can¹t figure out for the life of me how to then increment it without binding more calls there and then. Doing several contiguous calls is not what I want to do here and the examples I¹ve read all show this (using something like liftM2 (,) myRandom myRandom). I want to be able to do: Get_a_random_number a whole load of other stuff Get the next number as defined by the updated state in the first call some more stuff Get another number, and so on. I get the first number fine, but am lost at how to get the second, third, forth etc without binding there and then. I just want each number one at a time where and when I want it, rather than saying give 1,2,10 or even n¹ numbers now. I¹m sure it¹s blindly obvious! Note: I¹m not using Haskell¹s built in Random functionality (nor is that an option), I¹ll spare the details of the method I¹m using (NRC¹s ranq1) as I know it works for the non-Monad case, and it¹s irrelevent to the question. So the code is: ranq1 :: Word64 - ( Double, Word64 ) ranq1 state = ( output, newState ) where newState = ranq1Increment state output = convert_to_double newState ranq1Init :: Word64 - Word64 ranq1Init = convert_to_word64 . ranq1Increment . xor_v_init -- I¹ll leave the detail of how ranq1Increment works out for brevity. I know this bit works fine. Same goes for the init function it¹s just providing an initial state. -- The Monad State Attempt getRanq1 :: State Word64 Double getRanq1 = do state - get let ( randDouble, newState ) = ranq1 state put newState return randDouble _ And then in my main _ -- 124353542542 is just an arbitrary seed main :: IO() main = do let x = evalState getRanq1 (ranq1Init 124353542542) print (x) As I said this works fine; x gives me the correct first value for this sequence, but how do I then get the second and third without writing the giveMeTenRandoms style function? I guess what I want is a next() type function, imperatively speaking. Many thanks for any help, Phil. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] State Monad - using the updated state
Hi Phil. First a quick style comment, then I'll get to the meat of your question. getRanq1 is correct; although quite verbose. A simpler definition is this: getRanq1 = State ranq1 This uses the State constructor from Control.Monad.State: State :: (s - (a,s)) - State s a What it sounds like you want is this: main = do x - getARandomNumber ... do some other stuff y - getAnotherRandomNumber .. etc. using State. There are two ways to go about this; the first is, if the entire computation is pure, that is, the do some other stuff doesn't do IO, you can embed the whole computation in State: seed = 124353542542 main = do result - evalState randomComputation (ranq1Init seed) ... some IO using result ... randomComputation = do x - getRanq1 let y = some pure computation using x z - getRanq1 w - something that uses x, y, and z that also uses the random source ... etc. return (some result) The other option, if you want to do IO in between, is to use a transformer version of State: type MyMonad a = StateT Word64 IO a main = withStateT (ranq1Init seed) $ do x - getRanq1_t liftIO $ print x ... y - getRanq1_t ... getRanq1_t :: MyMonad Double getRanq1_t = liftStateT getRanq1 liftStateT :: State s a - MyMonad a liftStateT m = StateT $ \s - return (runState m s) withStateT :: Word64 - MyMonad a - IO a withStateT s m = evalStateT m s -- can also just use withStateT = flip evalStateT This uses these functions from Control.Monad.State: liftIO :: MonadIO m = IO a - m a This takes any IO action and puts it into any monad that supports IO. In this case, StateT s IO a fits. runState :: StateT s a - s - (a,s) This evaluates a pure stateful computation and gives you the result. StateT :: (s - m (a,s)) - StateT s m a This builds a StateT directly. You could get away without it like this: liftStateT m = do s - get let (a, s') = runState m s put s' return a (note the similarity to your getRanq1 function!) evalStateT :: StateT s m a - s - m a This is just evalState for the transformer version of State. In our case it has the type (MyMonad a - Word64 - IO a) This said, as a beginner I recommend trying to make more of your code pure so you can avoid IO; you do need side effects for some things, but while learning it makes sense to try as hard as you can to avoid it. You can make a lot of interesting programs with just interact and pure functions. If you're just doing text operations, try to make your program look like this: main = interact pureMain pureMain :: String - String pureMain s = ... You'll find it will teach you a lot about laziness the power of purity! A key insight is that State *is* pure, even though code using it looks somewhat imperative. -- ryan P.S. If you can't quite get out of the imperative mindset you can visit imperative island via the ST boat. 2009/1/7 Phil pbeadl...@mail2web.com: Hi, I'm a newbie looking to get my head around using the State Monad for random number generation. I've written non-monad code that achieves this no problem. When attempting to use the state monad I can get what I know to be the correct initial value and state, but can't figure out for the life of me how to then increment it without binding more calls there and then. Doing several contiguous calls is not what I want to do here – and the examples I've read all show this (using something like liftM2 (,) myRandom myRandom). I want to be able to do: Get_a_random_number a whole load of other stuff Get the next number as defined by the updated state in the first call some more stuff Get another number, and so on. I get the first number fine, but am lost at how to get the second, third, forth etc without binding there and then. I just want each number one at a time where and when I want it, rather than saying give 1,2,10 or even 'n' numbers now. I'm sure it's blindly obvious! Note: I'm not using Haskell's built in Random functionality (nor is that an option), I'll spare the details of the method I'm using (NRC's ranq1) as I know it works for the non-Monad case, and it's irrelevent to the question. So the code is: ranq1 :: Word64 - ( Double, Word64 ) ranq1 state = ( output, newState ) where newState = ranq1Increment state output = convert_to_double newState ranq1Init :: Word64 - Word64 ranq1Init = convert_to_word64 . ranq1Increment . xor_v_init -- I'll leave the detail of how ranq1Increment works out for brevity. I know this bit works fine. Same goes for the init function it's just providing an initial state. -- The Monad State Attempt getRanq1 :: State Word64 Double getRanq1 = do state - get let ( randDouble, newState ) = ranq1 state put newState return randDouble _ And then in my main _ -- 124353542542 is just an arbitrary seed main :: IO() main = do let x = evalState getRanq1 (ranq1Init 124353542542)
Re: [Haskell-cafe] State Monad - using the updated state in an adhoc manner
On 2009 Jan 7, at 20:58, Phil wrote: -- 124353542542 is just an arbitrary seed main :: IO() main = do let x = evalState getRanq1 (ranq1Init 124353542542) print (x) You're throwing away the state you want to keep by using evalState there. But you're also missing the point of using State; done right the evalState *is* what you want. What you want to do is run all of your operations within State, exiting it only when you're done: main = do print (evalState doRanqs (ranq1init 124353542542)) doRanqs = do r - getRanq1 -- do something involving it another - getRanq1 -- do more stuff Alternately you may use a tail recursive function or a fold, etc., depending on what exactly you're trying to accomplish. You do *not* want to execState or runState every individual time you want a random number; if you do that you'll have to carry the random state around yourself (in effect you'd be rewriting the State monad by hand, poorly). Stay in State and let it do the carrying for you. -- brandon s. allbery [solaris,freebsd,perl,pugs,haskell] allb...@kf8nh.com system administrator [openafs,heimdal,too many hats] allb...@ece.cmu.edu electrical and computer engineering, carnegie mellon universityKF8NH ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] state monad and continuation monads ...
2008/9/30 Galchin, Vasili [EMAIL PROTECTED]:
Hello,
I would like to read
1) pedagogical examples of State monad and the Continuation monad
2) library usage of these monads
Regarding 1), there is a lot to find on the web. Maybe start on haskell.org.
In term of example, here is one I like :
✁--
module StateExample where
import Control.Monad.State
-- The state : it is threaded along each
-- command in MyMonad.
type MyState = Int
-- A particular use of the State monad :
-- simply to wrap a value of type MyState.
type MyMonad a = State MyState a
-- Inc increments the state.
-- The get function retrieves the state
-- and the put function replaces it.
-- The () in :: MyMonad () means that
-- inc doesn't return any (meaningful)
-- value. It just has a side effect (it changes
-- the wrapped state).
-- get has type MyMonad MyState and
-- put has type MyState - MyMonad ().
inc :: MyMonad ()
inc = do
v - get
put (v + 1)
-- Example usage of the State monad with
-- runState (see the docs for other such functions)).
-- It starts with the value 5 as the wrapped state.
-- THe it performs three times the 'inc' command.
-- Thus it produces 8 as the new state.
-- As noted aboved, it also returns ().
-- Try it in GHCi. Change the {...} and use
-- get and put. Implement something else than
-- the inc function.
example = runState (do {inc ; inc ; inc}) 5
✁--
Cheers,
Thu
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] state monad and continuation monads ...
On Tue, 30 Sep 2008, Galchin, Vasili wrote: Hello, I would like to read 1) pedagogical examples of State monad and the Continuation monad 2) library usage of these monads For continuations I found the withCString example especially convincing: http://www.haskell.org/haskellwiki/Continuation#Intermediate_structures ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] state monad and continuation monads ...
Galchin, Vasili wrote: 1) pedagogical examples of State monad and the Continuation monad Shameless plug: http://www.vex.net/~trebla/haskell/ContMonad.lhs ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] state monad and continuation monads ...
Hello, I would like to read 1) pedagogical examples of State monad and the Continuation monad 2) library usage of these monads Regards, Vasili ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] State monad in the wikibood article
Matthew Brecknell: Note the lambda abstraction (\st - ...) at the beginning of the definition. This means that (container = fn) returns a *function* that maps an input state to the result of (container2 st2). It doesn't return the result of (container st2) directly. Ah. Silly me :D Thanks a bunch mate. Cheers :) TJ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] State monad in the wikibood article
In the wikibook article here: http://en.wikibooks.org/wiki/Haskell/Understanding_monads, which really does an excellent job explaining things (nuclear waste woohoo!), I am stuck at the following code snippet: container = fn = \st - let (a, st2) = container st container2 = fn a in container2 st2 What stumps me is that (=) is supposed to return a container, but if we return (container2 st2) as in the code, then what we're really returning is the contents of the container! So what would happen if we do this: nuclearWasteInContainer = processTheWaste = thoroughProcessTheWaste It seems to me that the second (=) in the above expression would have the arguments (nuclearWaste) and (nuclearWasteProcessor), when what it really expects are (Container nuclearWaste) and (nuclearWasteProcessor). So isn't something wrong with the definition of (=) above? Or am I missing something? (I know the article says that the type for their supposed State monad at that point is not actually correct, and will be clarified further on, but that seems to be irrelevant to my question.) TJ the forever noobie. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] State monad in the wikibood article
TJ [EMAIL PROTECTED] said: In the wikibook article here: http://en.wikibooks.org/wiki/Haskell/Understanding_monads, which really does an excellent job explaining things (nuclear waste woohoo!), I am stuck at the following code snippet: container = fn = \st - let (a, st2) = container st container2 = fn a in container2 st2 What stumps me is that (=) is supposed to return a container, but if we return (container2 st2) as in the code, then what we're really returning is the contents of the container! Note the lambda abstraction (\st - ...) at the beginning of the definition. This means that (container = fn) returns a *function* that maps an input state to the result of (container2 st2). It doesn't return the result of (container st2) directly. So what would happen if we do this: nuclearWasteInContainer = processTheWaste = thoroughProcessTheWaste It seems to me that the second (=) in the above expression would have the arguments (nuclearWaste) and (nuclearWasteProcessor), when what it really expects are (Container nuclearWaste) and (nuclearWasteProcessor). So isn't something wrong with the definition of (=) above? Or am I missing something? (I know the article says that the type for their supposed State monad at that point is not actually correct, and will be clarified further on, but that seems to be irrelevant to my question.) TJ the forever noobie. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] State monad strictness - how?
John Meacham wrote: incidentally, I made a very strict and unboxed version of the RWS monad, since it is a darn useful one in jhc. right now, it only implements the things I needed, but it might be useful to include somewhere common and expanded on http://repetae.net/dw/darcsweb.cgi?r=jhc;a=headblob;f=/Util/RWS.hs John I have copied your email and the code to the wiki at http://haskell.org/haskellwiki/New_monads/UnboxedRWS and linked to it from the page that collects such items: http://haskell.org/haskellwiki/New_monads Everyone who is discussing variants of State might consider posting useful implementations on the wiki under New_monads. For example, some time ago I posted a LazyWriterT that added the '~' to the tuple matching in (=) and mfix. -- Chris ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] State monad strictness - how?
Iavor Diatchki wrote: The state transformer inherits its behavior from the underlying monad. Ross Paterson wrote: This (like StateT) gives you strictness in the pair, but doesn't give the strictness in the state that the original poster wanted. I think it does - if you run his program with State Int replaced by StateT Int Identity, it now runs in constant memory. Once we have this kind of strictness, then the programmer has control over the state. That is true for MTL as well. Regards, Yitz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Re[2]: [Haskell-cafe] State monad strictness - how?
Josef Svenningsson wrote: Take the state monad for example. Should it be strict or lazy in the state that it carries around? What about the value component? ...both strict and lazy variants are useful. I wrote: Are those really needed? ...it wouldn't be very convenient, would it? Sometimes I find that I want strict state by default and then I don't want to sprinkle my code with seqs. I don't think that is so inconvenient. Why do we need to define getStrict, putStrict, getsStrict, etc., when it is perhaps even more clear to write get $!, put $!., (gets . ($!)), etc.?. The same goes for Iavor's monad library. Now, the challenge here is to design a library which doesn't explode in size from all the various possibilities for strictness or laziness. I am now pretty convinced that the only thing we need is two versions of each monad, varying only the strictness of =. Then, of course, we will need runFoo for each, and evalFoo and execFoo for each state monad. And adaptors that allow you to run a lazy calculation inside a strict one and vice-versa. So we need an asStrict function and an asLazy function for each lazy/strict pair of monads. I think that is all we need. Not too bad. I am very impressed that we get most of that almost for free in Iavor's library. The same challenge exists in many of the Data.* libraries. I think this is very important. I am now a bit more optimistic. Has anyone looked through them? http://www.cs.chalmers.se/~josefs/monadlib/ ...instantiating this with different pair types with different strictness properties will give us total control over strictness for state and value. Hmm. Your current implementation doesn't seem to do it that way. You use tuples for both the lazy version and the strict version, and each defines its own Monad instance for all Pair types. So it is impossible to use both in the same module, even with hiding. I tried to work on this a little. I defined a strict Pair type and tried to find a single Monad instance that will give the right strictness for both if you just vary between lazy and strict pairs. We need that both of the following converge in constant stack space: take 100 $ evalState (repeatM $ modify (+1)) 0 execStateStrict (replicateM_ 10 $ modify (+1)) 0 (You can verify that this is true if you use the standard evalState, and replace execStateStrict with runIdentity . execStateT.) I was unable to hit upon the right combination of seqs in the Monad instance. Is it really possible? Of course, you could use a newtype of tuples and define separate Monad instances. But then we are not gaining anything over just defining the lazy and strict monads directly. Regards, Yitz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] State monad strictness - how?
Yitzchak Gale wrote: You're right, it is not in the docs. I don't think anyone would have planned it that way. StateT is strict only because there happens to be a line in a do-expression that looks like: (a, s') - runStateT m s The tuple pattern-match causes the strictness. That appears accidental, so it seems to be just an honest bug. I agree that this is an accident, but the bug is in lazy State, for three reasons: - Being strict in the (result,state) pair does not for the evaluation of either result or state. Not being strict could only ever be useful for a following action that made no use of either state or result, and I have a hard time imagining why you'd ever want to write such a beast, let alone in monadic style. In fact, an unboxed tuple would be even better. - Assuming that the State monad is lazy in the tuple, and you need to be strict in the state component, you are hosed. No amount of 'seq' will help you. On the other hand, were it strict and you needed it to be lazy, you could achieve that by manually boxing the data involved. - (=) should also be head strict in the state component. Again, if this is wrong, you can repair it. If laziness turns out wrong, you can't. Moreover, for most data types that you want to build lazily, especially lists, head strictness doesn't make a difference, as long as the tail is lazily evaluated. For data where you need strictness, such as integers or tuples of them, having strictness available make all the difference. I'd be fine with laziness being configurable, of course, but if it isn't, I want strict state. Come to think of it, it's probably just a bad idea that _|_ and (_|_,_|_) are different things. -Udo -- The Seventh Commandments for Technicians: Work thou not on energized equipment, for if thou dost, thy fellow workers will surely buy beers for thy widow and console her in other ways. signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] State monad strictness - how?
Ross Paterson wrote: This (like StateT) gives you strictness in the pair, but doesn't give the strictness in the state that the original poster wanted. I think the OP wanted both. If State is lazy in the pair, a long chain of the form (a = (b = (c = ... = z))) gets build up and blows the stack if it finally turns out that yes, all these steps are needed. Worse than that, there's no way to correct this without changing the definition of (=). Laziness in the state component is annoying at times, but not as bad. You can recover strictness by writing put $! x get = (put $!) . f instead of put x modify f provided that (=) is already strict in the pair. (It gets even more ugly if the state is a Data.Map that needs to be updated strictly, in which Data.Map.update also doesn't work, even combined with the above modifications.) -Udo -- The only problem with seeing too much is that it makes you insane. -- Phaedrus signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Re[2]: [Haskell-cafe] State monad strictness - how?
On 1/11/07, Yitzchak Gale [EMAIL PROTECTED] wrote: Josef Svenningsson wrote: Take the state monad for example. Should it be strict or lazy in the state that it carries around? What about the value component? ...both strict and lazy variants are useful. I wrote: Are those really needed? ...it wouldn't be very convenient, would it? Sometimes I find that I want strict state by default and then I don't want to sprinkle my code with seqs. I don't think that is so inconvenient. Why do we need to define getStrict, putStrict, getsStrict, etc., when it is perhaps even more clear to write get $!, put $!., (gets . ($!)), etc.?. The same goes for Iavor's monad library. Indeed. I'm embarrassed that I've never realized this before. I suppose I though the tuple solution was so elegant that I never realized there was a simpler solution at hand. Now, the challenge here is to design a library which doesn't explode in size from all the various possibilities for strictness or laziness. I am now pretty convinced that the only thing we need is two versions of each monad, varying only the strictness of =. Then, of course, we will need runFoo for each, and evalFoo and execFoo for each state monad. And adaptors that allow you to run a lazy calculation inside a strict one and vice-versa. So we need an asStrict function and an asLazy function for each lazy/strict pair of monads. I think that is all we need. Not too bad. I am very impressed that we get most of that almost for free in Iavor's library. Yes, it seems quite feasible. http://www.cs.chalmers.se/~josefs/monadlib/ ...instantiating this with different pair types with different strictness properties will give us total control over strictness for state and value. Hmm. Your current implementation doesn't seem to do it that way. You use tuples for both the lazy version and the strict version, and each defines its own Monad instance for all Pair types. So it is impossible to use both in the same module, even with hiding. The way I enable laziness in a strict monad and vice versa is to use a non-standard bind operator, strictBind or lazyBind. But that's not really scalable. The whole architecture that I used in my library isn't really all that good. The reason I came up with it was to solve a completely different problem which doesn't really apply to this library anyway. The library design you outline above is indeed the way to go. I tried to work on this a little. I defined a strict Pair type and tried to find a single Monad instance that will give the right strictness for both if you just vary between lazy and strict pairs. We need that both of the following converge in constant stack space: take 100 $ evalState (repeatM $ modify (+1)) 0 execStateStrict (replicateM_ 10 $ modify (+1)) 0 (You can verify that this is true if you use the standard evalState, and replace execStateStrict with runIdentity . execStateT.) I was unable to hit upon the right combination of seqs in the Monad instance. Is it really possible? Of course, you could use a newtype of tuples and define separate Monad instances. But then we are not gaining anything over just defining the lazy and strict monads directly. I'm not sure exactly what you're trying to achieve here. If the tuple type you have is strict in both components then you're never going to get these examples to work. However, if you choose the lazy state monad and choose tuples carefully then both example can be made to terminate. Here's an example: ex1 = take 100 $ evalState ((repeatM $ modify (+1))::StateP StrictLeft Int [()]) 0 ex2 = execStateStrict ((replicateM_ 10 $ modify (+1)) :: StateTP StrictLeft Int Identity ()) 0 The first example also terminates with the all lazy pair (,), the importance is the laziness of the right component. Cheers, Josef ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] State monad strictness - how?
incidentally, I made a very strict and unboxed version of the RWS monad, since it is a darn useful one in jhc. right now, it only implements the things I needed, but it might be useful to include somewhere common and expanded on http://repetae.net/dw/darcsweb.cgi?r=jhc;a=headblob;f=/Util/RWS.hs John -- John Meacham - ⑆repetae.net⑆john⑈ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] State monad strictness - how?
Dean Herington wrote: I can't seem to figure out how to achieve strictness in the context of the State monad. Unfortunately, the current situation is that State is only available as a lazy monad, and StateT is only available as a strict monad. It seems to me that this should clearly be considered a serious bug in the library. It has been reported on numerous occasions over the years, but it has still not been fixed. At the very least, the two should be consistent. I would much prefer for them both to be lazy. I have written a lot of code that depends on that; it is the natural assumption in Haskell that everything is lazy by default, except seq, IO, and their friends. The obvious solution would be to have available both a lazy and a strict version of each monad: State, State', StateT, and State'T (or some such), with functions to convert between them. It is trivial to implement that in the current library. If someone can come up with a more elegant solution right away, that would be great. (Iavor - do you have a solution?) Otherwise, I think we have waited long enough. Let's implement the simple fix. This bug is a major inconvenience to users of this library. (try 100) overflows the stack. In the current situation, you can use where final = runIdentity $ execStateT prog (0::Int) ... tick :: (Num a, MonadState a m) = m a ... Regards, Yitz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re[2]: [Haskell-cafe] State monad strictness - how?
Hello Yitzchak, Wednesday, January 10, 2007, 12:02:25 PM, you wrote: Unfortunately, the current situation is that State is only available as a lazy monad, and StateT is only available as a strict monad. At the very least, the two should be consistent. I would much prefer for them both to be lazy. imho, lazy monads (as any other lazy things) is a source of beginner's confusion. therefore it may be better to provide default monads as strict and lazy ones - for one who knows what he wants - with a Lazy prefix, e.g. LazyST, LazyState... -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Re[2]: [Haskell-cafe] State monad strictness - how?
Hi Bulat, I wrote: [State and StateT] should be consistent. I would much prefer for them both to be lazy. Bulat Ziganshin wrote: imho, lazy monads (as any other lazy things) is a source of beginner's confusion. therefore it may be better to provide default monads as strict and lazy ones - for one who knows what he wants - with a Lazy prefix, e.g. LazyST, LazyState... Well, as long as both are provided, that is fine with me. But I do not think that laziness in monad methods is a reason for beginners' confusion. First of all, it is natural to get a little confused about strictness at the beginning. I'm not sure it happens more often with monads than anywhere else. If there is more confusion about strictness with monads, it is because of the fact that many introductions/tutorials confuse all monads with IO. They say something like: So how do you create side effects in the real world? That is what monads are for. No, no, no! That is what ** IO ** is for. Most monads are pure! In fact, I think making the default strict will create more confusion. We should help beginners to understand right from the start that do-notation is not a procedure of commands for the computer to carry out. It is just a special syntax for defining functions. We use it when it is more natural to describe the effect of a function in a step-by-step style, just as happens sometimes in mathematics. But the compiler is under no obligation to follow our steps literally. Except with IO - when dealing with the real world, we need to be able to specify the exact order in which things happen. ST represents using physical memory as a fast storage device. So it is really IO in disguise. Regards, Yitz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Re[2]: [Haskell-cafe] State monad strictness - how?
Yitzchak, I agree with you that both lazy and strict monads are important and that we should have both options in a monad library. But the fun doesn't end there. There are other strictness properties to consider. Take the state monad for example. Should it be strict or lazy in the state that it carries around? What about the value component? I think the answer to these questions are the same as for monadic strictness above: both strict and lazy variants are useful. Now, the challenge here is to design a library which doesn't explode in size from all the various possibilities for strictness or laziness. In fact I did once bite the bullet and came up with a library that does all this. Though I haven't released it publicly yet. I never took the time to polish the code to the point where I wouldn't be embarrassed about showing it to others. If you kick me hard enough I might release the library. Cheers, Josef On 1/10/07, Yitzchak Gale [EMAIL PROTECTED] wrote: Hi Bulat, I wrote: [State and StateT] should be consistent. I would much prefer for them both to be lazy. Bulat Ziganshin wrote: imho, lazy monads (as any other lazy things) is a source of beginner's confusion. therefore it may be better to provide default monads as strict and lazy ones - for one who knows what he wants - with a Lazy prefix, e.g. LazyST, LazyState... Well, as long as both are provided, that is fine with me. But I do not think that laziness in monad methods is a reason for beginners' confusion. First of all, it is natural to get a little confused about strictness at the beginning. I'm not sure it happens more often with monads than anywhere else. If there is more confusion about strictness with monads, it is because of the fact that many introductions/tutorials confuse all monads with IO. They say something like: So how do you create side effects in the real world? That is what monads are for. No, no, no! That is what ** IO ** is for. Most monads are pure! In fact, I think making the default strict will create more confusion. We should help beginners to understand right from the start that do-notation is not a procedure of commands for the computer to carry out. It is just a special syntax for defining functions. We use it when it is more natural to describe the effect of a function in a step-by-step style, just as happens sometimes in mathematics. But the compiler is under no obligation to follow our steps literally. Except with IO - when dealing with the real world, we need to be able to specify the exact order in which things happen. ST represents using physical memory as a fast storage device. So it is really IO in disguise. Regards, Yitz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Re[2]: [Haskell-cafe] State monad strictness - how?
Hi Josef, Josef Svenningsson wrote: ...the fun doesn't end there. There are other strictness properties to consider. Could be. But after using mtl heavily for a few years now, I find that in practice the only one where have felt the need for control over strictness is =, like Dean's example. Take the state monad for example. Should it be strict or lazy in the state that it carries around? What about the value component? I think the answer to these questions are the same as for monadic strictness above: both strict and lazy variants are useful. Are those really needed? Can't the strictness of the state be fully controlled by seq with runState, get, and put, and by choosing lazy or strict =? And similarly with value? As opposed to =, where there is no way to control its strictness from outside the Monad instance declaration. Now, the challenge here is to design a library which doesn't explode in size from all the various possibilities for strictness or laziness. The same challenge exists in many of the Data.* libraries. I think this is very important. In fact I did once bite the bullet and came up with a library that does all this. Though I haven't released it publicly yet. I never took the time to polish the code to the point where I wouldn't be embarrassed about showing it to others. If you kick me hard enough I might release the library. My boot is not long enough :). But I would love to see what you did. Regards, Yitz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Re[2]: [Haskell-cafe] State monad strictness - how?
On 1/10/07, Yitzchak Gale [EMAIL PROTECTED] wrote:
Hi Josef,
Josef Svenningsson wrote:
...the fun doesn't end there. There are other strictness properties
to consider.
Could be. But after using mtl heavily for a few years now,
I find that in practice the only one where have felt the need
for control over strictness is =, like Dean's example.
Yes. For most uses this finer control of strictness is just overkill.
But in the rare cases when you really need this tweakability then it's
a royal pain if you don't have it.
Take the state monad for example. Should it be strict or
lazy in the state that it carries around? What about the value
component? I think the answer to these questions are the same as for
monadic strictness above: both strict and lazy variants are useful.
Are those really needed? Can't the strictness of the state be
fully controlled by seq with runState, get, and put, and by
choosing lazy or strict =? And similarly with value?
Yes, you're right. But it wouldn't be very convenient, would it?
Sometimes I find that I want strict state by default and then I don't
want to sprinkle my code with seqs. Furthermore this extra level of
control is not that difficult to implement in a library.
Now, the challenge here is to design a library which doesn't explode
in size from all the various possibilities for strictness or laziness.
The same challenge exists in many of the Data.* libraries.
I think this is very important.
Indeed.
In fact I did once bite the bullet and came up with a library that
does all this. Though I haven't released it publicly yet. I never took
the time to polish the code to the point where I wouldn't be
embarrassed about showing it to others.
If you kick me hard enough I might release the library.
My boot is not long enough :). But I would love to see
what you did.
:-) Ok, I've put some files under the following url:
http://www.cs.chalmers.se/~josefs/monadlib/
It might need some explanation since I use the module system quite
heavily. For a monad such as the state monad the hierarchy looks like
this:
* Control.Monad.State.Base contains the type declaration and basic
functionality, but NOT instances of the monad class.
This module is not exposed.
* Control.Monad.State.Lazy
* Control.Monad.State.Strict
Contains instances for monad classes.
* Control.Monad.State is supposed to be the default and just reexports
Control.Monad.State.Strict.
Furthermore, again taking the state monad as example, the monad is
parameterized on the type of pair used in the definition of the monad.
So instead of:
newtype State s a = State { runState :: (s - (a, s)) }
we have:
newtype StateP p s a = StateP { runStateP :: (s - p a s) }
Now, instantiating this with different pair types with different
strictness properties will give us total control over strictness for
state and value. Data.Pair provides various pair for this purpose.
Enjoy,
Josef
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] State monad strictness - how?
Hello,
Unfortunately, the current situation is that State is only
available as a lazy monad, and StateT is only available
as a strict monad.
There is no such distinction in monadLib. The state transformer
inherits its behavior from the underlying monad. For example: StateT
Int IO is strict, but StatT Int Id is lazy. One way to get a strict
state monad with monadLib is like this:
import MonadLib
data Lift a = Lift { runLift :: a }
instance Monad Lift where
return x = Lift x
Lift x = f = f x
strict = runLift $ runStateT 2 $
do undefined
return 5
lazy = runId $ runStateT 2 $
do undefined
return 5
The difference between those two is that strict == undefined, while
lazy = (5,undefined).
Unfortunately the monad Lift is not part of monadLib at the moment
so you have to define it on your own, like I did above, but I think
that this is a good example of when it is useful, so I will probably
add it to the next release.
-Iavor
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] State monad strictness - how?
Wow! Now we are talking!
Josef Svenningsson wrote:
So instead of:
newtype State s a = State { runState :: (s - (a, s)) }
we have:
newtype StateP p s a = StateP { runStateP :: (s - p a s) }
Now, instantiating this with different pair types with different
strictness properties will give us total control over strictness for
state and value.
Beautiful!
Iavor Diatchki wrote:
The state transformer inherits its behavior from the underlying
monad. For example: StateT Int IO is strict, but StateT Int Id
is lazy.
Fantastic!
I'm drooling. When can we get stuff like this into MTL?
And maybe it is finally time for me to bite the bullet and
try out monadLib again (is it still CPS? gulp).
Now let's attack Data.* libraries...
-Yitzchak
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] State monad strictness - how?
At 11:02 AM +0200 1/10/07, Yitzchak Gale wrote: Unfortunately, the current situation is that State is only available as a lazy monad, and StateT is only available as a strict monad. [...] The obvious solution would be to have available both a lazy and a strict version of each monad: State, State', StateT, and State'T (or some such), with functions to convert between them. It is trivial to implement that in the current library. First, thanks for the very helpful reply explaining the situation. Second, how would one know that State is lazy and StateT is strict? I don't see that in the Haddock documentation. Third, isn't it a continuum rather than a binary choice between lazy and strict? In my example, I used ($!) in the definition of (=), but that's just one flavor of strictness that was appropriate to my example. Is there some way to parameterize this degree of strictness? Dean ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] State monad strictness - how?
Dean Herington wrote: Third, isn't it a continuum rather than a binary choice between lazy and strict? In my example, I used ($!) in the definition of (=), but that's just one flavor of strictness that was appropriate to my example. Is there some way to parameterize this degree of strictness? Dean The r0 and rwhnf and rnf from http://www.haskell.org/ghc/docs/latest/html/libraries/base/Control-Parallel-Strategies.html parameterize strictness. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] State monad strictness - how?
hi, I'm drooling. When can we get stuff like this into MTL? And maybe it is finally time for me to bite the bullet and try out monadLib again (is it still CPS? gulp). version 3 (the current version) implements the transformers in the usual way (e.g., as in mtl) so no cps (except, of course, for the continuation transformer). as usual, feedback is welcome. -iavor ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] State monad strictness - how?
...how would one know that State is lazy and StateT is strict? I don't see that in the Haddock documentation. You're right, it is not in the docs. I don't think anyone would have planned it that way. StateT is strict only because there happens to be a line in a do-expression that looks like: (a, s') - runStateT m s The tuple pattern-match causes the strictness. That appears accidental, so it seems to be just an honest bug. Regards, Yitz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] State monad strictness - how?
On Wed, Jan 10, 2007 at 10:02:36AM -0800, Iavor Diatchki wrote: [Yitzchak Gale:] Unfortunately, the current situation is that State is only available as a lazy monad, and StateT is only available as a strict monad. There is no such distinction in monadLib. The state transformer inherits its behavior from the underlying monad. For example: StateT Int IO is strict, but StatT Int Id is lazy. One way to get a strict state monad with monadLib is like this: [strict pseudo-monad] This (like StateT) gives you strictness in the pair, but doesn't give the strictness in the state that the original poster wanted. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] State monad strictness - how?
haskell is the standard lazy functional language, so strictness ought to be called out. e.g. StateStrict rather than StateLazy. The traction that haskell is starting to get (and why I'm spending time learning it and following haskell-cafe) is not because its semantics are unsurprising to newbies. They are surprising and surprisingly powerful. A haskell that did no more than scheme would not be as interesting. I may be subject to selection bias, but I haven't seen so many references to a language in unexpected contexts since smalltalk in the mid 80's. I don't think that's because it's a language that behaves the way someone coming from another language expects. On 1/10/07, Bulat Ziganshin [EMAIL PROTECTED] wrote: Hello Yitzchak, Wednesday, January 10, 2007, 12:02:25 PM, you wrote: Unfortunately, the current situation is that State is only available as a lazy monad, and StateT is only available as a strict monad. At the very least, the two should be consistent. I would much prefer for them both to be lazy. imho, lazy monads (as any other lazy things) is a source of beginner's confusion. therefore it may be better to provide default monads as strict and lazy ones - for one who knows what he wants - with a Lazy prefix, e.g. LazyST, LazyState... -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] State monad strictness - how?
Hello, On 1/10/07, Ross Paterson [EMAIL PROTECTED] wrote: There is no such distinction in monadLib. The state transformer inherits its behavior from the underlying monad. For example: StateT Int IO is strict, but StatT Int Id is lazy. One way to get a strict state monad with monadLib is like this: [strict pseudo-monad] This (like StateT) gives you strictness in the pair, but doesn't give the strictness in the state that the original poster wanted. Once we have this kind of strictness, then the programmer has control over the state. For example, they can define: setStrict x = seq x (set x) ex3 = runLift $ runState 2 $ setStrict undefined return 5 ex4 = runId $ runState 2 $ setStrict undefined return 5 In these examples ex3 == undefined but ex4 = (5,undefined). -Iavor ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] State monad strictness - how?
I can't seem to figure out how to achieve strictness in the context of the State monad. Consider: import Control.Monad.State try count = print final where (_,final) = runState prog 0 prog = sequence_ (replicate count tick) tick :: State Int Int tick = do n - get put (n+1) return n (try 100) overflows the stack. It doesn't help to use: put $! (n+1) The only way I've been able to get the necessary strictness is to add use of ($!) in the definition of (=): data SState s a = SState (s - (a,s)) instance Monad (SState s) where return x = SState (\s - (x,s)) m = f = SState (\s - let SState m' = m (x,s1) = m' s SState f' = f x (y,s2) = f' $! s1 in (y,s2)) runSState (SState m) s = m s sget = SState (\s - (s,s)) sput s' = SState (\s - ((),s')) stry count = print final where (_,final) = runSState prog 0 prog = sequence_ (replicate count stick) stick :: SState Int Int stick = do n - sget sput (n+1) return n Is there no way to get strictness using the standard State monad? Dean___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] State Monad
On Fri, 4 Mar 2005, Mark Carroll wrote: (snip) Enclosed is a programme that asks for two ints from standard input, adds (snip) Let me try again. (-: -- Markmodule StackMTest where import StackM import Control.Monad import Control.Monad.Trans import System.IO import System.Random add :: Num a = StackM a IO () add = do x - popM y - popM pushM (x + y) throwTenDie :: StackM Int IO () throwTenDie = lift (getStdRandom (randomR (1, 10))) = pushM stackMTest :: StackM Int IO Int stackMTest = do pushNumber pushNumber throwTenDie add add popM where pushNumber = do text - lift $ getLine pushM (read text) main :: IO () main = runStackM stackMTest = print ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] State Monad
Thinking of stacks, I've often wondered if Haskell would be a good language for implementing a PostScript interpreter. I actually have the beginning of a PostScript interpreter somwhere... And the core of a Joy interpreter is extremely small. It's pretty much 'foldl compose . map interpretWord'. Of course, I implemented a Joy interpreter in the slightly sugared lambda calculus that lambdabot's @eval module supports so... (Crap, I actually want to find it (the PostScript interpreter) now.) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] State Monad
Thaks a lot for your contribution, this helps me a lot, I see what I've got to do. However, I understand the first version (Stack.hs), but I can't get what StateM.hs is. Is it the same version but using state transformers, so as to be able to do IO (which I would need)? In fact, could you give me a simple example of how to use StackM.hs, a simple example that pushes some ints and add the toppest two. Thanks a lot anyway, Sam. PS: In fact I'm trying to implement a simple RPN calculator. So at first I need +, push, pop and view which shows the whole list. Attached is what I started to do before I get your mail. Mark Carroll wrote: On Thu, 3 Mar 2005, Sam G. wrote: I need a Monad to represent an internal stack. I mean I've got a lot of functions which operates on lists and I would not like to pass the list as an argument everytime. Could you help me writing this monad? To start, I just need a + function which will return the sum of the 2 toppest elements of the stack. I wrote one which is at, http://www.aetion.com/src/Stack.hs http://www.aetion.com/src/StackM.hs Then, add :: Num a = Stack a () add = do x - pop y - pop push (x + y) or whatever. Of course, if you use Control.Monad.State where you store the stack as a list then you can probably just do something like, add = (x:y:z) - get put ((x+y):z) I hope that helps. -- Mark ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe module Main where main = do putStrLn Forth Environment\nCopyright (C) Sam G. 2005.\n doLoop [] doLoop list = do l - getLine let w = execute (pushWords (words l)) list in do write w doLoop w write [] = return () write (s:ss) = do putStrLn $ show (s::Int) write ss pushWords [] = return [] pushWords (s:ss) = do push $ read (s) pushWords ss newtype State state value = State (state - (state, value)) instance Monad (State state) where return v = State $ \s - (s, v) State f = k = State $ \s - let (s0, v0) = f s State g = k v0 in g s0 push a = State $ \s - (a:s, a) execute (State program) = fst . program ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] State Monad
I need a Monad to represent an internal stack. I mean I've got a lot of functions which operates on lists and I would not like to pass the list as an argument everytime. Could you help me writing this monad? To start, I just need a + function which will return the sum of the 2 toppest elements of the stack. Thanks in advance, Sam. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] State Monad
Hello again,
in fact I wrote the following state monad:
--
newtype State state value = State (state - (state, value))
instance Monad (State state) where
return v = State $ \s - (s, v)
State f = k = State $ \s - let (s0, v0) = f s
State g = k v0
in g s0
push a = State $ \s - (a:s, a)
prog= do {push 100 ; push 1}
execute (State program) = fst (program [])
--
but I never use value, so is there a way not to write it in the monad
definition?
Sam.
Sam G. wrote:
I need a Monad to represent an internal stack. I mean I've got a lot of functions which operates on lists and I would not like to pass the list as an argument everytime.
Could you help me writing this monad? To start, I just need a + function which
will return the sum of the 2 toppest elements of the stack.
Thanks in advance,
Sam.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] State Monad
On Thu, 2005-03-03 at 02:03 +0100, Sam G. wrote: I need a Monad to represent an internal stack. I mean I've got a lot of functions which operates on lists and I would not like to pass the list as an argument everytime. Could you help me writing this monad? To start, I just need a + function which will return the sum of the 2 toppest elements of the stack. Thanks in advance, Sam. Here's a little program for you to ponder over. Cheers, Bernie. import Control.Monad.State type Stack a = [a] push :: a - Stack a - Stack a push x s = x:s peek :: Stack a - Maybe a peek (x:_) = Just x peek other = Nothing multTopTwo :: Num a = Stack a - Stack a multTopTwo (x:y:rest) = x * y : rest multTopTwo other = other type StateStack a = State (Stack Int) a pushList :: [Int] - StateStack () pushList [] = return () pushList (x:xs) = (modify $ push x) pushList xs prog :: [Int] - StateStack (Maybe Int) prog xs = do pushList xs modify multTopTwo gets peek main = print $ evalState (prog [1..5]) [] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] State Monad
On Thu, 3 Mar 2005, Sam G. wrote: I need a Monad to represent an internal stack. I mean I've got a lot of functions which operates on lists and I would not like to pass the list as an argument everytime. Could you help me writing this monad? To start, I just need a + function which will return the sum of the 2 toppest elements of the stack. I wrote one which is at, http://www.aetion.com/src/Stack.hs http://www.aetion.com/src/StackM.hs Then, add :: Num a = Stack a () add = do x - pop y - pop push (x + y) or whatever. Of course, if you use Control.Monad.State where you store the stack as a list then you can probably just do something like, add = (x:y:z) - get put ((x+y):z) I hope that helps. -- Mark ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] State monad strictness (was: ... abysmal Language Shootout results)
How can anyone stay away from such a deliciously pointless
waste of time as implementing a wc(1) derivate? :-)
Here is my attempt:
import IO
type Count = Int
data CountingState = ST !Bool !Count !Count !Count
deriving (Show)
initCST = ST True 0 0 0
wc :: CountingState - [Char] - CountingState
wc (ST _ l w c) ('\n':xs) = wc (ST True (l+1) w (c+1)) xs
wc (ST _ l w c) (' ' :xs) = wc (ST True lw (c+1)) xs
wc (ST _ l w c) ('\t':xs) = wc (ST True lw (c+1)) xs
wc (ST True l w c) ( x :xs) = wc (ST False l (w+1) (c+1)) xs
wc (ST False l w c) ( x :xs) = wc (ST False lw (c+1)) xs
wc st [] = st
main :: IO ()
main = do
ST _ l w c - getContents = return . wc initCST
putStrLn $ (l `shows`) . spaces . (w `shows`) . spaces . (c `shows`) $ []
where spaces = (' ':) . (' ':) . (' ':)
I compiled this with ghc -O2 -funbox-strict-fields and got
the following performance results in a simple test.
The wc(1) tool:
$ time /usr/bin/wc /usr/share/dict/words
234937 234937 2486824
real0m0.069s
user0m0.059s
sys 0m0.008s
My version:
$ time ./wc /usr/share/dict/words
234937 234937 2486824
real0m0.406s
user0m0.322s
sys 0m0.060s
The version from the shootout pages:
$ time ./wc-shootout /usr/share/dict/words
234937 234937 2486824
real0m2.749s
user0m2.682s
sys 0m0.062s
Then I made another experiment. I figured, the code above
yells out to be written with a State monad. So I did that:
import IO
import Control.Monad.State
type Count = Int
data CountingState = ST !Bool !Count !Count !Count
deriving (Show)
type WordCounter = State CountingState ()
initCST = ST True 0 0 0
wc :: Char - WordCounter
wc x = get = \(ST b l w c) -
case (b,x) of
( _ , '\n') - put (ST True (l+1) w (c+1))
( _ , '\t') - put (ST True l w (c+1))
( _ , ' ' ) - put (ST True l w (c+1))
(True, _ ) - put (ST False l (w+1) (c+1))
(False, _ ) - put (ST False lw (c+1))
main :: IO ()
main = do
xs - getContents
let ST _ l w c = snd (runState (mapM wc xs) initCST)
putStrLn $ (l `shows`) . spaces . (w `shows`) . spaces . (c `shows`) $ []
where
spaces = (' ':) . (' ':) . (' ':)
Curiously enough, this version fails to process the words
file because it runs out of stack space! Naturally, it is
very slow, too. So I wonder: How needs that program above to
be changed in order to solve this space leak?
Why does this happen in the first place?
Peter
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] State Monad
Hi, thanks for your suggestion. The thing is, that I don't want to change the type of my transformation functions. To answer Iavor's question: I have basically two types of transformation functions. One StringTransformation (String - String) and one transformation with a string and something (e.g. random generator) ((a,String) - (a,String)). The vast majority of transformation I use are from the first type. I was looking for a nice way to write this in a the compact style. I haven't thought about exceptions yet. My current approach is as follows: withString :: String - State String () - String withString state monad = execState monad state withStringAndT :: String - t - StateT t (State String) () - String withStringAndT state t monad = execState (execStateT monad t) state modifyT :: ((t, String) - (t, String)) - StateT t (State String) () modifyT trans = do s - lift get t - get let (t', s') = trans (t, s) lift (put s') put t' now I can use either let str' = withString str $ do modify $ foo_stringtrans modify $ bar_stringtrans or let str' = withStringAndT str (gen) $ do modifyT $ foo_stringgentrans lift $ modify $ foo_stringtrans Cheers, Georg On Thu, 04 Mar 2004 08:51:04 +1300, Tom Pledger [EMAIL PROTECTED] wrote: Georg Martius wrote: [...] I could write: modifyT :: ((a, String) - (a, String)) - a - State String a modifyT trans a = do str - get let (a', str') = trans (a, str) put str' return a' f :: State String () f = do put hallo modify strTrans i - modifyT strIntTrans 4-- strIntTrans :: (Int, String) - (Int, String) i' - modifyT strIntTrans i... But this is obviously awkward. [...] Hi. People have already replied about the state monad aspect, but there's another small improvement I'd like to suggest. Look at what modifyT does with 'trans' and 'a'. They are always used together. So, how about combining them *outside* the definition of modifyT? modifyT :: (String - (a, String)) - State String a modifyT trans = do (a, s) - gets trans put s return a f = do ... i - modifyT (strIntTrans 4) -- strIntTrans :: Int - String - (Int, String) i' - modifyT (strIntTrans i) ... Aside: if you rewrite ($) similarly, you get id. Regards, Tom ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] State Monad
Hi folks, I have a question to the State Monad or Monads in general - I'am not sure. Lets assume I have functions to transform strings. I can use the State Monad as follows: strTrans :: String - String strTrans s = s ++ s f :: State String () f = do put hallo modify strTrans modify strTrans' ... Up to this point everything is clear. Now I have also functions to map from (a, String) - (a,String). I could write: modifyT :: ((a, String) - (a, String)) - a - State String a modifyT trans a = do str - get let (a', str') = trans (a, str) put str' return a' f :: State String () f = do put hallo modify strTrans i - modifyT strIntTrans 4-- strIntTrans :: (Int, String) - (Int, String) i' - modifyT strIntTrans i ... But this is obviously awkward. How can I stick two Monads in each other? I could't figure out how to use StateT. Any help would be appreciated. Thanks! Georg ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] State Monad
Am Mittwoch, 3. Mrz 2004 14:44 schrieb Georg Martius: [...] Now I have also functions to map from (a, String) - (a,String). I could write: modifyT :: ((a, String) - (a, String)) - a - State String a modifyT trans a = do str - get let (a', str') = trans (a, str) put str' return a' f :: State String () f = do put hallo modify strTrans i - modifyT strIntTrans 4 -- strIntTrans :: (Int, String) - (Int, String) i' - modifyT strIntTrans i ... But this is obviously awkward. How can I stick two Monads in each other? I could't figure out how to use StateT. StateT is one solution. See http://www.haskell.org/pipermail/haskell/2004-January/013330.html and the follow-ups (available via the next message links). With StateT, modifyT may be written as follows (untested code): modifyT :: ((a, String) - (a, String)) - StateT a (State String) () modifyT trans = do str - liftM get a - get let (a', str') = trans (a, str) liftM (put str') put a' Alternatively, you can use the ordinary state monad with (a,String) as its state. Then modifyT is just modify. [...] Thanks! Georg Wolfgang ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] State Monad
hi, Georg Martius wrote: Now I have also functions to map from (a, String) - (a,String). I could write: modifyT :: ((a, String) - (a, String)) - a - State String a modifyT trans a = do str - get let (a', str') = trans (a, str) put str' return a' f :: State String () f = do put hallo modify strTrans i - modifyT strIntTrans 4-- strIntTrans :: (Int, String) - (Int, String) i' - modifyT strIntTrans i ... But this is obviously awkward. How can I stick two Monads in each other? I could't figure out how to use StateT. Any help would be appreciated. Thanks! Georg could you be a little more specific on what you are trying to do? what do you mean by sticking two monads in each other, do you want to have two state componenets, or perhaps work with computations that manipulate state, but can also raise exceptions? -iavor -- == | Iavor S. Diatchki, Ph.D. student | | Department of Computer Science and Engineering | | School of OGI at OHSU | | http://www.cse.ogi.edu/~diatchki | == ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] State Monad
Am Mittwoch, 3. Mrz 2004 18:15 schrieb Georg Martius: Thanks for your answer. I got it now. It works with lift instead of liftM. Yes, of course. Georg Wolfgang ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] State Monad
Georg Martius wrote: [...] I could write: modifyT :: ((a, String) - (a, String)) - a - State String a modifyT trans a = do str - get let (a', str') = trans (a, str) put str' return a' f :: State String () f = do put hallo modify strTrans i - modifyT strIntTrans 4-- strIntTrans :: (Int, String) - (Int, String) i' - modifyT strIntTrans i ... But this is obviously awkward. [...] Hi. People have already replied about the state monad aspect, but there's another small improvement I'd like to suggest. Look at what modifyT does with 'trans' and 'a'. They are always used together. So, how about combining them *outside* the definition of modifyT? modifyT :: (String - (a, String)) - State String a modifyT trans = do (a, s) - gets trans put s return a f = do ... i - modifyT (strIntTrans 4) -- strIntTrans :: Int - String - (Int, String) i' - modifyT (strIntTrans i) ... Aside: if you rewrite ($) similarly, you get id. Regards, Tom ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
