-1

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

我知道我没有很好地解释它，所以我会用一个例子来帮助自己。tuple list = [(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

但它仍然给出错误......我该如何解决它？

4

1 回答 1

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函数执行类似的操作，但只有在找到“叶子”或在当前节点中找不到它正在寻找的任何键时才会停止。

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, []))

这是你要找的东西吗？

于 2022-02-07T01:47:02.293 回答