Why this obsession with IO? There should be no IO involved in this, except for getting the initial generator. Using IO just confuses what is going on. -- Lennart On 7/30/07, Cale Gibbard wrote:

On 30/07/07, Chad Scherrer wrote:

...

I'm trying to do something I thought would be pretty simple, but it's giving me trouble.

Given a list, say [1,2,3], I'd like to be able to generate an infinite list of random elements from that list, in this case maybe [1,2,1,3,2,1,3,2,3,1,2,...]. I'm using IO for random purely due to laziness (my own, not Haskell's).

I was thinking the best way to do this might be to first write this function:

randomElts :: [a] -> [IO a] randomElts [] = [] randomElts [x] = repeat (return x) randomElts xs = repeat r where bds = (1, length xs) xArr = listArray bds xs r = do i <- randomRIO bds return (xArr ! i)

Then I should be able to do this in ghci:

...

sequence . take 5 $ randomElts [1,2,3] [*** Exception: stack overflow

Any idea what's going on? I thought laziness (Haskell's, not my own) would save me on this one.

I don't get that result. However, you can't compute an infinite random list in IO without using something like unsafeInterleaveIO. However, you will probably be interested in randoms/randomRs, which take a random generator, and give an infinite list of results.

Using that, we could write something like:

randomElts :: [a] -> IO [a] randomElts [] = return [] randomElts xs = do g <- newStdGen return (map (xArr !) (randomRs bds g)) where bds = (1, length xs) xArr = listArray bds xs

which for a nonempty input list, gives an infinite list of pseudorandom elements of that input list.

- Cale _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

Thanks for your responses. Stefan, I appreciate your taking a step back for me (hard to judge what level of understanding someone is coming from), but the example you gave doesn't contradict my intuition either. I don't consider the output [IO a] a "list of tainted a's", but, as you suggest, a "list of IO actions, each returning an a". I couldn't return an IO [a], since that would force evaluation of an infinite list of random values, so I was using [IO a] as an intermediary, assuming I'd be putting it through something like (sequence . take n) rather than sequence alone. Unfortunately, I can't use your idea of just selecting one, because I don't have any way of knowing in advance how many values I'll need (in my case, that depends on the results of several layers of Map.lookup). Also, I'm using GHC 6.6, so maybe there have been recent fixes that would now allow my idea to work. Cale, that's interesting. I wouldn't have thought this kind of laziness would work in this context. Lennart, I prefer the purely functional approach as well, but I've been bitten several times by laziness causing space leaks in this context. I'm on a bit of a time crunch for this, so I avoided the risk. Sebastian, this seems like a nice abstraction to me, but I don't think it's the same thing statistically. If I'm reading it right, this gives a concatenation of an infinite number of random shuffles of a sequence, rather than sampling with replacement for each value. So shuffles [1,2] g would never return [1,1,...], right? Chad

I was thinking the best way to do this might be to first write this function:

randomElts :: [a] -> [IO a] randomElts [] = [] randomElts [x] = repeat (return x) randomElts xs = repeat r where bds = (1, length xs) xArr = listArray bds xs r = do i <- randomRIO bds return (xArr ! i)

Then I should be able to do this in ghci:

...

sequence . take 5 $ randomElts [1,2,3] [*** Exception: stack overflow

No leak in sight. -- Lennart import Random import Array randomElts :: RandomGen g => g -> [a] -> [a] randomElts _ [] = [] randomElts g xs = map (a!) rs where a = listArray (1, n) xs rs = randomRs (1, n) g n = length xs main = do g <- getStdGen let xs = randomElts g [10,2,42::Int] print $ sum $ take 1000000 xs On 7/31/07, Chad Scherrer wrote:

Thanks for your responses.

Stefan, I appreciate your taking a step back for me (hard to judge what level of understanding someone is coming from), but the example you gave doesn't contradict my intuition either. I don't consider the output [IO a] a "list of tainted a's", but, as you suggest, a "list of IO actions, each returning an a". I couldn't return an IO [a], since that would force evaluation of an infinite list of random values, so I was using [IO a] as an intermediary, assuming I'd be putting it through something like (sequence . take n) rather than sequence alone. Unfortunately, I can't use your idea of just selecting one, because I don't have any way of knowing in advance how many values I'll need (in my case, that depends on the results of several layers of Map.lookup). Also, I'm using GHC 6.6, so maybe there have been recent fixes that would now allow my idea to work.

Cale, that's interesting. I wouldn't have thought this kind of laziness would work in this context.

Lennart, I prefer the purely functional approach as well, but I've been bitten several times by laziness causing space leaks in this context. I'm on a bit of a time crunch for this, so I avoided the risk.

Sebastian, this seems like a nice abstraction to me, but I don't think it's the same thing statistically. If I'm reading it right, this gives a concatenation of an infinite number of random shuffles of a sequence, rather than sampling with replacement for each value. So shuffles [1,2] g would never return [1,1,...], right?

Chad

...

I was thinking the best way to do this might be to first write this function:

randomElts :: [a] -> [IO a] randomElts [] = [] randomElts [x] = repeat (return x) randomElts xs = repeat r where bds = (1, length xs) xArr = listArray bds xs r = do i <- randomRIO bds return (xArr ! i)

Then I should be able to do this in ghci:

...

sequence . take 5 $ randomElts [1,2,3] [*** Exception: stack overflow

---

Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

On Jul 31, 2007, at 16:20 , Chad Scherrer wrote:

calls. I suppose a State' monad, strict in the state, could help here.

You mean Control.Monad.State.Strict ? -- brandon s. allbery [solaris,freebsd,perl,pugs,haskell] allbery@kf8nh.com system administrator [openafs,heimdal,too many hats] allbery@ece.cmu.edu electrical and computer engineering, carnegie mellon university KF8NH

Well, I don't know how many generators you need. But I'm sure you can pass them around in a way that doesn't leak. On 7/31/07, Chad Scherrer wrote:

Ok, that looks good, but what if I need some random values elsewhere in the program? This doesn't return a new generator (and it can't because you never get to the end of the list). Without using IO or ST, you'd have to thread the parameter by hand or use the State monad, right? This is where I was leaking space before.

Actually, this makes me wonder... I think what killed it before was that the state was threaded lazily through the various (= very many) calls. I suppose a State' monad, strict in the state, could help here. I wonder how performance for this would compare with IO or ST. Might have to try that sometime...

Chad

On 7/31/07, Lennart Augustsson wrote:

...

No leak in sight.

-- Lennart

import Random import Array

randomElts :: RandomGen g => g -> [a] -> [a] randomElts _ [] = [] randomElts g xs = map (a!) rs where a = listArray (1, n) xs rs = randomRs (1, n) g n = length xs

main = do g <- getStdGen let xs = randomElts g [10,2,42::Int] print $ sum $ take 1000000 xs

---

Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe