在 OCaml 中展平嵌套列表

Question

我正在做 OCaml 练习的问题 7。它基本上要求给出定义的嵌套列表：

type 'a node =
  | One of 'a 
  | Many of 'a node list

编写一个函数

flatten

将其展平：

assert (
  flatten [ One "a"; Many [ One "b"; Many [ One "c"; One "d" ]; One "e" ] ]
  = [ "a"; "b"; "c"; "d"; "e" ])

网站提供的解决方案如下：

let flatten list =
  let rec aux acc = function
    | [] -> acc
    | One x :: t -> aux (x :: acc) t
    | Many l :: t -> aux (aux acc l) t
  in
  List.rev (aux [] list)
;;

我想知道为什么他们这样做

x :: acc

然后反转列表而不是

acc @ [x]

这样可以避免最后需要反转列表？

Answer 1

@

如何运作？好吧，让我们定义一下。

let rec (@) lst1 lst2 =
  match lst1 with 
  | [] -> lst2
  | x::xs -> x :: (xs @ lst2)

因此，为了将一个列表附加到另一个列表，我们必须迭代第一个列表的所有。如果我们在循环中执行此操作，随着第一个列表变得更长，到达它的末尾需要更长的时间。在大 O 表示法中，这具有 O(n^2) 或“二次”性能。适合小样本量，但适合大样本量。

但是，

::

会在恒定时间内发生。无论列表有多大，将值添加到列表前面总是需要相同的时间。如果我们在循环中执行此操作，我们将获得 O(n) 或“线性”性能。

反转列表也可以在线性时间内进行。运行two线性时间操作的成本是否昂贵？当然，运行 one 更有效，但考虑两次 n 与 n 的平方：

n	2n	n^2
0	0	0
1	2	1
2	4	4
3	6	8
4	8	16
100	200	10,000
10,000	20,000	100,000,000
1,000,000	2,000,000	1,000,000,000,000

附加说明：利用

flatten

的 OP 所示的

::

的实现不是尾递归的。以下是：

let flatten lst =
  let rec aux lst to_process acc =
    match lst, to_process with
    | [], [] -> acc
    | [], _ -> aux to_process [] acc
    | (One v)::xs, _ -> aux xs to_process (v :: acc)
    | (Many lst')::xs, _ -> aux lst' (xs @ to_process) acc
  in
  List.rev @@ aux lst [] [] 

评估样本数据后：

flatten [One "a"; Many [One "b"; Many [One "c"; One "d"]; One "e"]]
aux [One "a"; Many [One "b"; Many [One "c"; One "d"]; One "e"]] []        []
aux [Many [One "b"; Many [One "c"; One "d"]; One "e"]]          []        ["a"]
aux [One "b"; Many [ One "c"; One "d" ]; One "e" ]              []        ["a"]
aux [Many [ One "c"; One "d"]; One "e"]                         []        ["b"; "a"]
aux [One "c"; One "d"]                                          [One "e"] ["b"; "a"]
aux [One "d"]                                                   [One "e"] ["c"; "b"; "a"]
aux [One "e"]                                                   []        ["d"; "c"; "b"; "a"]
aux []                                                          []        ["e"; "d"; "c"; "b"; "a"]
List.rev ["e"; "d"; "c"; "b"; "a"]
["a"; "b"; "c"; "d"; "e"]