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 :: (a -> b) -> [a] -> [a]
nubOn a -> b
f = (Set b, [a]) -> [a]
forall a b. (a, b) -> b
snd ((Set b, [a]) -> [a]) -> ([a] -> (Set b, [a])) -> [a] -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Set b -> [a] -> (Set b, [a])
go Set b
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 b -> Set b -> Bool
forall a. Ord a => a -> Set a -> Bool
`Set.member` Set b
before'
            then (Set b
before', [a]
xs')
            else (b -> Set b -> Set b
forall a. Ord a => a -> Set a -> Set a
Set.insert b
key Set b
before', a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a]
xs')