Skip to content

Instantly share code, notes, and snippets.

@m80126colin

m80126colin/nub.hs

Created April 26, 2018 18:21
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save m80126colin/0852fa76bf741c4a258840f892033aae to your computer and use it in GitHub Desktop.
Save m80126colin/0852fa76bf741c4a258840f892033aae to your computer and use it in GitHub Desktop.
Download ZIP
An amortised linear-time solution by hashing
Raw
nub.hs
import Data.Hashable
import Data.HashSet
-- Amortised linear-time by hashing
uniqhs :: (Hashable a, Eq a) => HashSet a -> [a] -> [a]
uniqhs _ [] = []
uniqhs h (x:xs) = if member x h then uniqhs h xs else x:uniqhs (insert x h) xs
nub :: [Int] -> [Int]
nub = uniqhs empty
@terry182
Copy link

Amortised linear-time POGGERS

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment