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

I finally decided to actually solve the problem, and I'm sorry to say I was on the wrong track. ListT won't do it on its own: you actually need a custom monad that does the random pick in the bind operation. Attached are a module to solve the problem and a Main module that tests it. I hope this helps. Paul.
participants (2)
-
Chad Scherrer
-
Paul Johnson