Just want choose some random elements of a list and return them in OCaml

Question

I want to choose n distinct random elements in a list l and return them in choose_elements but I have a StackOverFlow error for sufficiently large lists!

I tried to use a tail_recursive function choose_elem_aux in order to do that but I think my condition List.mem is not efficient enough in term of complexity! I do this normally in other programming languages with a boolean mark array which I mark the index of each random number that is generated in true! But I can't do this in OCaml because I can't do multiple instruction into an if or else block! like this:

... else {
mark[r] =true ;
choose_elem_aux l n mark tmp ;
} ...


let choose l = 
  nth l (Random.int (List.length l)) ;;
  
let rec choose_elem_aux l n tmp =
  if n=0 then tmp
  else
    let r=choose l in 
    if List.mem r tmp then
      choose_elem_aux l n tmp 
    else 
      choose_elem_aux l (n-1) (r::tmp) ;;

let rec choose_elements l n = 
  choose_elem_aux l n [] ;;

StackOverflow for large list like:

choose_elements [1...10_000] 7 ;;

Answer 1

First of all, ocaml does allow you to write several statements in an if then else, it's just not written as in C-like languages.

if condition then begin
  instruction1 ;
  instruction 2 ;
  (* ... *)
end
else begin
  (* ... *)
end

The begin (* ... *) end block works the same as parentheses, so you can also just parenthesise:

if condition then (
  instruction1 ;
  instruction 2 ;
  (* ... *)
)
else (
  (* ... *)
)

So you can do your optimisation just fine.

What happens here is that when writing if b then t else f in ocaml, you are building a value of type T if t : T and f : T. You can for instance write if b then 0 else 1 or if b then "Hello" else "Goodbye". It also works with the unit type (the type of most instructions):

if b then instruction1 else instruction2

The semicolon operator allows to do two instructions sequentially:

(;) : unit -> unit -> unit

Note that it is not the same as in most language where it marks the end of an instruction.

The problem is that when you write

if b then instruction1 else instruction2 ; instruction 3

it is not understood as

if b then instruction1 else (instruction2 ; instruction 3)

as you wished, but as

(if b then instruction1 else instruction2) ; instruction 3

which also makes sense because the if expression also has type unit.