时间戳

首页 > 解决方案 > 识别 Haskell 元组中的重复项

algorithm - 识别 Haskell 元组中的重复项

问题描述

我正在尝试编写一个函数，如果元组中的任何两个值相同，则该函数将Nothing成为一个元组。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 种可能性。

必须有一种更惯用的方法来做到这一点，可能依赖于非确定性特征。

这应该怎么做？

标签： algorithmhaskellnon-deterministic

解决方案

我们可以首先生成一个Ints 列表，然后执行所有相等性检查：

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调用中的列表中。在这里，我们仍然执行O(n 2 )。如果我们可以先对元素进行排序，我们可以在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

推荐阅读