<br><font size=2 face="sans-serif">&gt;&gt; </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 &quot;pure&quot; 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 &quot;pure&quot; 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>&quot;Chad Scherrer&quot;
&lt;chad.scherrer@gmail.com&gt;</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">&quot;Paul Johnson&quot; &lt;paul@cogito.org.uk&gt;,
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 &nbsp;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 &lt;paul@cogito.org.uk&gt; wrote:<br>
&gt; Chad Scherrer wrote:<br>
&gt; &gt; There's a problem I've been struggling with for a long time...<br>
&gt; &gt;<br>
&gt; &gt; I need to build a function<br>
&gt; &gt; buildSample :: [A] -&gt; State StdGen [(A,B,C)]<br>
&gt; &gt;<br>
&gt; &gt; given lookup functions<br>
&gt; &gt; f :: A -&gt; [B]<br>
&gt; &gt; g :: A -&gt; [C]<br>
&gt; &gt;<br>
&gt; &gt; The idea is to first draw randomly form the [A], then apply each<br>
&gt; &gt; lookup function and draw randomly from the result of each.<br>
&gt; &gt;<br>
&gt; I don't understand why this returns a list of triples instead of a<br>
&gt; single triple. &nbsp;Your description below seems to imply the latter.<br>
&gt;<br>
&gt; You should probably look at the &quot;Gen&quot; monad in Test.QuickCheck,
which is<br>
&gt; basically a nice implementation of what you are doing with &quot;State<br>
&gt; StdGen&quot; below. &nbsp;Its &quot;elements&quot; function gets a
single random element,<br>
&gt; and you can combine it with replicateM to get a list of defined length.<br>
&gt;<br>
&gt; (BTW, are you sure want multiple random samples rather than a shuffle?<br>
&gt; A shuffle has each element exactly once whereas multiple random samples<br>
&gt; can pick any element an arbitrary number of times. &nbsp;I ask because<br>
&gt; shuffles are a more common requirement. &nbsp;For the code below I'll
assume<br>
&gt; you meant what you said.)<br>
&gt;<br>
&gt; Using Test.QuickCheck I think you want something like this (which
I have<br>
&gt; not tested):<br>
&gt;<br>
&gt; &nbsp; &nbsp;buildSample :: [A] -&gt; Gen (A,B,C)<br>
&gt; &nbsp; &nbsp;buildSample xs = do<br>
&gt; &nbsp; &nbsp; &nbsp; x &lt;- elements xs<br>
&gt; &nbsp; &nbsp; &nbsp; f1 &lt;- elements $ f x<br>
&gt; &nbsp; &nbsp; &nbsp; g1 &lt;- elements $ g x<br>
&gt; &nbsp; &nbsp; &nbsp; return<br>
&gt;<br>
&gt; If you want n such samples then I would suggest<br>
&gt;<br>
&gt; &nbsp; &nbsp;samples &lt;- replicateM n $ buildSample xs<br>
&gt; &gt; It's actually slightly more complicated than this, since for
the real<br>
&gt; &gt; problem I start with type [[A]], and want to map buildSample
over<br>
&gt; &gt; these, and sample from the results.<br>
&gt; &gt;<br>
&gt; &gt; There seem to be so many ways to deal with random numbers in
Haskell.<br>
&gt; &gt;<br>
&gt; Indeed.<br>
&gt; &gt; After some false starts, I ended up doing something like<br>
&gt; &gt;<br>
&gt; &gt; sample :: [a] -&gt; State StdGen [a]<br>
&gt; &gt; sample [] = return []<br>
&gt; &gt; sample xs = do<br>
&gt; &gt; &nbsp; g &lt;- get<br>
&gt; &gt; &nbsp; let (g', g'') = split g<br>
&gt; &gt; &nbsp; &nbsp; &nbsp; bds = (1, length xs)<br>
&gt; &gt; &nbsp; &nbsp; &nbsp; xArr = listArray bds xs<br>
&gt; &gt; &nbsp; put g''<br>
&gt; &gt; &nbsp; return . map (xArr !) $ randomRs bds g'<br>
&gt; &gt;<br>
&gt; Not bad, although you could instead have a sample function that returns<br>
&gt; a single element and then use replicateM to get a list.<br>
&gt; &gt; buildSample xs = sample $ do<br>
&gt; &gt; &nbsp; x &lt;- xs<br>
&gt; &gt; &nbsp; y &lt;- f x<br>
&gt; &gt; &nbsp; z &lt;- g x<br>
&gt; &gt; &nbsp; return (x,y,z)<br>
&gt; &gt;<br>
&gt; &gt; This is really bad, since it builds a huge array of all the<br>
&gt; &gt; possibilities and then draws from that. Memory is way leaky right
now.<br>
&gt; &gt; I'd like to be able to just have it apply the lookup functions
as<br>
&gt; &gt; needed.<br>
&gt; &gt;<br>
&gt; &gt; Also, I'm still using GHC 6.6, so I don't have<br>
&gt; &gt; Control.Monad.State.Strict. Not sure how much difference this
makes,<br>
&gt; &gt; but I guess I could just copy the source for that module if I
need to.<br>
&gt; &gt;<br>
&gt; Strictness won't help. &nbsp;In fact you would be better with laziness
if<br>
&gt; that were possible (which it isn't here). &nbsp;The entire array has
to be<br>
&gt; constructed before you can look up any elements in it. &nbsp;That
forces the<br>
&gt; entire computation. &nbsp; But compare your implementation of buildSample
to<br>
&gt; mine.<br>
&gt;<br>
&gt; Paul.<br>
&gt;<br>
<br>
<br>
-- <br>
<br>
Chad Scherrer<br>
<br>
&quot;Time flies like an arrow; fruit flies like a banana&quot; -- 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>