Problems with input values to a list

Question

I'm quite new at this and I have a problem. I want to read an input and store it at a list, for example:

2 -> number of trees that will be formed after this all
2 -> number of nodes of the first tree
1 -> node 1
2 -> node 2
1 -> number of nodes of the second tree
2 -> node 1

The code below doesn't work as I wanted. That means for example, using the input before:

2 -> number of trees that will be formed after this all
2 -> number of nodes of the first tree
1 -> number of nodes of the second tree
2 -> node 1 of the second tree
1 -> node 1 of the first tree
2 -> node 2 of the first tree 

Output that the program shows for the input above is: 1 2 2

But I expected to have this: 1 2 1 How I can fix this?

let rec inputs number_of_nodes =
  match number_of_nodes with 
  | 0 -> []
  | _ -> let a = read_int() in a :: (inputs (number_of_nodes - 1))


let rec fill_tree_values number_of_trees = 
  match number_of_trees with
  | 0 -> []
  | _ -> let number_of_nodes = read_int() in 
    (inputs number_of_nodes) :: fill_tree_values (number_of_trees - 1)


let number_of_trees = read_int()
let trees = fill_tree_values number_of_trees

let printlist l = List.iter (Printf.printf "%d ") l

let () = List.iter (fun ll -> printlist ll) trees

Answer 1

You wrote:

    (inputs number_of_nodes) :: fill_tree_values (number_of_trees - 1)

but the evaluation order between both operands of :: is unspecified. So it might very well be the case?—?and unless I’m mistaken, it is effectively the case?—?that they are evaluated right-to-left, i.e. fill_tree_values (number_of_trees - 1) is performed before inputs number_of_nodes. So you’re reading inputs in a broken order. You can test this right-to-left behavior:

let _ = print_int 1 :: print_int 2 :: print_int 3 :: []
(* with OCaml 4.12, this prints me "321" *)

You must enforce the evaluation order by rewriting your code as:

    let trees = inputs number_of_nodes in
    trees :: fill_tree_values (number_of_trees - 1)

Note: I believe the evaluation order around :: might change in cutting-edge versions of OCaml, with the introduction of the “tail-call-modulo-constructor” optimisation. In any case, you should not rely on it.

Answer 2

In addition to what Maëlan has written about order of evaluation in his answer, you can achieve this as well by using tail recursion.

For example, a read_ints function that reads n ints.

let read_ints n =
  let rec aux n acc =
    if n = 0 then acc
    else aux (n - 1) (read_int () :: acc)
  in
  aux n [] |> List.rev

The very act of building the accumulator makes order of evaluation explicit.

Of course, that's not where you had a problem, but rather with:

let rec fill_tree_values number_of_trees = 
 match number_of_trees with
 | 0 -> []
 | _ -> let number_of_nodes = read_int() in 
   (inputs number_of_nodes) :: fill_tree_values (number_of_trees - 1)

But we can apply the same strategy and now there's no ambiguous order of evaluation.

let fill_tree_values number_of_trees =
  let rec aux n acc =
    if n = 0 then acc
    else aux (n - 1) (inputs (read_int ()) :: acc)
  in
  aux number_of_trees [] |> List.rev

We could generalize this with a function which takes a function.

let map_times n f =
  let rec aux n' f acc =
    if n' = n then acc
    else let c = f n' in aux (n'+1) f (c :: acc)
  in
  aux 0 f [] |> List.rev

And then if we know we need to read n ints:

let fill_tree_values number_of_trees =
  map_times 
    number_of_trees 
    (fun _ -> 
       let n = read_int () in
       map_times n (fun _ -> read_int ()))

And then if we're really smart, we realize that we could just use List.init to do the exact same thing.

let fill_tree_values number_of_trees =
  List.(
    init number_of_trees (fun _ -> 
      let n = read_int () in
      init n (fun _ -> read_int ())
    )
  )

utop # fill_tree_values 2;;
2
3
4
1
5
- : int list list = [[3; 4]; [5]]