0

我有以下树结构：

type 'a tree =
    | Function of string * 'a tree list  (* function name and arguments *)
    | Terminal of 'a

我使用这个树结构来构造一个抽象语法树：

type atoms =
    | Int of int
    | Bool of bool

let t1 = Function ("+", [Function ("*", [Terminal (Int 5);
                                         Terminal (Int 6)]);
                         Function ("sqrt", [Terminal (Int 3)])])

let t2 = Function ("-", [Terminal (Int 4); Terminal (Int 2)])

的树表示t1：

t1 的树表示

的树表示t2：

t2 的树表示

目标：在指定的索引位置替换其中的一个子树t1。索引位置从根节点的 0 开始，并且是深度优先的。在上图中，我用索引标记了所有节点以显示这一点。t2t1

例如，replace_subtree t1 4 t2将索引 4 处的子树替换为t1，t2得到此树：

结果的树表示

Function ("+", [Function ("*", [Terminal (Int 5);
                                Terminal (Int 6)]);
                Function ("-", [Terminal (Int 4);
                                Terminal (Int 2)])])

这本质上是基于树的遗传编程中的交叉操作。

如何replace_subtree在 OCaml 中实现？

我强烈希望使用纯粹的功能解决方案。

请注意，这个问题类似于如何用指定索引处的另一棵树替换部分树？，除了这个问题中的编程语言是OCaml而不是Scheme/Racket。我在理解 Scheme/Racket 时遇到了一些麻烦，所以我正在寻找 OCaml 解决方案。

4

3 回答 3

2

假设您有一个递归函数dfs，它访问了树的每个节点，其中一个参数是节点的索引号。

现在重写此函数以返回一个附加值，该值是节点下方子树的副本。即，它递归地访问节点的子树（接收子树的副本）并构造一个新节点作为它们的父节点。

现在向函数添加两个参数，索引和所需的替换。当达到所需的索引时，该函数返回替换而不是节点的副本。

（由于这看起来像是可能的作业，我不想提供代码。）

于 2022-02-11T06:18:19.087 回答
0

不确定它是否比您提出的解决方案更好...

我使用的递归函数比你少：

let replace to_replace index replacement =
  let rec dfs i tree =
    if i = index then (replacement, i + 1) (* we can replace *)
    else if i > index then (tree, i) (* we already replaced *)
    else
      match tree with
      | Terminal _ -> (tree, i + 1)
      | Function (n, children) ->
          let new_i, new_children = iter_children (i + 1) children in
          (Function (n, new_children), new_i)
  and iter_children i = function
    | [] -> (i, [])
    | child :: children ->
        let new_child, new_i = bfs i child in
        if new_i = index + 1 then (new_i + 1, new_child :: children)
          (* +1 to stop the bfs after appending the children to the Function node *)
        else
          let last_i, last_children = iter_children new_i children in
          (last_i, new_child :: last_children)
  in
  fst @@ bfs 0 to_replace
于 2022-02-11T18:55:21.927 回答
0

我写了一个解决方案：

let rec replace_subtree' start_index tree replacement_index replacement
        : (int * 'a tree) =
    (* Returns (max_index, new_tree), where max_index = start_index + number of
       nodes in new_tree - 1, and where the replacement is counted as a single
       node. *)
    if start_index = replacement_index then
        (start_index, replacement)
    else
        match tree with
        | Function (name, args) ->
            (* (start_index + 1) to account for this function node itself. *)
            let (max_index, new_args) = replace_subtree_args (start_index + 1)
                                                             args
                                                             replacement_index
                                                             replacement in
            (max_index, Function (name, new_args))
        | Terminal _ ->
            (start_index, tree)

and replace_subtree_args arg_index args replacement_index replacement
        : (int * 'a tree list) =
    (* `arg_index` is the index of the first item in `args` (note that `args`
       could be empty, however).
       Returns (max_index, replaced_args), where max_index = arg_index +
       number of nodes in all transformed args - 1, and where the replacement is
       counted as a single node. *)
    let rec f arg_index args acc =
        match args with
        | [] -> (arg_index - 1, List.rev acc)
        | arg::rest_args ->
            let (max_index, arg_result) = replace_subtree' arg_index
                                                           arg
                                                           replacement_index
                                                           replacement in
            f (max_index + 1) rest_args (arg_result::acc)
    in
    f arg_index args []

let replace_subtree = replace_subtree' 0

示例用法：

let string_of_terminal = function
    | Int x -> string_of_int x
    | Bool b -> string_of_bool b

let rec string_of_tree = function
    | Function (name, args) ->
        "(" ^
        String.concat " " (name::(List.map string_of_tree args)) ^
        ")"
    | Terminal x -> string_of_terminal x

let () =
    List.iter (fun n ->
                  let (max_index, new_tree) = replace_subtree t1 n t2 in
                  print_string ("Index " ^ (string_of_int n) ^ ":  ");
                  print_endline (string_of_tree new_tree))
              (List.init 8 Fun.id)

结果：

Index 0:  (- 4 2)
Index 1:  (+ (- 4 2) (sqrt 3))
Index 2:  (+ (* (- 4 2) 6) (sqrt 3))
Index 3:  (+ (* 5 (- 4 2)) (sqrt 3))
Index 4:  (+ (* 5 6) (- 4 2))         ; <- Here.
Index 5:  (+ (* 5 6) (sqrt (- 4 2)))
Index 6:  (+ (* 5 6) (sqrt 3))
Index 7:  (+ (* 5 6) (sqrt 3))

更好的解决方案是最受欢迎的。

于 2022-02-11T09:53:21.480 回答