functional-programmingocaml

Why did I still get stackoverflow even if I used tail-recursion in OCaml?


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?


Solution

  • 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.