module - OCaml：树函数

Question

有没有处理树的模块或函数？我有一个看起来像这样的类型：

    type t =
        Leaf of string (* todo: replace with 'a *)
      | Node of string * t list

我正在努力插入、删除子树等。

我用过谷歌，但找不到任何东西。

Answer 1

In the past, I've used ocamlgraph. This is not a trivial lib to use, but if you need to insert nodes and change path, that could the trick, I've never used that in a b-tree context though...

And extracted from the language documentation:

The most common usage of variant types is to describe recursive data structures. Consider for example the type of binary trees:

#type 'a btree = Empty | Node of 'a * 'a btree * 'a btree;;
type 'a btree = Empty | Node of 'a * 'a btree * 'a btree

This definition reads as follow: a binary tree containing values of type 'a (an arbitrary type) is either empty, or is a node containing one value of type 'a and two subtrees containing also values of type 'a, that is, two 'a btree.

Operations on binary trees are naturally expressed as recursive functions following the same structure as the type definition itself. For instance, here are functions performing lookup and insertion in ordered binary trees (elements increase from left to right):

#let rec member x btree =
   match btree with
     Empty -> false
   | Node(y, left, right) ->
       if x = y then true else
       if x < y then member x left else member x right;;
val member : 'a -> 'a btree -> bool = <fun>

#let rec insert x btree =
   match btree with
     Empty -> Node(x, Empty, Empty)
   | Node(y, left, right) ->
       if x <= y then Node(y, insert x left, right)
                 else Node(y, left, insert x right);;
val insert : 'a -> 'a btree -> 'a btree = <fun>

Hope this helps

Answer 2

在 OCaml 标准库的源代码中阅读模块 Set 的实现。它们是用二叉树实现的，只比你的复杂一点。

（我建议你从二叉树开始，而不是像你定义的那样有一个孩子列表）

Answer 3

实际上，这取决于您希望树的工作方式，例如元素之间是否有顺序等。

否则，您可以在树上使用已知的算法，如果您知道如何用其他语言 C 或 Java 使用它，例如，我可以帮助将其翻译成 OCAML。

Answer 4

我认为，Matt McDonnell有一个Ptree数据类型可以满足您的需求。