[Haskell-cafe] monte carlo trouble

[Chad Scherrer]

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.
>
>
>