module Matterhorn.Util
( nubOn
)
where
import Prelude ()
import Matterhorn.Prelude
import qualified Data.Set as Set
nubOn :: (Ord b) => (a -> b) -> [a] -> [a]
nubOn :: forall b a. Ord b => (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')