Получение первого дублирующего элемента кругового списка - PullRequest
Новая
       7

Получение первого дублирующего элемента кругового списка

0 голосов
/ 12 декабря 2018

Я пытаюсь получить первый дубликат элемента из кругового списка.например, 

[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 дает разные результаты.

Ответы [ 2 ]

0 голосов
/ 12 декабря 2018

Обратите внимание, что предикат 

[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.

In V2, firstDup' рекурсивно конструирует Набор как: 

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

и проверяет следующий вставленный элемент, является ли элемент набора как: 

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' возврат Just 3.

0 голосов
/ 12 декабря 2018

В v1 он возвращает первый элемент с дубликатом где-то справа самого себя в списке.

В v2 он возвращает первый элемент, которыйгде-то есть дубликат где-то слева в списке.

В круглом списке первый элемент всегда будет иметь дубликат где-то справа, поэтому v1 всегда будет возвращатьпервый элемент.Тем временем v2 ждет, пока элемент не будет виден ранее.

...