logo标签列表

检查一个列表的列表是否有两个或更多相同的元素。

listhaskellfilter
4

我需要编写一个函数来检查列表中是否有两个或更多相同的元素，并返回 true 或 false。

例如，[3,3,6,1] 应该返回 true，但 [3,8] 应该返回 false。

以下是我的代码：

identical :: [Int] -> Bool
identical x = (\n-> filter (>= 2) n )( group x )

我知道这是不好的，也行不通。 我想把列表分组成子列表，如果一个列表的长度>=2，那么它应该返回true，否则返回false。

两个或更多连续相同的元素？还是相同的元素可以放在任何地方？ - Willem Van Onsem
第二个，它是否连续并不重要。 - Tyler Joe
提示：这里的“n”是什么？一个列表“[Int]”？还是一个长度“Int”？如果你对它进行过滤，结果会是什么？ - Willem Van Onsem
也许是一个长度为Int的变量？我尝试过[n]，但它也不起作用。 - Tyler Joe
4个回答
6

使用any来获取布尔结果。

any ( . . . ) ( group x )

不要忘记对列表进行排序，group 只能处理连续的元素。

any ( . . . ) ( group ( sort x ) )

您可以使用（not . null . tail）作为谓词之一，作为选项。
这行代码可以正常工作，但我不理解 not . null . tail 的作用是什么。 - Tyler Joe
1
我可能会选择(not . null . drop 1)，因为drop 1与tail完全不同。但是由于group的语义（它从不生成空列表），在这种情况下并不重要。 - Mor A.
我认为 not . null . tail 不是很清晰。也许值得定义一个函数 longerThan :: Int -> [a] -> Bool，然后它就变得非常清晰：any (longerThan 1) . group . sort。 - leftaroundabout
1
@JorgeAdriano，排序并不比重复的“Set”插入低效（使用来自“containers”库的“Set”类型，无论是O(lg n)还是O(1)）。 - chepner
@chepner 没错，你说得对。不过，重点在于人们不必事先对整个列表进行排序才能找到重复项。 - Jorge Adriano Branco Aires
显示剩余2条评论
1

就在昨天，我发布了一个类似的算法这里。实现的可能方法是：

  • 生成元素的累积集合序列
    {}, {x0}, {x0,x1}, {x0,x1,x2} ...
  • 将原始元素序列与累积集合配对
    x0, x1 , x2 , x3 ...
    {}, {x0}, {x0,x1}, {x0,x1,x2} ...
  • 检查重复插入，即
    xi 满足 xi ∈ {x0..xi-1}

例如，可以通过以下函数实现。 首先，我们使用 scanl 将列表的元素迭代添加到集合中，从而生成这些迭代的累积序列。

sets  :: [Int] -> [Set Int]
sets  = scanl (\s x -> insert x s) empty

然后我们将原始列表与此序列压缩在一起，因此每个xi都与{x0...xi-1}配对。
elsets :: [Int] -> [(Int, Set Int)] 
elsets xs  = zip xs (sets xs)

最后，我们使用find在已经包含元素的集合中搜索一个“即将插入”的元素。函数find返回元素/集合对，我们进行模式匹配，并只保留元素并返回它。
result ::  [Int] -> Maybe Int
result xs = do (x,_) <- find(\(y,s)->y `elem` s) (elsets xs)
               return x
1
另一种使用 Data.Map 的方法如下，虽然不如 ..group . sort.. 解决方案高效, 但仍为 O(n log n)，并且能够处理无限列表。
import Data.Map.Lazy as Map (empty, lookup, insert)

identical :: [Int] -> Bool
identical = loop Map.empty
    where loop _ []     = False
          loop m (x:xs) = if Map.lookup x m == Nothing
                          then loop (insert x 0 m) xs
                          else True
0

好的，基本上这是一个罕见的情况，你真的需要使用sort来提高效率。实际上，Data.List.Unique包有一个repeated函数专门用于此任务，如果检查源代码，可以看到选择了sort和group策略。我想这不是最有效的算法。我将介绍如何使sort更加高效，但现在让我们先享受一下，因为这是一个很好的问题。

所以我们有Data.List包中的tails :: [a] -> [[a]]函数。相应地；

