What's the best technique to generate a random-access data structure lazily?

Question

In Haskell, I'd like to generate a list of random integers of undetermined length. (However, less than say 1 million.)

I'm not likely to need all the elements of the list immediately, so I'd like to generate it lazily. However, once generated, I'll need to access elements in the list with random access. So, I assume the best technique would be to copy an infinite list to an array. However, I don't know if arrays can be "interchanged" with lists very easily -- for instance, once I want to generate more items of the list, I want to start where I left off but expand the array.

Anyways, perhaps I should settle for some log(n) tree structure instead of an array? What do you think?

Does Haskell have a tree structure for sequential elements that can be accessed using a list-like API?

Answer 1

If you have a good PRNG, then values which are generated with seeds which are close together should be independent, so you can just choose an initial seed, then each cell i in the array will be prng(seed+i).

This is essentially just using it as a hash function :P

If you do it this way, you don't even really need the array, you can just have a function getRandomValue seed i = prng (seed+i). Whether or not this is better than an array of lazy values will depend on the complexity of your PRNG, but either way you'll get O(1) access.

Answer 2

This seems like it might be useful, but you would need to generate increasingly larger trees as the list gets longer: http://www.codeproject.com/KB/recipes/persistentdatastructures.aspx#RandomAccessLists (it is a log(n) structure, though). Something like http://research.janelia.org/myers/Papers/applicative.stack.pdf might be useful as well, but I don't see off hand how to make it work efficiently (with shared structure) when the list is generated dynamically.

One possible approach would be to use a pseudorandom number generator that allows "leapfrogging," or skipping forward n steps in sub-linear time. One method (that is slow, but works in constant time) is to use a block cipher in counter mode; see http://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator#Designs_based_on_cryptographic_primitives. See http://cs.berkeley.edu/~mhoemmen/cs194/Tutorials/prng.pdf for more information.