首页 文章

设置尾部递归的交叉点

提问于
浏览 次
1

我试图使用尾递归和空列表 [] 作为 accu 为两个集合的交集生成解决方案：

let rec setintersect list list =
  let rec setintersect2 a b c = 
    match a with
      | [] -> (match b with [] -> (setsimplify c) | h::t -> (setsimplify c))
      | h1::t1 -> (match b with [] -> (setsimplify c) |h2::t2 -> (if (elementof h1 b) then (setintersect2 t1 b (c@[h1])) else (setintersect2 t1 b c)))  in
  setintersect2 list list [];;

Elementof 需要"an int and a list"并正确工作，如果x是列表的元素，则给出true，否则为false .

这是问题所在：

# setintersect [5;2;1] [2;6;9];;
- : int list = [2; 6; 9]

它应该给 [2] .

我究竟做错了什么？我觉得有一些非常简单的东西我误解了！

编辑：感谢您的回复 .

setsimplify 只删除重复项 . 所以 [2,2,3,5,6,6] 变成 [2,3,5,6] . 测试并确保它正常工作 .

我也不应该使用List库中的任何东西 . 另外，我必须使用“tail recursion”，累加器是我 Build 的列表 .

这是思想：

  • 检查 list1 中的head元素，如果它存在于 list2 中，那么使用“ list1 ， list2 的尾部，并列出 c ，其中添加了该元素的". ELSE, then recurse with "尾部 list1 ， list2 和列表 c （原样）” .

  • 结束条件是 list1 或 list2 为空或两者都为空，返回列表 c （原样） .

recursion ocaml tail-recursion

2 回答

  • 1

    let rec setintersect list list = 是错误的：两个参数应该以不同的方式命名（你当然应该更新对 setintersect2 的调用），否则第二个会影响第一个 . 我本以为OCaml至少会警告你这个事实，但事实并非如此 .

    除此之外，代码似乎可以解决问题 . 有几件事可以改进：

    • setintersect 本身不是递归的（只有 setintersect2 ），因此你不需要 rec

    • 你应该为 setintersect2 的参数找到一个不同的名字 . 特别是，哪些是累加器并不明显（大多数OCaml程序员在这些情况下都会理解 acc 或 accu ） .

    • c@[h1] 效率低下：每次附加元素时，您将完全遍历 c . 最好做 h1::c 并在结束时反转结果

    • 作为奖励点，如果您在 c 的开头附加元素，并假设 a 已订购，则您不必在通话结束时调用 setsimplify ：只需检查 c 是否为空，如果不是在这种情况下，只有在 h1 不等于 c 的头部时才追加 h1 .

    回复于
  • 0

    首先，您没有列出您的 setsimplify 功能 .

    要编写 ocaml 函数，请先尝试拆分它，然后尽可能合并 .

    要解决此任务，您只需浏览 l1 中的所有元素，并为每个元素检查它是否在 l2 中，对吧？

    所以你肯定需要一个函数来检查元素是否在列表中，对吧？

    让一个：

    let rec mem x = function
  | [] -> false
  | hd::tl -> hd = x || mem x tl

    然后你可以做你的交集：

    let rec inter l1 l2 =
  match l1 with
    | [] -> []
    | hd::tl -> if mem hd l2 then hd::(inter tl l2) else inter tl l2

    请注意，上面的函数不是尾递归的，我想你可以将它改为tail-recursive作为一个消费税 .

    如果你使用std库，那很简单：

    let intersection l1 l2 = List.filter (fun x -> List.mem x l2) l1
    回复于

相关问题