获取循环列表的第一个重复元素

Question

我正在尝试从循环列表中获取第一个重复元素。例如

[1,-2, 3, 2, 3, 4, 5, 5]     => Just 3
[0,-2, 9, 2, 3, 4, -23,- 2] => Just (-2)

v1:

firstDup :: Ord a => [a] -> Maybe a
firstDup [] = Nothing
firstDup (x:xs)
  | [x] `intersect` xs == [x]   =  Just x
  | otherwise         = firstDup xs

v2:

firstDup' :: Ord a => [a] -> Maybe a
firstDup' = go Set.empty
  where
    go _ [] = Nothing
    go z (x:xs)
      | x `Set.member` z = Just x
      | otherwise        = go (Set.insert x z) xs

我希望 v1 和 v2 产生相同的结果，但它们不会。

firstDup       . cycle       $ [1,-2, 3, 2, 3, 4, 5, 5]  ==> Just 1
firstDup'      . cycle       $ [1,-2, 3, 2, 3, 4, 5, 5]  ==> Just 3

我想知道为什么 v1 和 v2 会产生不同的结果。

Answer 1

在 v1 中，它是 return 列表中第一个在右边某处有重复项的元素。

在 v2 中，它是 return 列表中第一个在左侧处有重复项的元素。

在循环列表中，第一个元素总是在右边某处有重复项，所以 v1 总是 return 第一个元素。同时，v2 一直等到一个元素被看过。

Answer 2

注意谓词

[x] `intersect` xs == [x]

总是 true，因为 cycle 无限次重复列表，如

[1, -2, 3, 2, 3, 4, 5, 5, 1, -2, 3, 2, 3, 4, 5, 5, ...]

和 1 必须是 [-2, 3, 2, 3, 4, 5, 5, 1, -2, 3, 2, 3, 4, 5, 5, ...]

的元素

所以

[1] `intersect` [-2, 3, 2, 3, 4, 5, 5, 1, -2, 3, 2, 3, 4, 5, 5, ...] = [1]

这就是为什么 V1 firstDup return Just 1.

在V2中，firstDup'递归构造一个Set如：

{}
{1}
{1, -2}
{1, -2, 3}
{1, -2, 3, 2, ...}

并检查下一个插入的元素是否是Set as的元素：

1  `Set.member` {}
-2 `Set.member` {1}
3  `Set.member` {1, -2}
2  `Set.member` {1, -2, 3}
3  `Set.member` {1, -2, 3, 2}

注意 3 是 {1, -2, 3, 2} 的成员，所以 firstDup' return Just 3。

获取循环列表的第一个重复元素

Getting the first duplicate element of a circular list

haskell

lazy-evaluation