functional-programming - 生成只有 3 个值和 2 个运算符的所有高度为 n 的树

Question

我有这种类型的树：

type op = Add | Mult ;;

type tree =
  | Value of int
  | Node of tree * op * tree
;;

它是一个语法二叉树。这意味着每个节点都是一个运算符，每个叶子代表一个数字。在这里我需要以 3 为模工作，所以我的值是[0;1;2].

例如，表达式let e1 = Node(Node(Value 1,Add,Value 2),Add,Value 2) in表示以下表达式：((1+2)+2)。

现在我需要创建一个函数generate_height : int n -> tree list来返回所有可能的高度为 n 的树。

一点绘图可以帮助：

我最初的想法是生成所有空树（我们不关心叶子中的值，我们只是将它们设置为 0，但我们需要所有节点的组合）

let generate_empty n =

  let rec gen_rec n op =
    match n with 
    | 0 -> Value 0
    | _ -> Node(gen_rec (n-1) op,op, gen_rec (n-1) op)
  in

 
  (gen_rec n Add)::[gen_rec n Mult]

;;

但它只返回两棵树：一棵只有一个 add op，另一棵有 mult。我不知道如何制作运算符的所有组合。

其次，如果此功能成功，我想遍历所有“空树”并使用[0;1;2].

我有一个开始

let modify_trees_empty list =

  let rec modify_leaf empty_tree = 

    match empty_tree with 
    | Value x -> Value x
    | Node(Value x, op, Value y) -> Node(Val 1, op, Val 1);(*here I want Node(0,op,0),(0,1)..(2,2)*)
    | Node (g, op, d) -> Node(modify_leaf g, op, modify_leaf d)  
  
  in

  let rec iterate_list_and_apply list =
    match list with 
    | [] -> []
    | el :: tl -> [modify_leaf el] @ iterate_list_and_apply tl
  in

  iterate_list_and_apply list
;;

但它只是把叶子变成了一片，这不是我想要的^^

标签： functional-programmingocamlbinary-treecombinationsabstract-syntax-tree

Answer 1

问题 ：

你想要所有大小的树n

解决方案 ：

• 如果n = 0那么它是所有Value i（在你的情况下，i是0，1或2）的列表
• 如果n > 0那么：
  • n-1在名为sub_treesexample的列表中列出所有长度的树。
  • 然后创建一个函数cartesian_product，给定一个列表，返回所有可能的列表元素。例如，cartesian_product [1,2,3]返回[(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3)]
  • 然后对于每个可能的运算符（此处Mult和Add），返回使用此运算符生成的所有树和一对来自cartesian_product sub_trees

关于您当前代码的备注

以下是关于您的代码的一些注释，可以帮助您发现新事物。

为了

let rec iterate_list_and_apply list =
    match list with 
    | [] -> []
    | el :: tl -> [modify_leaf el] @ iterate_list_and_apply tl
  in

您不应使用@运算符将​​唯一元素添加到列表中，而应使用::运算符

| el :: tl -> modify_leaf el :: iterate_list_and_apply tl

还要注意，如果你想让你的程序更短，你也可以使用List.iter modify_leaf listwhich 做同样的事情（但是对这些简单的函数进行编码也是一个很好的练习）iterate_list_and_apply list

另外，这里有一个你可能不知道的语法糖：
而不是

let rec modify_leaf empty_tree = 
   match empty_tree with 
    | ... -> ...
    | ... -> ...

你可以做

let rec modify_leaf = function
    | ... -> ...
    | ... -> ...