<br><font size=2 face="sans-serif">>> </font><tt><font size=2>I've
seen PFP, but I don't see where that would help here. I'd still end up
with an enormous list of tuples. </font></tt>
<br>
<br><font size=2 face="sans-serif">I'm not sure I understand what you need,
but did you read the bits about replacing a "pure" state expansion
(all the possibile states) with an approximation using random/io ? the
approximation of course used much less resources (orders of orders of magnitude
:) ) , the more time the random process had to evolve the better the approximation
matched the "pure" calculation. very wonderful.</font>
<br>
<br><font size=2 face="sans-serif">thomas.</font>
<br>
<br>
<br>
<br>
<table width=100%>
<tr valign=top>
<td width=40%><font size=1 face="sans-serif"><b>"Chad Scherrer"
<chad.scherrer@gmail.com></b> </font>
<p><font size=1 face="sans-serif">08/15/2007 03:05 PM</font>
<td width=59%>
<table width=100%>
<tr valign=top>
<td>
<div align=right><font size=1 face="sans-serif">To</font></div>
<td><font size=1 face="sans-serif">"Paul Johnson" <paul@cogito.org.uk>,
Thomas Hartman/ext/dbcom@DBAmericas</font>
<tr valign=top>
<td>
<div align=right><font size=1 face="sans-serif">cc</font></div>
<td><font size=1 face="sans-serif">haskell-cafe@haskell.org</font>
<tr valign=top>
<td>
<div align=right><font size=1 face="sans-serif">Subject</font></div>
<td><font size=1 face="sans-serif">Re: [Haskell-cafe] monte carlo trouble</font></table>
<br>
<table>
<tr valign=top>
<td>
<td></table>
<br></table>
<br>
<br>
<br><tt><font size=2>Thanks for your replies.<br>
<br>
I actually starting out returning a single element instead. But a<br>
given lookup might return [], and the only way I could think of to<br>
handle it in (State StdGen a) would be to fail in the monad. But<br>
that's not really the effect I want - I'd rather have it ignore that<br>
element. Another option was to wrap with Maybe, but then since I<br>
really want a sequence of them anyway, I decided to just wrap in
a<br>
List instead. Is there a way Maybe would work out better?<br>
<br>
I've seen PFP, but I don't see where that would help here. I'd still<br>
end up with an enormous list of tuples. This could be generated<br>
lazily, but sampling with replacement (yes I want this, not a shuffle)<br>
would require forcing the whole list anyway, wouldn't it? Using my<br>
approach, even asking ghci for the length of the list ran for 30+<br>
minutes.<br>
<br>
If there's a way to lazily sample with replacement from a list without<br>
even requiring the length of the list to be known in advance, that<br>
could lead to a solution.<br>
<br>
Thanks,<br>
Chad<br>
<br>
On 8/15/07, Paul Johnson <paul@cogito.org.uk> wrote:<br>
> Chad Scherrer wrote:<br>
> > There's a problem I've been struggling with for a long time...<br>
> ><br>
> > I need to build a function<br>
> > buildSample :: [A] -> State StdGen [(A,B,C)]<br>
> ><br>
> > given lookup functions<br>
> > f :: A -> [B]<br>
> > g :: A -> [C]<br>
> ><br>
> > The idea is to first draw randomly form the [A], then apply each<br>
> > lookup function and draw randomly from the result of each.<br>
> ><br>
> I don't understand why this returns a list of triples instead of a<br>
> single triple. Your description below seems to imply the latter.<br>
><br>
> You should probably look at the "Gen" monad in Test.QuickCheck,
which is<br>
> basically a nice implementation of what you are doing with "State<br>
> StdGen" below. Its "elements" function gets a
single random element,<br>
> and you can combine it with replicateM to get a list of defined length.<br>
><br>
> (BTW, are you sure want multiple random samples rather than a shuffle?<br>
> A shuffle has each element exactly once whereas multiple random samples<br>
> can pick any element an arbitrary number of times. I ask because<br>
> shuffles are a more common requirement. For the code below I'll
assume<br>
> you meant what you said.)<br>
><br>
> Using Test.QuickCheck I think you want something like this (which
I have<br>
> not tested):<br>
><br>
> buildSample :: [A] -> Gen (A,B,C)<br>
> buildSample xs = do<br>
> x <- elements xs<br>
> f1 <- elements $ f x<br>
> g1 <- elements $ g x<br>
> return<br>
><br>
> If you want n such samples then I would suggest<br>
><br>
> samples <- replicateM n $ buildSample xs<br>
> > It's actually slightly more complicated than this, since for
the real<br>
> > problem I start with type [[A]], and want to map buildSample
over<br>
> > these, and sample from the results.<br>
> ><br>
> > There seem to be so many ways to deal with random numbers in
Haskell.<br>
> ><br>
> Indeed.<br>
> > After some false starts, I ended up doing something like<br>
> ><br>
> > sample :: [a] -> State StdGen [a]<br>
> > sample [] = return []<br>
> > sample xs = do<br>
> > g <- get<br>
> > let (g', g'') = split g<br>
> > bds = (1, length xs)<br>
> > xArr = listArray bds xs<br>
> > put g''<br>
> > return . map (xArr !) $ randomRs bds g'<br>
> ><br>
> Not bad, although you could instead have a sample function that returns<br>
> a single element and then use replicateM to get a list.<br>
> > buildSample xs = sample $ do<br>
> > x <- xs<br>
> > y <- f x<br>
> > z <- g x<br>
> > return (x,y,z)<br>
> ><br>
> > This is really bad, since it builds a huge array of all the<br>
> > possibilities and then draws from that. Memory is way leaky right
now.<br>
> > I'd like to be able to just have it apply the lookup functions
as<br>
> > needed.<br>
> ><br>
> > Also, I'm still using GHC 6.6, so I don't have<br>
> > Control.Monad.State.Strict. Not sure how much difference this
makes,<br>
> > but I guess I could just copy the source for that module if I
need to.<br>
> ><br>
> Strictness won't help. In fact you would be better with laziness
if<br>
> that were possible (which it isn't here). The entire array has
to be<br>
> constructed before you can look up any elements in it. That
forces the<br>
> entire computation. But compare your implementation of buildSample
to<br>
> mine.<br>
><br>
> Paul.<br>
><br>
<br>
<br>
-- <br>
<br>
Chad Scherrer<br>
<br>
"Time flies like an arrow; fruit flies like a banana" -- Groucho
Marx<br>
</font></tt>
<br>
<br>
<span style="font-family:sans-serif,helvetica; font-size:10pt; color:#000000">---</span><br>
<br>
<span style="font-family:sans-serif,helvetica; font-size:10pt; color:#000000">This e-mail may contain confidential and/or privileged information. If you </span><br>
<span style="font-family:sans-serif,helvetica; font-size:10pt; color:#000000">are not the intended recipient (or have received this e-mail in error) </span><br>
<span style="font-family:sans-serif,helvetica; font-size:10pt; color:#000000">please notify the sender immediately and destroy this e-mail. Any </span><br>
<span style="font-family:sans-serif,helvetica; font-size:10pt; color:#000000">unauthorized copying, disclosure or distribution of the material in this </span><br>
<span style="font-family:sans-serif,helvetica; font-size:10pt; color:#000000">e-mail is strictly forbidden.</span><br>