如何检查OCaml中n元树的n位置是否有子级

Question

我正在尝试制作一个函数，给定一个元组列表(我不知道元组是否是正确的术语，我的意思是(x，y(列表(和一个n元树，它会返回检查元组中的键是否存在于树中所得到的叶，并将子项放在与该键相关的值的位置，如果它不存在，则会引发错误。

我知道我没有很好地解释，所以我会举个例子来帮助自己。元组列表=[(1,3(；(2,2(；(3,1(；(10,1(]如果根的值是1，则它将检查第三个子项(如果不是，则它继续列表(，然后如果子项的值是10，则它会检查他的第一个子项，直到它找到一个叶子。

我想做的是首先使用List.map删除与元组键不匹配的元素和不在关联值的值位置的子元素，然后递归地对它们的子元素执行同样的操作。

以下是我所做的：

type 'a ntree = Tr of 'a * 'a ntree list;;
let leaf x = Tr(x,[]);; 
let alb = Tr(1,[Tr(2,[leaf 3; leaf 4; leaf 2]);Tr(5,[leaf 11; leaf 10]);Tr(3,[leaf 9; leaf 7; leaf 10])]);;
let guida = [(1,3);(2,2);(3,1);(10,1);(16,2);(11,2)];;

let rec cerca_foglia guida (Tr(x,tlist)) =
match tlist with
[] -> x
|_ -> List.map(fun a -> List.mem_assoc x guida && (*a.position = List.nth tlist List.assoc x guida*)) (cerca tlist)
and cerca = function
[] -> raise NotFound
|[t] -> cerca_foglia guida t
|t::rest -> 
try cerca_foglia guida t
with NotFound -> cerca rest

当然，a.position不存在，那么我该如何检查它呢？

我也尝试了不同的方法：

let rec cerca_foglia guida (Tr(x,tlist)) =
match tlist with
[] -> x
|_ -> List.map(fun a -> a = List.nth tlist List.assoc x guida) (cerca tlist)
and cerca = function
[] -> raise NotFound
|[t] -> if List.mem_assoc t guida then  cerca_foglia guida t else raise NotFound
|t::rest -> 
try cerca_foglia guida t
with NotFound -> cerca rest

但它仍然会出现错误。。。我该如何解决？

Answer 1

经过深思熟虑，我想我可能已经理解了其中的一些内容。我已经编写了两个函数：find_child和find_child2。

type 'a ntree = Tr of 'a * 'a ntree list
let leaf x = Tr(x,[])
let alb = Tr(1,[Tr(2,[leaf 3; leaf 4; leaf 2]);Tr(5,[leaf 11; leaf 10]);Tr(3,[leaf 9; leaf 7; leaf 10])])
let guida = [(1,3);(2,2);(3,1);(10,1);(16,2);(11,2)]
let rec find_child (Tr (root, children) as tree) =
function
| [] -> None
| (k, v)::_ when root = k -> Some (List.nth children (v - 1))
| _::kvs -> find_child tree kvs
let rec find_child2 (Tr (root, children) as tree) key_val_list =
match children with
| [] -> Some tree
| _ ->
(match key_val_list with
| [] -> None
| (k, v)::kvs when root = k -> find_child2 (List.nth children (v - 1)) kvs
| _::kvs -> find_child2 tree kvs)

find_child函数在找到的第一个匹配处停止。因此评估find_child alb guida产量：

utop # find_child alb guida;;
- : int ntree option = Some (Tr (3, [Tr (9, []); Tr (7, []); Tr (10, [])]))

find_child2函数做一些类似的事情，但它只有在找到"0"时才停止；叶子；或者如果它在当前节点中找不到任何要查找的键。

utop # find_child2 alb guida;;
- : int ntree option = Some (Tr (9, []))

对find_child2进行一点重构，以清理它并处理可能发生的Failure "nth"异常：

let rec find_child3 (Tr (root, children) as tree) key_val_list =
match children, key_val_list with
| [], _ -> Some tree
| _, [] -> None
| _, (k, v)::kvs when root = k -> 
(match List.nth children (v - 1) with
| child -> find_child3 child kvs
| exception (Failure "nth") -> None)
| _, _::kvs -> find_child3 tree kvs
| exception Failure "nth" -> None

勾画出当我们评估find_child3 alb guida:时递归的样子

find_child3 alb guida
find_child3 (Tr(1,
[Tr(2,[leaf 3; leaf 4; leaf 2]);
Tr(5,[leaf 11; leaf 10]);
Tr(3,[leaf 9; leaf 7; leaf 10])])) 
[(1,3);(2,2);(3,1);(10,1);(16,2);(11,2)]
find_child3 (Tr(3,[leaf 9; leaf 7; leaf 10])) 
[(2,2);(3,1);(10,1);(16,2);(11,2)]
find_child3 (Tr(3,[leaf 9; leaf 7; leaf 10])) 
[(3,1);(10,1);(16,2);(11,2)]
find_child3 (leaf 9) [(10,1);(16,2);(11,2)]
Some (Tr (9, []))

这就是你要找的东西吗？