Problems with input values to a list-CodePudding

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

CodePudding user response：

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.

CodePudding user response：

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