具有数据类型树的 OCaml 函数

Question

我们给出一棵包含两种类型元素的树。它是用以下数据结构定义的。

type ( 'a , 'b ) tree =
   Empty
   | Vertexa of 'a * ( 'a , 'b ) tree list
   | Vertexb of 'b * ( 'a , 'b ) tree list

编写一个函数 split: ('a,'b) tree -> 'a list * 'b list，将 'a 类型的所有元素保存到第一个列表中，将 'b 类型的所有元素保存到第二个列表中。

我有一个递归地执行此操作的想法，但我有点坚持这一点。我会附上我的尝试，即使它根本不起作用:/

let rec one drevo_list=
    match drevo_list with
   | [Empty]->Empty 
   | Empty::tl -> one tl
   | Vertexa(a,b)::tl -> Vertexa(a,b@tl) 
   | Vertexb(a,b)::tl -> Vertexb(a,b@tl) 

该函数将列表变成树。我需要它来进行递归，因为 Vertexa 或 Vertexb 中的第二个参数是一个列表。这有效 但递归部分却没有。

let rec split drevo=
   match drevo with
   | Empty -> [],[]
   | Vertexa(a,b)-> split (one b)
   | Vertexb(a,b)-> split (one b)

这部分不起作用，我不知道如何完成它。有人知道如何完成这个吗？

Answer 1

您不需要

drevo_list

功能来解决这个问题。它实际上会把你引向错误的方向。

您需要使用

List.map

将分割应用于树列表。您将获得

('a list * 'b list) list

类型的值。现在您需要一个辅助函数

concat_pairs

，它将将此值展平为一对类型

'a list * 'b list

（参见标准

concat

函数）。要实现此功能，您可以使用

List.fold_left

。其余的都是微不足道的。

注意，这当然是一个贪婪的解决方案。当你完成它后，你可能会尝试找到更好的解决方案，即更高效且尾递归。

Answer 2

这个函数至少有两部分比较难写：

1. 返回一对列表的函数需要在每个递归步骤中打包和解包其返回值，例如辅助函数、match 语句或 let 绑定。一种方法是编写一个函数，将一个元素插入到一对内的列表中：

   let insertA a (xs, ys) = (a::xs, ys)
   let insertB b (xs, ys) = (xs, b::ys)
   

2. 在树类型和嵌入列表类型上递归的函数需要两种递归模式的组合。这可以使用一组相互递归函数或使用列表的高阶组合器来解决。以下是使用前一种策略的解决方案的概述：

   let rec split s =
       match s with
     | Empty -> ([], [])
     | Vertexa (a, ts) -> (* if we had just one t: insertA a (split t) *)
     | Vertexb (a, ts) -> (* if we had just one t: insertB b (split t) *)
   

   因此您需要一个函数

   splitMany : ('a, 'b) tree list -> ('a list, 'b list)

   可以为每个单独的树回调

   split

   。

   and rec splitMany ts =
       match ts with
     | [] -> ([], [])
     | (t:ts') -> (* merge (split t) with (splitMany ts') *)
   

   对于高阶函数方法，您可以通过让函数将自身传递给一组高阶函数来避免显式相互递归，从而不会将其纠缠在高阶函数的实现中：

   let rec split s =
       match s with
     | Empty -> [],[]
     | Vertexa (a, ts) -> insertA (concat_pairs (map split ts))
     | Vertexb (a, ts) -> insertB (concat_pairs (map split ts))
   

   其中

   concat_pairs

   是ivg的发明。

Answer 3

这种类型的 n 叉树问题的解决方案是维护一个节点列表作为函数的参数进行处理，以及一个累加器，并随时填充或使用该节点列表。这样您就只需担心一次处理一个节点。

这还有尾递归的优点。

let rec split tree to_process (acca, accb as acc) =
  match tree, to_process with
  | Empty,              []    -> List.(rev acca, rev accb)
  | Empty,              x::xs -> split x xs acc
  | Vertexa (v, []),    []    -> List.(rev (v::acca), rev accb)
  | Vertexb (v, []),    []    -> List.(rev acca, rev (v::accb))
  | Vertexa (v, y::ys), []    -> split y ys (v::acca, accb)
  | Vertexb (v, y::ys), []    -> split y ys (acca, v::accb) 
  | Vertexa (v, lst),   x::xs -> split x (xs @ lst) (v::acca, accb)
  | Vertexb (v, lst),   x::xs -> split x (xs @ lst) (acca, v::accb)

# split (Vertexa (4, [Vertexb (3, [Vertexa (5, [Empty; Empty])]); Vertexa (1, [])])) [] ([], []);;
- : int list * int list = ([4; 1; 5], [3])

split (Vertexa (4, [Vertexb (3, [Vertexa (5, [Empty; Empty])]); Vertexa (1, [])])) [] ([], [])
split (Vertexb (3, [Vertexa (5, [Empty; Empty])])) [Vertexa (1, [])] (4::[], []) 
split (Vertexa (1, [])) [Vertexa (5, [Empty; Empty])] (4::[], 3::[])
split (Vertexa (5, [Empty; Empty]) [] (1::4::[], 3::[])
split Empty [Empty] (5::1::4::[], 3::[])
split Empty [] (5::1::4::[], 3::[])
([4; 1; 5]; [3])