Выявление дубликатов в кортежах Haskell

Question

Я пытаюсь написать функцию, которая будет Nothing a Just Int кортежем, если любые два значения в кортеже совпадают. Для набора из пяти значений вот что я получил. Очевидно, что есть возможности для улучшения:

nothingIfMatch :: Maybe (Int, Int, Int, Int, Int) -> Maybe (Int, Int, Int, Int, Int)
nothingIfMatch Nothing = Nothing
nothingIfMatch (Just (a, b, c, d, e))
    | a == b = Nothing
    | a == c = Nothing
    | a == d = Nothing
    | a == e = Nothing
    | b == c = Nothing
    | b == d = Nothing
    | b == e = Nothing
    | c == d = Nothing
    | c == e = Nothing
    | d == e = Nothing
    | otherwise = Just (a, b, c, d, e)

Учитывая, что для n-кортежа есть "n выбирать 2" возможные пересечения, в этом случае есть только 10 вариантов. Но представьте, что это 8-кортеж с 28 вариантами или 10-кортеж с 45.

Должен быть более идиоматический способ сделать это, возможно, полагаясь на функции недетерминизма.

Как это сделать?

Answer 1

Сначала мы можем создать список Int с, а затем выполнить все проверки на равенство:

import Data.List(tails)

twoEqual :: Eq a => [a] -> Bool
twoEqual xs = any (uncurry elem) [(h, t) | (h:t) <- tails xs]

Здесь мы сначала генерируем для каждого элемента в списке кортеж, содержащий элемент и rest списка. Затем мы выполняем elem функции: мы вызываем elem для элемента и остальной части списка и в случае, если any этих проверок выполняется, тогда мы возвращаем True, False в противном случае.

Итак, теперь мы можем составить список из этого кортежа, а затем использовать защиту для выполнения проверок:

nothingIfMatch :: Eq a => Maybe (a, a, a, a, a) -> Maybe (a, a, a, a, a)
nothingIfMatch = (>>= f)
    where f r@(a, b, c, d, e) | twoEqual [a, b, c, d, e] = Nothing
                              | otherwise = Just r

Мы можем легко добавить один дополнительный элемент в кортеж и добавить его в список при вызове twoEqual. Здесь мы все еще выполняем O (n ² ) . Мы можем сделать это в O (n log n) , если мы можем сначала упорядочить элементы, или мы можем даже сделать это в O (n) в случае, если элементы хешируемый и не происходит коллизий хешей.

Например:

-- O(n log n) if the elements can be ordered

import Data.List(sort, tails)

twoEqual :: Ord a => [a] -> Bool
twoEqual xs = or [h1 == h2 | (h1:h2:_) <- tails (sort xs)]

Или, если элементы могут быть хэшированы:

-- O(n) in case the elements are hashable and no hash collisions

import Data.Hashable(Hashable)
import Data.HashSet(fromList, member)

twoEqual :: (Hashable a, Ord a) => [a] -> Bool
twoEqual xs = any (flip member hs) xs
    where hs = fromList xs