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 = 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')