On 2017-10-16 at 18:17:19 -0400, Gershom B wrote: [...]
1) I propose two new functions,
`ordNub` and `intNub`
with the standard implementation (from https://github.com/nh2/haskell-ordnub):
import qualified Data.Set as Set
ordNub :: (Ord a) => [a] -> [a] ordNub l = go Set.empty l where go _ [] = [] go s (x:xs) = if x `Set.member` s then go s xs else x : go (Set.insert x s) xs
and the same implementation, but specialized to `Int` and using `IntSet`s.
I'm generally +1 for an 'ordNub'; I don't mind the particular color of the shed. While at it, I'd like to use the occasion to point out two minor things with that specific implementation: a) One thing I've been missing from `container's API are "UPSERT"-ish operations; In the case of `Set`, the implementation above performs a lookup, and then has to start the insertion from scratch. If we had something like, Set.tryInsert :: Ord a => a -> Set a -> (Set a, Bool) or Set.tryInsert :: Ord a => a -> Set a -> Maybe (Set a) `ordNub` would benefit. b) This is more of an observation, as there's not much we can do here with little effort: iirc, `nub` has a worst-case space complexity (if the input list is made up of N distinct values, e.g. (`nub [1..n] :: [Int])) of 3N words for the [a]-spine to keep track of the already seen values. Using `Set` however trades time-complexity for memory-complexity, and needs 5N words for the 'Set a'-spine. c.f. http://blog.johantibell.com/2011/06/memory-footprints-of-some-common-data.ht... -- hvr