I wrote a function which generates a list of randomized ints
in OCaml
.
let create_shuffled_int_list n =
Random.self_init;
let rec create n' acc =
if n' = 0 then acc
else
create (n'-1) (acc @ [Random.int (n/2)])
in
create n [];;
When I tried to generate 10000
integers, it gives Exception: RangeError: Maximum call stack size exceeded.
error.
However, I believed in the function, I have used tail-recursion
and it should not give stackoverflow
error, right?
Any idea?
From the core library documentation
val append : 'a list -> 'a list -> 'a list Catenate two lists. Same function as the infix operator @. Not tail-recursive (length of the first argument). The @ operator is not tail-recursive either.
So it's not your function that's causing the overflow, it's the @
function. Seeing as you only care about producing a shuffled list, however, there's no reason to be appending things onto the end of lists. Even if the @
operator were tail-recursive1, list append is still O(n). List prepending, however, is O(1). So if you stick your new random numbers on the front of your list, you avoid the overflow (and make your function much much faster):
let create_shuffled_int_list n =
Random.self_init;
let rec create n' acc =
if n' = 0 then acc
else
create (n'-1) (Random.int (n/2) :: acc)
in
create n [];;
If you care about the order (not sure why), then just stick a List.rev on the end:
List.rev (create n []);;
1 As of OCaml 5.1, released September 2023, @
is tail-recursive. Though still not ideal for this use.