[Haskell-cafe] ordNub

Conrad Parker conrad at metadecks.org
Tue Jul 16 06:08:35 CEST 2013


On 16 July 2013 10:31, Ivan Lazar Miljenovic <ivan.miljenovic at gmail.com> wrote:
> On 16 July 2013 11:46, John Lato <jwlato at gmail.com> wrote:
>> In my tests, using unordered-containers was slightly slower than using Ord,
>> although as the number of repeated elements grows unordered-containers
>> appears to have an advantage.  I'm sure the relative costs of comparison vs
>> hashing would affect this also.  But both are dramatically better than the
>> current nub.
>>
>> Has anyone looked at Bart's patches to see how difficult it would be to
>> apply them (or re-write them)?
>
> If I understand correctly, this function is proposed to be added to
> Data.List which lives in base... but the proposals here are about
> using either Sets from containers or HashSet from
> unordered-containers; I thought base wasn't supposed to depend on any
> other package :/

This discussion (on -cafe@) is just about what course of action to
take; adding such functions to containers or unordered-containers
would not require a libraries@ proposal.

Conrad.

>
>>
>>
>>
>> On Mon, Jul 15, 2013 at 8:43 PM, Clark Gaebel <cgaebel at uwaterloo.ca> wrote:
>>>
>>> Apologies. I was being lazy. Here's a stable version:
>>>
>>>   import qualified Data.HashSet as S
>>>
>>>   hashNub :: (Ord a) => [a] -> [a]
>>>   hashNub l = go S.empty l
>>>     where
>>>       go _ []     = []
>>>       go s (x:xs) = if x `S.member` s then go s xs
>>>                                     else x : go (S.insert x s) xs
>>>
>>> Which, again, will probably be faster than the one using Ord, and I
>>> can't think of any cases where I'd want the one using Ord instead. I
>>> may just not be creative enough, though.
>>>
>>>
>>>   - Clark
>>>
>>> On Mon, Jul 15, 2013 at 12:46 AM, Brandon Allbery <allbery.b at gmail.com>
>>> wrote:
>>> > On Sun, Jul 14, 2013 at 7:54 AM, Clark Gaebel <cgaebel at uwaterloo.ca>
>>> > wrote:
>>> >>
>>> >> Oops sorry I guess my point wasn't clear.
>>> >>
>>> >> Why ord based when hashable is faster? Then there's no reason this has
>>> >> to
>>> >> be in base, it can just be a
>>> >
>>> > Did the point about "stable" fly overhead?
>>> >
>>> > --
>>> > brandon s allbery kf8nh                               sine nomine
>>> > associates
>>> > allbery.b at gmail.com
>>> > ballbery at sinenomine.net
>>> > unix, openafs, kerberos, infrastructure, xmonad
>>> > http://sinenomine.net
>>>
>>> _______________________________________________
>>> Haskell-Cafe mailing list
>>> Haskell-Cafe at haskell.org
>>> http://www.haskell.org/mailman/listinfo/haskell-cafe
>>
>>
>>
>> _______________________________________________
>> Haskell-Cafe mailing list
>> Haskell-Cafe at haskell.org
>> http://www.haskell.org/mailman/listinfo/haskell-cafe
>>
>
>
>
> --
> Ivan Lazar Miljenovic
> Ivan.Miljenovic at gmail.com
> http://IvanMiljenovic.wordpress.com
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>




More information about the Haskell-Cafe mailing list