module Matterhorn.Util
  ( nubOn
  )
where

import           Prelude ()
import           Matterhorn.Prelude

import qualified Data.Set as Set

-- | The 'nubOn' function removes duplicate elements from a list. In
-- particular, it keeps only the /last/ occurrence of each
-- element. The equality of two elements in a call to @nub f@ is
-- determined using @f x == f y@, and the resulting elements must have
-- an 'Ord' instance in order to make this function more efficient.
nubOn :: (Ord b) => (a -> b) -> [a] -> [a]
nubOn :: forall b a. Ord b => (a -> b) -> [a] -> [a]
nubOn a -> b
f = forall a b. (a, b) -> b
snd forall b c a. (b -> c) -> (a -> b) -> a -> c
. Set b -> [a] -> (Set b, [a])
go forall a. Set a
Set.empty
  where go :: Set b -> [a] -> (Set b, [a])
go Set b
before [] = (Set b
before, [])
        go Set b
before (a
x:[a]
xs) =
          let (Set b
before', [a]
xs') = Set b -> [a] -> (Set b, [a])
go Set b
before [a]
xs
              key :: b
key = a -> b
f a
x in
          if b
key forall a. Ord a => a -> Set a -> Bool
`Set.member` Set b
before'
            then (Set b
before', [a]
xs')
            else (forall a. Ord a => a -> Set a -> Set a
Set.insert b
key Set b
before', a
x forall a. a -> [a] -> [a]
: [a]
xs')