tags:

views:

90

answers:

4

How to efficiently generate a list of million random elements in scheme? The following code hits maximum recursion depth with 0.1 million itself.

(unfold (lambda(x)(= x 1000000)) (lambda(x)(random 1000)) (lambda(x)(+ x 1)) 0)
+3  A: 

I don't know much scheme but couldn't you just use tail-recursion (which is really just looping) instead of unfold (or any other higher-order function)?

Pessimist
Yes - I just wanted to know what is the idiomatic construct. Also is that the most efficient?
Fakrudeen
+1  A: 

Use the do-loop-construct as described here.

Amit Kumar
Thanks! Please see my comment to Pessimist.
Fakrudeen
It would work. Not sure about "most efficient" but will be reasonably efficient. I mean what is simpler than a loop?
Amit Kumar
Function calls: You don't need to add loops to your language if you have `apply`. Scheme's `do` is added as a concession to usability but I believe is still defined in terms of tail-recursive calls. So, loops: efficient but not idiomatic.
Nathan Sanders
A: 

Some one correct me if I am wrong but the Fakrudeen's code should end up being optimized away since it is tail recursive. Or it should be with a proper implementation of unfold. It should never reach a maximum recursion depth.

What version of scheme are you using Fakrudeen? DrScheme does not choke on a mere million random numbers.

Davorak
I am using MIT scheme - 7.7.90.+
Fakrudeen
+2  A: 

It really depends on the system you're using, but here's a common way to do that in plain scheme:

(let loop ([n 1000000] [r '()])
  (if (zero? n)
    r
    (loop (- n 1) (cons (random 1000) r))))

One note about running this code as is: if you just type it into a REPL, it will lead to printing the resulting list, and that will usually involve using much more memory than the list holds. So it's better to do something like

(define l ...same...)

There are many other tools that can be used to varying degrees of convenience. unfold is one of them, and another is for loops as can be found in PLT Scheme:

(for/list ([i (in-range 1000000)]) (random 1000))
Eli Barzilay