f#列表的交集

Question

let rec mem list x = match list with
                 | [] -> false
                 | head :: tail -> 
                   if x = list.Head 
                   then true
                   else mem list.Tail x 

函数mem接受一个列表和一个var X作为参数,并检查列表是否包含值X,如果是,则返回true,如果是,则返回false.

let rec intersection list1 list2 = match list1 with
               | head :: tail -> match list2 with 
                     | head :: tail -> if mem list2 list1.Head = true 
                     then (*add the value to a list*) else intersection list1.Tail list2
               | [] -> failwith "Second list is empty"
       | [] -> failwith "First list is empty"

我对F#很新,我现在遇到的问题是我不知道如何构建一个列表(将值添加到列表中),然后将值添加到它.我还没有测试过代码,因为我需要先完成这一步,以免出错,所以我不能100%确定它是如何工作的.

我试图交叉2个列表,我知道它确实存在这个"Set.Intersect list1 list2"的函数.缩进在这里有点奇怪,因为我不想长行,但你可能会理解.

Answer 1

我喜欢使用集合运算符http://msdn.microsoft.com/en-us/library/ee353629.aspx 你可以使用Set.intersect (Set.ofList list1) (Set.ofList list2) |> Set.toList

Answer 2

修复代码的最直接方法是编写类似下面的代码.

在mem功能,我只是固定的压痕,并更改为使用head和tail您从模式匹配,而不是通过访问他们获得list.Head和list.Tail(因为这样做是更地道,更安全):

let rec mem list x = 
  match list with
  | [] -> false
  | head :: tail -> 
    if x = head then true else mem tail x 

在intersection,诀窍是head::rest当head一个元素出现在两个列表中时使用构建结果列表(并且rest是通过递归地将尾部应用于尾部获得的列表).你也不需要匹配list2因为mem句柄空列表很好:

let rec intersection list1 list2 = 
  match list1 with
  | head :: tail -> 
      let rest = intersection tail list2
      if mem list2 head then head::rest
      else rest
  | [] -> []

这是不是超级效率(假设ñ是长度list1和米是长度list2,你可能需要多达m*n个步骤),但是这可能不是问题的关键.此外,intersection它不是尾递归的,因此它不适用于大型列表,但这是另一个 - 更高级的 - 函数式编程主题.

最后,代码还将返回可能多次包含单个元素的列表 - 但我想这对你来说很好(例如intersection [1;1;1] [1]返回,[1;1;1]但是如果你翻转参数你会得到的[1])