F#使用函数从列表中删除重复项

Question

我想创建一个获取列表并返回已删除重复项的列表的函数.

let removedupes list1 =
  let list2 = []
  let rec removeduprec list1 list2 =
    match list1 with
    | [] -> list2
    | head :: tail when mem list2 head = false -> head :: removeduprec tail list2
    | _ -> removeduprec list1.Tail list2
  removeduprec list1 list2

我使用这个"mem"函数进入列表,看看该值是否已经存在,在这种情况下,我想继续递归.

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

当我测试这个代码时,我得到了

let list1 =  [ 1; 2; 3; 4; 5; 2; 2; 2]
removedups list1;;
val it : int list = [1; 2; 3; 4; 5; 2; 2; 2]

我认为"head :: removeduprec tail list2",但我对f#很新,所以不完全确定这是如何工作的.

Answer 1

只是为了完整性：在 F# 4.0 中，该List模块现在具有distinct完全符合 OP 要求的功能。

List.distinct [1; 2; 2; 3; 3; 3];;
val it : int list = [1; 2; 3;]

Answer 2

我重写了一些逻辑以使事情变得更简单.问题是你需要list2在创建时添加内容,而不是之后 - 我将内容移动::到调用内部

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

let removedupes list1 =
  let rec removeduprec list1 list2 =
    match list1 with
    | [] -> list2
    | head :: tail when mem list2 head = false -> removeduprec tail (head::list2)
    | h::t -> removeduprec t list2
  removeduprec list1 []

Answer 3

stackoverflow.com/questions/6842466和John的方法的补充; 不那么惯用,但快速而明显:

let removeDups is =
    let d = System.Collections.Generic.Dictionary()
    [ for i in is do match d.TryGetValue i with
                     | (false,_) -> d.[i] <- (); yield i
                     | _ -> () ]

它从具有100000个可能不同值的1000000个元素列表中删除重复项

 Real: 00:00:00.182, CPU: 00:00:00.171, GC gen0: 14, gen1: 1, gen2: 0

更新:使用ildjarn的评论HashSet代替Dictionary在相同数据上摊销两次的提升性能:

Real: 00:00:00.093, CPU: 00:00:00.093, GC gen0: 2, gen1: 1, gen2: 0

相反,在相同的测试用例中使用字面意思设置的缺点是性能27x:

Real: 00:00:02.788, CPU: 00:00:02.765, GC gen0: 100, gen1: 21, gen2: 1