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)
views:
90answers:
4
+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
2010-03-13 08:20:56
Yes - I just wanted to know what is the idiomatic construct. Also is that the most efficient?
Fakrudeen
2010-03-13 10:49:14
It would work. Not sure about "most efficient" but will be reasonably efficient. I mean what is simpler than a loop?
Amit Kumar
2010-03-13 13:33:55
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
2010-03-13 14:20:09
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
2010-03-13 11:29:40
+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
2010-03-13 19:59:19