OCaml的 - 一棵树

我的树类型的镜像是OCaml的 - 一棵树

type 'a tree = Tree of 'a * 'a tree list;;

我怎样才能得到这样的树的镜像？对于我来说，有一个孩子的名单是令人困惑的，因为我不知道如何分别给每个孩子做递归，而没有丢失父母的踪迹，任何想法？

编辑：我一直想，我想我得到了解决：

let spec arbol = 
     match arbol with 
     Tree(a,[])-> Tree(a,[]) 
     | Tree(a,l)-> Tree(a, List.rev (
        let rec aux = function 
         Tree(a,[])::[]->Tree(a,[])::[] 
         | Tree(a,[])::l-> [Tree(a,[])]@(aux l) 
         | Tree(a,t)::[]-> [Tree(a, (List.rev (aux t)))] 
         | Tree(a,t)::l-> [Tree(a, (List.rev (aux t)))]@(aux l) 
        in aux l));;

我已经和这棵树试了一下：

let p = Tree(1, [ 
    Tree(2,[]); 
    Tree(3, [ 
     Tree(6,[]); 
     Tree(7,[]) 
     ]); 
    Tree(4,[]); 
    Tree(5,[]) 
]);;

而且我得到了作为# spec p;;

结果

-: int tree = Tree (1, [ 
       Tree (5,[]); 
       Tree (4,[]); 
       Tree (3,[ 
        Tree(7,[]); 
        Tree(6,[])]); 
       Tree (2,[]) 
       ])

所以我想我的功能按预期工作。让我知道它是否不正确

来源

2014-01-12 horro

如果我理解你正在尝试计算的函数，那么只需要一行代码就可以得到一个非常简单的答案。

不幸的是，您的代码引入了这么多的案例，很难用眼睛来检查。

它在我看来像你的aux功能是为了计算树列表的镜像。但是，它不适用于空列表。如果您重写aux以在空列表上工作，您可能会发现不需要这么多不同的情况。特别是，你可以在你的内线比赛中移除你最外面的比赛和一半的情况。

事实上，你的aux函数（如果正确的话）完成所有工作。如果你正确地看，它可以使用aux的一切。

由于您使用List.rev，我假设您也可以使用List.map。这也是值得关注的。

更新

树木本身是递归结构，所以寻找一个树算法的时候，它常常有助于想象你会如何使用递归你的算法。在这种情况下，你可以问自己如何将树的所有子树的镜像镜像成整个树的镜像。

来源

2014-01-12 23:50:12

我明白你的意思，其实我已经重写了它这样的： '让规范树= \t \t让REC AUX =功能 \t \t [] - > [] \t \t | Tree（a，t）:: l-> [Tree（a，（List.rev（aux t）））] @（aux l） \t in List.hd（aux [tree]）;; ' 我觉得更清楚了，所有的情况也是可以考虑的。我正在寻找使用'List.map'，但我真的不知道如何在我的代码中使用它。 – horro

你应该真的使用'List.rev_map'。然后这个函数是单线程的，'let rec spec（Tree（a，ts））= Tree（a，List.rev_map spec）' – nlucaroni

这就是我正在谈论的解决方案。但OP可能会更好地弄清楚。 –

OCaml的 - 一棵树

回答

相关问题