firstRepeat test "removing repeats matches nub" doesn't really work.

[pedrofurla]

The code in question https://github.com/system-f/fp-course/blob/master/src/Test/StateTest.hs#L127:

  , testProperty "removing repeats matches nub" $ \xs ->
      case firstRepeat (xs :: List Integer) of
        Empty -> True
        Full x ->
          let
            (l, rx :. rs) = span (/= x) xs
            (l2, _) = span (/= x) rs
            l3 = hlist (l ++ rx :. l2)
          in
            nub l3 == l3

The spans and the list reconstruction don't account for lists with multiple repetitions. The test fail for this input listh [4,10,1,9,9,8,2,-9,10,8], where l3 == [4,10,1,9,9,8,2,-9] && nub l3 == [4,10,1,9,8,2,-9].

An alternative is removing all repetitions:

  , testProperty "removing repeats matches nub" $ \(xs :: List Integer) ->
      let xs' = hlist $
            P.fix (\r as ->
              let
                rep = firstRepeat as
                as' = ((\a -> (\a' -> if a == a' then Nil else a' :. Nil) =<< as) <$> rep) ?? as
              in if as' /= as then r as' else as') xs
      in nub xs' == xs'

Happy to make a PR.

[lowderdev]

My implementation for firstRepeat is:

firstRepeat :: Ord a => List a -> Optional a
firstRepeat as = eval (findM p as) S.empty
  where
    p x = State (\s -> (S.member x s, S.insert x s))

The function appears to return correctly for the input in question, but I may be misunderstanding? 🤔

>> firstRepeat $ listh [4,10,1,9,9,8,2,-9,10,8]
Full 9

[pedrofurla]

Yes, mine is very similar, but the test still fails. The test is the thing that is wrong.

[tonymorris]

PR please :)

[aveia]

@pedrofurla it seems that you believe that firstRepeat $ listh [4,10,1,9,9,8,2,-9,10,8] should be 10, but it's supposed to be 9. The task is to find the first duplicate, not the first item that has a duplicate.