[Haskell-cafe] infinite list of random elements

[Stefan O'Rear]

On Mon, Jul 30, 2007 at 02:40:35PM -0700, 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.

The code you posted works fine for me (GHCi 6.7.20070712).

However, it's pretty bad style in a way that suggests a misunderstanding
of IO.  A value of type IO t is not a "tainted t", it's an "action that
returns t".  So, in general:

do let xv = randomRIO (1,20)
   a <- xv
   b <- xv
   return (a == b)

will normally return *False*.  Why?  Because, while the same action is
used, it doesn't always return the same value!  In general, when you see
a type of the form [IO a] or Maybe (IO a) or IO a -> b, ask yourself if
that's what you really want.  (Sometimes it is, and the flexibility of
having IO anywhere is very powerful).

A better way to write randomElts is:

randomElt :: [a] -> IO a
randomElt xs = do ix <- randomRIO bds
                  return (arr ! i)
  where arr = listArray bds xs
        bds = (1, length xs)

randomElts :: Int -> [a] -> IO [a]
randomElts n xs = replicateM n (randomElt xs)  -- uses replicateM from Control.Monad

Sadly, it's very hard to "just return an infinite list" in IO.  it can
be done in dedicated monads, however.

Stefan
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20070730/6436a3ef/attachment.bin