Выявление дубликатов в кортежах Haskell
Я пытаюсь написать функцию, которая будет Nothing кортеж JustInt, если любые два значения в кортеже совпадают. Вот что у меня есть для кортежа из пяти значений. Ясно, что есть возможности для улучшения:
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 выберите 2» возможных пересечения для n-кортежа, в этом случае есть только 10 вариантов. Но представьте, что это 8-кортеж с 28 вариантами или 10-кортеж с 45.
Должен быть более идиоматический способ сделать это, вероятно, опираясь на свойства недетерминизма.
Как это сделать?
Ответы 1
Мы можем сначала создать список Int, а затем выполнить все проверки на равенство:
import Data.List(tails)
twoEqual :: Eq a => [a] -> Bool
twoEqual xs = any (uncurry elem) [(h, t) | (h:t) <- tails xs]
Здесь мы сначала генерируем для каждого элемента в списке кортеж, содержащий элемент и отдых списка. Затем мы выполняем функции 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. Здесь мы по-прежнему выполняем О (n2). Мы можем сделать это в O (п войти п), если мы можем сначала упорядочить элементы, или мы можем даже сделать это в На), если элементы являются хэшируемый и не возникает хэш-коллизий.
Например:
-- 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
Ради будущего читателя, не могли бы добавить информацию о том, как это работает?
В случае "no-Ord-available" можно записать twoEqual xs = xs == Data.List.nub xs. Мне это нравится своей краткостью и модульностью; особенно потому, что, как только вы это поймете, вы можете сразу же записать случай «Ord-available» в почти идентичном материале: twoEquals xs_ = xs == Data.List.Ordered.nub xs where xs = sort xs_.
Если вам нужно сохранить произвольное количество данных только одного типа в структуре, вы, вероятно, захотите использовать какой-то список вместо кортежа. Рассмотрим, например,
Maybe [Int]илиMaybe (Vector Int)