f# - 在列表中查找重复元素的基本功能是什么？

Question

在列表中查找重复元素的基本功能是什么？

翻译后，我如何简化以下功能:

let numbers = [ 3;5;5;8;9;9;9 ]

let getDuplicates = numbers |> List.groupBy id
                            |> List.map snd
                            |> List.filter (fun set -> set.Length > 1)
                            |> List.map (fun set -> set.[0])

我确定这是重复的。但是，我无法在此站点上找到问题。

更新

let getDuplicates numbers =

    numbers |> List.groupBy id
            |> List.choose (fun (k,v) -> match v.Length with
                                         | x when x > 1 -> Some k
                                         | _            -> None)

Answer 1

简化您的函数 :

每当您有一个 过滤器 后跟一个 映射 时，您就可以用 choose _0x104 替换该对。选择的目的是为列表中的每个值运行一个函数，只返回返回 Some 值的项目(没有值被删除，这是过滤器部分)。无论你在 Some 里面放什么值，都是 map 部分:

let getDuplicates = numbers |> List.groupBy id
 |> List.map snd
 |> List.choose( fun( set ) ->
 if set.Length > 1
 then Some( set.[0] )
 else None )

我们可以通过删除 map 来采取额外的步骤。在这种情况下，保留包含键的元组是有帮助的，因为它不需要获取列表的第一项:

let getDuplicates = numbers |> List.groupBy id
                            |> List.choose( fun( key, set ) ->
                               if set.Length > 1
                                  then Some key
                                  else None )

这比原来的简单吗？也许。因为 选择 结合了两个目的，它必然比那些分开的目的更复杂( 过滤器 和 映射 _092046 可能使代码更难理解，“撤销”可能会使代码更难理解，7 .稍后会详细介绍。

分解概念

不过，简化代码并不是直接的问题。您询问了可用于查找重复项的功能。在高层次上，您如何找到重复项？这取决于您的算法和特定需求:

您给定的算法使用“根据项目的值将项目放入桶中”，以及“查找包含多个项目的桶”。这是与 List.groupBy 和 List.choose (或过滤器/映射)

的直接匹配

一种不同的算法可以是“遍历所有项目”、“修改我们看到的每个项目的累加器”，然后“报告多次看到的所有项目”。这有点像第一个算法，其中 List.fold 之类的东西正在替换 List.groupBy，但是如果您需要拖动其他类型的状态，它可能会有所帮助。

也许你需要知道有多少次重复。满足这些要求的不同算法可能是“对项目进行排序，使它们总是升序”，以及“标记下一个项目是否与当前项目相同”。在这种情况下，您有一个 List.sort 后跟一个 List.toSeq 然后是 Seq.windowed :

let getDuplicates = numbers |> List.sort
                            |> List.toSeq
                            |> Seq.windowed 2
                            |> Seq.choose( function
                              | [|x; y|] when x = y -> Some x
                              | _ -> None )

请注意，这将返回一个带有 [5; 的序列； 9; 9]，通知您 9 重复了两次。

这些是主要基于列表函数的算法。已经有两个答案，一个是可变的，另一个不是，它们基于集合和存在。

我的观点是，有助于查找重复项的完整函数列表读起来就像现有集合函数的谁是谁的列表——这完全取决于您要尝试做什么和您的特定要求。我认为您对 List.groupBy 和 List.choose 的选择可能非常简单。

简化可维护性

关于简化的最后一个想法是记住，简化代码会在一定程度上提高代码的可读性。超出这一点的“简化”很可能涉及技巧或模糊的意图。如果我回顾一下我在几周前和几个项目前编写的代码示例，最短且可能最简单的代码可能不是最容易理解的。因此最后一点——简化 future 的代码可维护性可能是您的目标。如果是这种情况，您的原始算法修改后仅保留 groupBy 元组并添加有关管道每个步骤正在执行的操作的注释可能是您最好的选择:

// combine numbers into common buckets specified by the number itself
let getDuplicates = numbers |> List.groupBy id
                            // only look at buckets with more than one item
                            |> List.filter( fun (_,set) -> set.Length > 1)
                            // change each bucket to only its key
                            |> List.map( fun (key,_) -> key )

最初的问题评论已经表明，您的代码对于不熟悉它的人来说是不清楚的。这是经验问题吗？确实。但是，无论我们是在团队中工作，还是孤军奋战，优化代码(在可能的情况下)以快速理解应该是每个人的首要任务。 (从沙箱上爬下来......):)

不管怎样，祝你好运。