[Haskell-cafe] monte carlo trouble
Chad Scherrer
chad.scherrer at gmail.com
Thu Aug 16 15:30:47 EDT 2007
I'm using ListT now, trying to do this:
type Sample a = ListT (State StdGen) a
randomStreamR :: (RandomGen g, Random a) => (a,a) -> g -> ([a], g)
randomStreamR bds g =(randomRs bds g1, g2)
where (g1,g2) = split g
sample :: [a] -> Sample a
sample [] = ListT (State f)
where f s = case next s of (_,s') -> ([],s')
sample xs = do
let bds = (1, length xs)
xArr = listArray bds xs
i <- ListT . State $ randomStreamR bds
return $ (xArr ! i)
-- Simple example, for testing
main = mapM_ print . flip evalState (mkStdGen 1) . runListT $ do
x <- sample [1..100]
y <- sample [1..x]
return (x,y)
The abstraction seems much better now, but even the simple little
example blows up in memory. Here's a snippet from profiling with
-auto-all -caf-all (after I interrupted it):
CAF:lvl4 Main 261 1
0.0 0.0 100.0 100.0
main Main 273 0
0.0 0.0 100.0 100.0
sample Main 274 1
100.0 100.0 100.0 100.0
randomStreamR Main 276 1
0.0 0.0 0.0 0.0
I'm wondering if the bind for ListT is still effectively building
every possibility behind the scenes, and sampling from that. I could
redo the Sample monad by hand, if that could be the problem, but I'm
not sure what changes would need to be made. Or maybe it's building
lots of different arrays and holding them for too long from the GC. Or
maybe it's a strictness/laziness issue I'm missing. Still not so sure
when I need case vs let/where.
How would you guys going about tracking down the problem?
Thanks,
Chad
On 8/15/07, Paul Johnson <paul at cogito.org.uk> wrote:
> Chad Scherrer wrote:
> > Thanks for your replies.
> >
> > I actually starting out returning a single element instead. But a
> > given lookup might return [], and the only way I could think of to
> > handle it in (State StdGen a) would be to fail in the monad. But
> > that's not really the effect I want - I'd rather have it ignore that
> > element. Another option was to wrap with Maybe, but then since I
> > really want a sequence of them anyway, I decided to just wrap in a
> > List instead. Is there a way Maybe would work out better?
> Ahh. How about using ListT Gen then? That (if I've got it the right
> way round) works like the list monad (giving you non-determinism), but
> has your random number generator embedded as well. Take a look at "All
> About Monads" at http://www.haskell.org/all_about_monads/html/. Each
> action in the monad may use a random number and produce zero or more
> results.
>
> Paul.
>
>
>
More information about the Haskell-Cafe
mailing list