*Main> tails [3,3,6,1]
[[3,3,6,1],[3,6,1],[6,1],[1],[]]

正如您可能很快注意到的那样，我们可以使用zipWith函数将tails列表的tail，即[[3,6,1],[6,1],[1],[]]与给定的原始列表进行组合，并应用一个函数来检查所有项是否都不同。这个函数可以是列表推导式，也可以是简单的all :: Foldable t => (a -> Bool) -> t a -> Bool函数。问题是，我想要短路zipWith，这样一旦我遇到第一个重复项，就让zipWith停止检查剩下的内容，以免做无用功。为此，我可以使用zipWithM :: Applicative m => (a -> b -> m c) -> [a] -> [b] -> m [c]的单子版本，它位于Control.Monad包中。原因是，从它的类型签名中，我们可以理解到，如果我的单子恰好是Maybe或Either，它将在中间计算到Nothing或Left whatever时停止计算。

哦..！在 Haskell 中，我也喜欢使用 bool :: a -> a -> Bool -> a 函数代替 if 和 then。 bool 是 Haskell 的三元运算符，其语法如下：

bool "work time" "coffee break" isCoffeeTime

负选择在左边，正选择在右边，其中isCoffeeTime :: Bool是一个函数，如果现在是喝咖啡的时间则返回True。非常可组合，太酷了..！

既然我们现在已经拥有了所有的背景知识，那么我们可以继续进行代码编写。

import Control.Monad (zipWithM)
import Data.List (tails)
import Data.Bool (bool)

anyDupe :: Eq a => [a] -> Either a [a]
anyDupe xs = zipWithM f xs ts
             where ts = tail $ tails xs
                   f  = \x t -> bool (Left x) (Right x) $ all (x /=) t

*Main> anyDupe [1,2,3,4,5]
Right [1,2,3,4,5] -- no dupes so we get the `Right` with the original list
*Main> anyDupe [3,3,6,1]
Left 3 -- here we have the first duplicate since zipWithM short circuits.
*Main> anyDupe $ 10^7:[1..10^7]
Left 10000000 -- wow zipWithM worked and returned reasonably fast.

但是，正如我所说的，这仍然是一种天真的方法，因为从理论上讲，我们正在执行n(n+1)/2次操作。是的，如果第一个重复项接近头部，zipWithM可以大大减少冗余，但是这个算法仍然是O(n^2)。

我认为在这种特殊情况下最好使用Haskell的天堂级别的sort算法（顺便说一句，这不是我们所知道的归并排序）。

现在，算法奖项授予 -> 鼓声响起 -> sort和fold -> 掌声。抱歉，没有分组。

现在...我们再次使用单子技巧来利用短路。我们将使用foldM :: (Foldable t, Monad m) => (b -> a -> m b) -> b -> t a -> m b。当与Either单子一起使用时，这也允许我们返回更有意义的结果。好的，让我们开始吧。任何Left n表示n是第一个重复项，不需要进行更多计算，而任何Right _表示没有重复项。

import Control.Monad (foldM)
import Data.List (sort)
import Data.Bool (bool)

anyDupe' :: (Eq a, Ord a, Enum a) => [a] -> Either a a
anyDupe' xs = foldM f i $ sort xs
              where i = succ $ head xs -- prevent the initial value to be equal with the value at the head
                    f = \b a -> bool (Left a) (Right a) (a /= b)

*Main> anyDupe' [1,2,3,4,5]
Right 5
*Main> anyDupe' [3,3,6,1]
Left 3
*Main> anyDupe' $ 1:[10^7,(10^7-1)..1]
Left 1
(2.97 secs, 1,040,110,448 bytes)
*Main> anyDupe $ 1:[10^7,(10^7-1)..1]
Left 1
(2.94 secs, 1,440,112,888 bytes)
*Main> anyDupe' $ [1..10^7]++[10^7]
Left 10000000
(5.71 secs, 3,600,116,808 bytes)   -- winner by far
*Main> anyDupe $ [1..10^7]++[10^7] -- don't try at home, it's waste of energy

在现实世界的场景中，anyDupe' 应该总是获胜者。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接