CODEWITHSUNDEEP
haskelllazy-evaluation
user28522
user28522

Reputation: 321

Getting the first duplicate element of a circular list

I am trying to get the first duplicate element from a circular list. e.g.

[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

I expect v1 and v2 produce the same result, but they don't.

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

I'd like to know why v1 and v2 work produce different results.

Upvotes: 1

Views: 116

Answers (2)

assembly.jc
assembly.jc

Reputation: 2066

Note that the predicate

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

is always true, since cycle repeats the list infinite time as

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

and 1 must be an element of [-2, 3, 2, 3, 4, 5, 5, 1, -2, 3, 2, 3, 4, 5, 5, ...]

so 

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

that is why V1 firstDup return Just 1.

In V2, firstDup' recursively constructs a Set like:

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

and check the next inserted element whether is element of the 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}

Note that 3 is a member of {1, -2, 3, 2}, so firstDup' return Just 3.

Upvotes: 5

castletheperson
castletheperson

Reputation: 33496

In v1, it's returning the first element that has a duplicate somewhere to the right of itself in the list.

In v2, it's returning the first element that has a duplicate somewhere to the left of itself in the list.

In a circular list, the first element will always have a duplicate somewhere to the right, so v1 will always return the first element. Meanwhile, v2 waits until an element has been seen before.

Upvotes: 3

Related Questions