<HTML>
<HEAD>
<TITLE>Re: [Haskell-cafe] Multiple State Monads</TITLE>
</HEAD>
<BODY>
<FONT SIZE="4"><FONT FACE="Calibri, Verdana, Helvetica, Arial"><SPAN STYLE='font-size:11pt'>Ahh, I see – so using the State monad is arguably overcomplicating this. This is very helpful.<BR>
<BR>
The use of ‘keyword’ was just an unfortunate use of terminology – my bad.<BR>
<BR>
Very useful explanation about the laziness resulting in stack overflows too – when I crank up the numbers I have been seeing this, I had been temporarily ignoring the issue and just increasing the stack size at runtime, but I suspected something was awry.<BR>
<BR>
One last question on this function:<BR>
<BR>
In the definition:<BR>
<BR>
mcSimulate :: Double -> Double -> Word64 -> [Dou<SPAN STYLE='font-size:14px'>ble]<BR>
<SPAN STYLE='font-size:11pt'>mcSimulate startStock endTime seedForSeed = fst expiryStock : mcSimulate startStock endTime newSeedForSeed<BR>
<BR>
It is abundantly clear that the startStock and endTime are just being passed around from call to call unchanged – that is their value is constant throughout the the simulation. For the purposes here when I’m only passing 2 ‘constants’ around it doesn’t strike me as too odd, but my list of ‘constants’ is likely to grow as I bolt more functionality onto this. For readability, I understand that I can create new types to encapsulate complex data types into a single type , but I can’t help thinking that passing say 9 or 10 ‘constants’ around and around like this ‘feels wrong’. If I sit back and think about it, it doesn’t strike me as implausible that the compiler will recognize what I’m doing and optimize this out for me, and what I’m doing is thinking about the whole think like a C++ programmer (which I traditionally am) would. <BR>
<BR>
However before I allayed my own concerns I wanted to check that in the Haskell world passing around lots of parameters isn’t a bad thing – that is, I’m not missing a trick here to make my code more readable or more importantly more performant.<BR>
<BR>
Thanks again,<BR>
<BR>
Phil.<BR>
<BR>
On 13/01/2009 23:24, "Luke Palmer" <lrpalmer@gmail.com> wrote:<BR>
<BR>
</SPAN></SPAN></SPAN></FONT></FONT><BLOCKQUOTE><FONT SIZE="4"><FONT FACE="Calibri, Verdana, Helvetica, Arial"><SPAN STYLE='font-size:11pt'><SPAN STYLE='font-size:14px'><SPAN STYLE='font-size:11pt'>On Tue, Jan 13, 2009 at 3:29 PM, Phil <pbeadling@mail2web.com> wrote:<BR>
</SPAN></SPAN></SPAN></FONT></FONT><BLOCKQUOTE><FONT SIZE="4"><FONT FACE="Calibri, Verdana, Helvetica, Arial"><SPAN STYLE='font-size:11pt'><SPAN STYLE='font-size:14px'><SPAN STYLE='font-size:11pt'>My only concern with using this method is - Will 'iterate' not create a full<BR>
list of type [Double] and then take the final position once the list has<BR>
been fully realized? For my application this would be undesirable as the<BR>
list may be millions of items long, and you only ever care about the last<BR>
iteration (It's a crude Monte Carlo simulator to give it some context). If<BR>
Haskell is smart enough to look ahead and see as we only need the last<BR>
element as it is creating the list, therefore garbage collecting earlier<BR>
items then this would work fine - by I'm guessing that is a step to far for<BR>
the compiler?<BR>
</SPAN></SPAN></SPAN></FONT></FONT></BLOCKQUOTE><FONT SIZE="4"><FONT FACE="Calibri, Verdana, Helvetica, Arial"><SPAN STYLE='font-size:11pt'><SPAN STYLE='font-size:14px'><SPAN STYLE='font-size:11pt'><BR>
No, doing this type of thing is very typical Haskell, and the garbage collector <I>will</I> incrementally throw away early elements of the list. <BR>
<BR>
</SPAN></SPAN></SPAN></FONT></FONT><BLOCKQUOTE><FONT SIZE="4"><FONT FACE="Calibri, Verdana, Helvetica, Arial"><SPAN STYLE='font-size:11pt'><SPAN STYLE='font-size:14px'><SPAN STYLE='font-size:11pt'><BR>
I had originally implemented this similar to the above (although I didn't<BR>
know about the 'iterate' keyword<BR>
</SPAN></SPAN></SPAN></FONT></FONT></BLOCKQUOTE><FONT SIZE="4"><FONT FACE="Calibri, Verdana, Helvetica, Arial"><SPAN STYLE='font-size:11pt'><SPAN STYLE='font-size:14px'><SPAN STYLE='font-size:11pt'><BR>
FWIW, iterate is just a function, not a keyword. Could just be terminology mismatch.<BR>
<BR>
So, while the garbage collector will do the right thing, for a list millions of elements long, I suspect you will get stack overflows and/or bad memory performance because the computation is too lazy. One solution is to use a stricter version of !!, which evaluates elements of the list as it whizzes by them. Because the function you're iterating is strict to begin with, you do not lose performance by doing this:<BR>
<BR>
</SPAN></SPAN></SPAN></FONT><SPAN STYLE='font-size:11pt'><SPAN STYLE='font-size:14px'><SPAN STYLE='font-size:11pt'><FONT FACE="Courier New">strictIdx :: Int -> [a] -> a<BR>
strictIdx _ [] = error "empty list"<BR>
strictIdx 0 (x:xs) = x<BR>
strictIdx n (x:xs) = x `seq` strictIdx (n-1) xs<BR>
</FONT><FONT FACE="Calibri, Verdana, Helvetica, Arial"><BR>
(Note that I flipped the arguments, to an order that is nicer for currying)<BR>
<BR>
The reason is that iterate f x0 constructs a list like this:<BR>
<BR>
[ x0, f x0, f (f x0), f (f (f x0)), ... ]<BR>
<BR>
But shares the intermediate elements, so if we were to evaluate the first f x0 to, say, 42, then the thunks are overwritten and become:<BR>
<BR>
[ x0, 42, f 42, f (f 42), ... ]<BR>
<BR>
So iterate f x0 !! 1000000 is f (f (f (f ( ... a million times ... f x0)))), which will be a stack overflow because of each of the calls. What strictIdx does is to evaluate each element as it traverses it, so that each call is only one function deep, then we move on to the next one.<BR>
<BR>
This is the laziness abstraction leaking. Intuition about it develops with time and experience. It would be great if this leak could be patched by some brilliant theorist somewhere.<BR>
<BR>
Luke<BR>
<BR>
</FONT></SPAN></SPAN></SPAN></FONT><BLOCKQUOTE><FONT SIZE="4"><SPAN STYLE='font-size:11pt'><SPAN STYLE='font-size:14px'><SPAN STYLE='font-size:11pt'><FONT FACE="Calibri, Verdana, Helvetica, Arial"> - which makes things tidier - a useful<BR>
tip!), I moved to using the state monad and replicateM_ for the first<BR>
truncate(endTime/timeStep)-1 elements so that everything but the last result<BR>
is thrown away, and a final bind to getEvolution would return the result.<BR>
<BR>
Now that the code has been modified so that no result is passed back, using<BR>
modify and execState, this can be simplified to "replicateM_<BR>
truncate(endTime/timeStep)" with no final bind needed. I've tried this and<BR>
it works fine.<BR>
<BR>
The key reason for using the Monad was to tell Haskell to discard all but<BR>
the current state. If I'm wrong about please let me know, as I don't want<BR>
to be guilty of overcomplicating my algorithm, and more importantly it means<BR>
I'm not yet totally grasping the power of Haskell!<BR>
<BR>
Thanks again,<BR>
<FONT COLOR="#888888"><BR>
Phil.<BR>
</FONT><BR>
<BR>
<BR>
<BR>
On 13/01/2009 03:13, "David Menendez" <dave@zednenem.com> wrote:<BR>
<BR>
> On Mon, Jan 12, 2009 at 8:34 PM, Phil <pbeadling@mail2web.com> wrote:<BR>
>> Thanks Minh - I've updated my code as you suggested. This looks better than<BR>
>> my first attempt!<BR>
>><BR>
>> Is it possible to clean this up any more? I find:<BR>
>><BR>
>> ( (), (Double, Word64) )<BR>
>><BR>
>> a bit odd syntactically, although I understand this is just to fit the type<BR>
>> to the State c'tor so that we don't have to write our own Monad longhand.<BR>
><BR>
> If you have a function which transforms the state, you can lift it<BR>
> into the state monad using "modify".<BR>
><BR>
>> evolveUnderlying :: (Double, Word64) -> (Double, Word64)<BR>
>> evolveUnderlying (stock, state) = ( newStock, newState )<BR>
>> where<BR>
>> newState = ranq1Increment state<BR>
>> newStock = stock * exp ( ( ir - (0.5*(vol*vol)) )*timeStep + (<BR>
>> vol*sqrt(timeStep)*normalFromRngState(state) ) )<BR>
>><BR>
>> getEvolution :: State (Double, Word64) ()<BR>
>> getEvolution = modify evolveUnderlying<BR>
><BR>
> Now, I don't know the full context of what you're doing, but the<BR>
> example you posted isn't really gaining anything from the state monad.<BR>
> Specifically,<BR>
><BR>
> execState (replicateM_ n (modify f))<BR>
> = execState (modify f >> modify f >> ... >> modify f)<BR>
> = execState (modify (f . f . ... . f))<BR>
> = f . f . ... . f<BR>
><BR>
> So you could just write something along these lines,<BR>
><BR>
>> mcSimulate :: Double -> Double -> Word64 -> [Double]<BR>
>> mcSimulate startStock endTime seedForSeed = fst expiryStock : mcSimulate<BR>
>> startStock endTime newSeedForSeed<BR>
>> where<BR>
>> expiryStock = iterate evolveUnderlying (startStock, ranq1Init seedForSeed)<BR>
>> !! truncate (endTime/timeStep)<BR>
>> newSeedForSeed = seedForSeed + 246524<BR>
><BR>
><BR>
> Coming back to your original question, it is possible to work with<BR>
> nested state monad transformers. The trick is to use "lift" to make<BR>
> sure you are working with the appropriate state.<BR>
><BR>
> get :: StateT s1 (State s2) s1<BR>
> put :: s1 -> StateT s1 (State s2) ()<BR>
><BR>
> lift get :: StateT s1 (State s2) s2<BR>
> lift put :: s2 -> StateT s1 (State s2) ()<BR>
><BR>
> A more general piece of advice is to try breaking things into smaller<BR>
> pieces. For example:<BR>
><BR>
> getRanq1 :: MonadState Word64 m => m Word64<BR>
> getRanq1 = do<BR>
> seed <- get<BR>
> put (ranq1Increment seed)<BR>
> return seed<BR>
><BR>
> getEvolution :: StateT Double (State Word64) ()<BR>
> getEvolution = do<BR>
> seed <- lift getRanq1<BR>
> modify $ \stock -> stock * exp ( ( ir - (0.5*(vol*vol)) )*timeStep<BR>
> + ( vol*sqrt(timeStep)*normalFromRngState(seed) ) )<BR>
><BR>
<BR>
_______________________________________________<BR>
Haskell-Cafe mailing list<BR>
Haskell-Cafe@haskell.org<BR>
<a href="http://www.haskell.org/mailman/listinfo/haskell-cafe">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><BR>
<BR>
<BR>
</FONT></SPAN></SPAN></SPAN></FONT></BLOCKQUOTE></BLOCKQUOTE><SPAN STYLE='font-size:11pt'><SPAN STYLE='font-size:14px'>
</BODY>
</HTML>