列表输入值的问题

Question

我对此很陌生，但遇到了问题。我想读取输入并将其存储在列表中，例如：

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

下面的代码不符合我的要求。这意味着例如，使用之前的输入：

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

程序针对上述输入显示的输出是： 1 2 2

但我希望有这个： 1 2 1 我该如何解决这个问题？

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

您写道：

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

但 :: 的两个操作数之间的求值顺序未指定。所以很可能是这种情况——除非我弄错了，实际上是情况——它们被评估 right-to-left，即 fill_tree_values (number_of_trees - 1) 被执行在 inputs number_of_nodes 之前。因此，您正在以错误的顺序读取输入。您可以测试此 right-to-left 行为：

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

您必须通过将代码重写为以下方式来执行评估顺序：

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

注意：我相信 :: 周围的评估顺序可能会在 cutting-edge 版本的 OCaml 中发生变化，引入“tail-call-modulo-constructor”优化。无论如何，你不应该依赖它。

Answer 2

除了 Maëlan 在他的回答中写的关于评估顺序的内容，您也可以通过使用尾递归来实现。

例如，读取 n 个整数的 read_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

构建累加器的行为使得计算顺序明确。

当然，这不是您遇到问题的地方，而是：

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

我们可以用一个带有函数的函数来概括它。

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

然后如果我们知道我们需要读取 n 整数：

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

然后，如果我们真的很聪明，就会意识到我们可以使用 List.init 来做完全相同的事情。

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]]

列表输入值的问题

Problems with input values to a list

ocaml

list