具有数据类型树的OCaml函数 [英] OCaml function with data type tree

问题描述

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

  type（'a，'b）tree = 
 Empty 
 | 'a *（'a，'b）树列表
 |的顶点'b *（'a，'b）树列表的顶点b 
  

写一个函数split： a，'b）树 - >'list *'b列表，它将类型'a的所有元素保存到第一个列表和所有类型为'b的元素在第二个列表中。

我有一个想法递归地做这件事，但我有点卡住这个。 / b>

  let rec一个drevo_list = 
匹配drevo_list我将附加我的尝试，即使它根本不起作用与
 | [空]  - >清空
 | Empty :: tl  - >一个
 | Vertexa（a，b）:: tl  - > Vertexa（a，b @ tl）
 |顶点（a，b）:: tl  - > Vertexb（a，b @ tl）
  

这个函数将一个列表变成一棵树。我需要它的递归，因为Vertexa或Vertexb中的第二个参数是一个列表。这可以工作
但递归部分不会。

  let rec split drevo = 
 match drevo with 
 |空 - > []，[] 
 | Vertexa（A，B） - >拆分（一个b）
 | Vertexb（A，B） - >拆分（一个b）
  

这部分不起作用，我不知道如何完成它。有没有人有一个想法如何完成这项工作？ 您不需要 drevo_list 函数来解决这个问题。它会导致你错误的方向。

您需要使用 List.map 树木清单。您将获得（'list *'b list）列表类型的值。现在你需要一个帮助函数 concat_pairs ，这个函数将这个值平铺成一对'列表*'b list （比较，标准 concat 函数）。要实现这个功能，你可以使用 List.fold_left 。其余的是微不足道的。

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

We are give a tree that contains two types of elements. It is defined with the following data-structure.

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

Write a function split: ('a,'b) tree -> 'a list * 'b list, that saves all elements of type 'a to the first list and all elements of type 'b in the second list.

I had an idea of doing this recursively but I am kind of stuck on this. I will attach my attempt even though it does not work at all :/

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) 

This function turns a list into a tree. I needed it for the recursion, since the second parametar in Vertexa or Vertexb is a list. And this works But the recursion part does not.

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

This part does not work and I have no idea how to finish it. Does any one have an idea how to finish this?

解决方案

You don't need the drevo_list function to solve this problem. It will actually lead you in a wrong direction.

You need to use List.map to apply your split on a list of trees. You will get a value of ('a list * 'b list) list type. Now you need a helper function concat_pairs that will flatten this value into a pair of type 'a list * 'b list (c.f., standard concat function). To implement this function you may use List.fold_left. The rest is trivial.

Note, of course this is a greedy solution. When you finished with it, you may try to find a better solution, that is more efficient and tail recursive.

这篇关于具有数据类型树的OCaml函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！