Проверьте, имеет ли список списков два или более одинаковых элемента

Question

Мне нужно написать функцию, которая проверяет, имеет ли список два или более одинаковых элемента, и возвращает true или false.

Например, [3,3,6,1] должно возвращать true, но [3,8] должно возвращать false.

Вот мой код:

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

Я знаю, что это плохо, и оно не работает.Я хотел сгруппировать список в список списков, и если длина списка составляет> = 2, тогда он должен возвращаться с истинным, иначе ложным.

Answer 1

ОК, в принципе, это один из редких случаев, когда вам действительно нужно sort для эффективности.Фактически, пакет Data.List.Unique имеет функцию repeated только для этой работы, и если источник проверен, можно увидеть, что выбраны стратегии sort и group.Я думаю, что это не самый эффективный алгоритм.Я пойду к тому, как мы можем сделать sort еще более эффективным, но пока давайте немного порадуемся, поскольку это хороший вопрос.

Итак, у нас есть tails :: [a] -> [[a]] функции в пакете Data.List.Соответственно;

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

Как вы можете быстро заметить, мы можем zipWith список tail из tails, который равен [[3,6,1],[6,1],[1],[]], с данным исходным списком, применяя функцию для проверки, если all пункт разные.Эта функция может быть пониманием списка или просто функцией all :: Foldable t => (a -> Bool) -> t a -> Bool.Дело в том, что я хотел бы замкнуть zipWith, чтобы, встретив первый обман, давайте просто перестанем zipWith выполнять расточительную работу, проверяя остальное.Для этой цели я могу использовать монадическую версию zipWith, а именно zipWithM :: Applicative m => (a -> b -> m c) -> [a] -> [b] -> m [c], которая находится в пакете Control.Monad.Причина в том, что из его сигнатуры типа мы понимаем, что он перестанет вычислять дальше, когда он посчитает Nothing или Left whatever в середине, если моя монада окажется Maybe или Either.

Ой ..!В 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).

Я считаю, что было бы лучше использовать небесный sort алгоритмHaskell (который не является сортировкой слиянием, как мы это знаем, кстати) в этом конкретном случае.

Теперь алгоритм вознаграждения идет к -> барабанная дробь здесь -> 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' всегда должен быть победителем.

Answer 2

Только вчера я выложил похожий алгоритм здесь .Возможный способ сделать это -

• сгенерировать последовательность совокупных наборов элементов
  {}, {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 возвращает пару element / set, и мы сопоставляем шаблон, чтобы сохранить только элемент и вернуть его.

result ::  [Int] -> Maybe Int
result xs = do (x,_) <- find(\(y,s)->y `elem` s) (elsets xs)
               return x

Answer 3

Другой способ сделать это, используя 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

Answer 4

Используйте any для получения результата Bool.

any ( . . . ) ( group x )

Не забудьте отсортировать список, group работает с последовательными элементами.

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

Вы можетеиспользуйте (не. null. tail) для предиката в качестве одного из вариантов.