-- | Find the first element in a `List` that repeats.
-- It is possible that no element repeats, hence an `Optional` result.
--
-- /Tip:/ Use `findM` and `State` with a @Data.Set#Set@.
--
-- prop> case firstRepeat xs of Empty -> let xs' = hlist xs in nub xs' == xs'; Full x -> length (filter (== x) xs) > 1
-- prop> case firstRepeat xs of Empty -> True; Full x -> let (l, (rx :. rs)) = span (/= x) xs in let (l2, r2) = span (/= x) rs in let l3 = hlist (l ++ (rx :. Nil) ++ l2) in nub l3 == l3
firstRepeat ::
  Ord a =>
  List a
  -> Optional a
firstRepeat list =
  eval (firstRepeatH list) S.empty

firstRepeatH ::
  Ord a =>
  List a
  -> State (S.Set a) (Optional a)
firstRepeatH Nil =
  return Empty
firstRepeatH (x:.xs) =
  do
    res <- addH x
    if res == Empty
      then firstRepeatH xs
      else return res

addH ::
  Ord a =>
  a
  -> State (S.Set a) (Optional a)
addH a =
  State (\s -> if (S.member a s) then (Full a, s) else (Empty, S.insert a s))