module Bio.Util.Nub ( nubHash, nubHashBy )where

import BasePrelude
import Data.Hashable ( Hashable )
import qualified Data.HashSet as H

nubHash :: (Hashable a, Eq a) => [a] -> [a]
nubHash :: [a] -> [a]
nubHash = (a -> a) -> [a] -> [a]
forall b a. (Hashable b, Eq b) => (a -> b) -> [a] -> [a]
nubHashBy a -> a
forall k (cat :: k -> k -> *) (a :: k). Category cat => cat a a
id

nubHashBy :: (Hashable b, Eq b) => (a -> b) -> [a] -> [a]
nubHashBy :: (a -> b) -> [a] -> [a]
nubHashBy f :: a -> b
f = HashSet b -> [a] -> [a]
go HashSet b
forall a. HashSet a
H.empty
  where
    go :: HashSet b -> [a] -> [a]
go _ [] = []
    go h :: HashSet b
h (x :: a
x:xs :: [a]
xs) | a -> b
f a
x b -> HashSet b -> Bool
forall a. (Eq a, Hashable a) => a -> HashSet a -> Bool
`H.member` HashSet b
h = HashSet b -> [a] -> [a]
go HashSet b
h [a]
xs
                | Bool
otherwise        = a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
: HashSet b -> [a] -> [a]
go (b -> HashSet b -> HashSet b
forall a. (Eq a, Hashable a) => a -> HashSet a -> HashSet a
H.insert (a -> b
f a
x) HashSet b
h) [a]
xs