> Niklas Hambüchen nh2.me> writes:
>
> > On 14/10/13 03:20, AntC wrote:
> > ...
> > Then here's a further possible optimisation, instead of making
> > separate calls to `member` and `insert`:
>
> This I understand again. Where do you get insert' from? containers
> doesn't seem to have it. Do y
On 14/10/13 03:20, AntC wrote:
> Thanks Niklas, I hadn't spotted those benchmarks back in July.
No worries :)
> I'm surprised at that result for singletons
> (and for very small numbers of elements which are in fact each different).
I think one of the main reasons for the performance difference
> Niklas Hambüchen nh2.me> writes:
>
> > On 13/10/13 21:42, AntC wrote:
> > ...
> > If you use the Set library, that fact may be very visible!
> > Because Set re-sequences the whole list, as per its Ord instance.
> >
> > But List.nub preserves the list sequence
> > (except for omitting duplicate
On 13/10/13 21:42, AntC wrote:
>> Niklas Hambüchen nh2.me> writes:
>>
>> In sets, the order does not matter, while for nub it does.
>>
>
> Let's be careful here!. Niklas, when you say "order", do you mean:
> * the _ordering_ from the Ord instance? Or
> * the relative sequence of elements in the l
> Niklas Hambüchen nh2.me> writes:
>
> In sets, the order does not matter, while for nub it does.
>
Let's be careful here!. Niklas, when you say "order", do you mean:
* the _ordering_ from the Ord instance? Or
* the relative sequence of elements in the list?
> ... the fact that Set is used ins
* Anthony Cowley [2013-10-12 15:43:57-0400]
>
> On Oct 12, 2013, at 2:47 PM, Niklas Hambüchen wrote:
> >
> > I would like to come back to the original question:
> >
> > How can ordNub be added to base?
> >
> > I guess we agree that Data.List is the right module for a function of
> > type Ord
On 12/10/13 20:43, Anthony Cowley wrote:
> I think nub's behavior is rather set-related, so I don't really understand
> the objection to putting it in Data.Set.
In sets, the order does not matter, while for nub it does.
nub:: Eq a => [a] -> [a]
ordNub :: Ord a => [a] -> [a]
both do
On Oct 12, 2013, at 2:47 PM, Niklas Hambüchen wrote:
>
> I would like to come back to the original question:
>
> How can ordNub be added to base?
>
> I guess we agree that Data.List is the right module for a function of
> type Ord a => [a] -> [a], but this introduces
>
> * a cyclic dependency
I would like to come back to the original question:
How can ordNub be added to base?
I guess we agree that Data.List is the right module for a function of
type Ord a => [a] -> [a], but this introduces
* a cyclic dependency between Data.List and Data.Set
* a base dependency on containers.
What i
On 14/07/13 20:20, Niklas Hambüchen wrote:
> As you might not know, almost *all* practical Haskell projects use it,
> and that in places where an Ord instance is given, e.g. happy, Xmonad,
> ghc-mod, Agda, darcs, QuickCheck, yesod, shake, Cabal, haddock, and 600
> more (see https://github.com/nh2/h
> Richard A. O'Keefe cs.otago.ac.nz> writes:
>
> There are at least four different things that "an Ord version" might
> mean:
>
> - first sort a list, then eliminate duplicates
> - sort a list eliminating duplicates stably as you go
>(think 'merge sort', using 'union' instead of 'merge')
>
On 14.07.2013 13:20, Niklas Hambüchen wrote:
I've taken the Ord-based O(n * log n) implementation from yi using a Set:
ordNub :: (Ord a) => [a] -> [a]
ordNub l = go empty l
where
go _ [] = []
go s (x:xs) = if x `member` s then go s xs
Francesco Mazzoli writes:
>> import qualified Data.HashSet as S
>>
>> nub :: Hashable a => [a] -> [a]
>> nub = S.toList . S.fromList
> Well, the above is not stable while Niklas’ is. But I guess that’s not
> the point of your message :).
We could also implement Data.BloomFilter.nub, which re
On 16 July 2013 10:31, Ivan Lazar Miljenovic wrote:
> On 16 July 2013 11:46, John Lato 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 rel
nubBy is a very good suggestion. Added!
Regarding good hash functions: if your data structure is algebraic,
you can derive generic and Hashable will give you a pretty good hash
function:
> data ADT a = C0 Int String | C1 [a]
> deriving Generic
>
> instance Hashable a => Hashable (ADT a)
It's m
On 16/07/2013, at 3:21 PM, Clark Gaebel wrote:
>
> I'm still against having an Ord version, since my intuition tells me
> that hash-based data structures are faster than ordered ones.
There are at least four different things that "an Ord version" might
mean:
- first sort a list, then eliminate
On Mon, Jul 15, 2013 at 10:31 PM, Ivan Lazar Miljenovic <
ivan.miljeno...@gmail.com> wrote:
> 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-cont
I'm procrastinating something else, so I wrote the patch to
unordered-containers. Feel free to comment on the github link:
https://github.com/tibbe/unordered-containers/pull/67
I'm still against having an Ord version, since my intuition tells me
that hash-based data structures are faster than ord
On Tue, Jul 16, 2013 at 10:31 AM, Ivan Lazar Miljenovic <
ivan.miljeno...@gmail.com> wrote:
> On 16 July 2013 11:46, John Lato wrote:
> > In my tests, using unordered-containers was slightly slower than using
> Ord,
> > although as the number of repeated elements grows unordered-containers
> > ap
On 16 July 2013 11:46, John Lato 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 a
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
c
On Sun, Jul 14, 2013 at 4:20 AM, Niklas Hambüchen wrote:
> tldr: nub is abnormally slow, we shouldn't use it, but we do.
>
>
> As you might know, Data.List.nub is O(n²). (*)
>
> As you might not know, almost *all* practical Haskell projects use it,
> and that in places where an Ord instance is giv
On Sun, Jul 14, 2013 at 7:54 AM, Clark Gaebel 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
Hey Jason,
would you mind giving a short idea of what the point of Bird's
implementation is / from what properties it is derived?
Also, running the QuickCheck tests you added, it doesn't give the same
output (order) as nub.
On 15/07/13 13:26, Jason Dagit wrote:
> Richard Bird has a book, "Pearls
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
Just so people are aware - five years ago the notion of nubOrd and
nubWith was discussed and a consensus reached on including nubOrd. I
think Bart got too busy, didn't submit a final patch, and no one with
commit access actually commited any code.
http://haskell.1045720.n5.nabble.com/GHC-2717-Add
On 15 July 2013 09:54, Joey Adams wrote:
> On Sun, Jul 14, 2013 at 7:31 AM, Clark Gaebel wrote:
>>
>> Similarly, I've always used:
>>
>> import qualified Data.HashSet as S
>>
>> nub :: Hashable a => [a] -> [a]
>> nub = S.toList . S.fromList
>>
>> And i can't think of any type which i can't write
On Sun, Jul 14, 2013 at 7:31 AM, Clark Gaebel wrote:
> Similarly, I've always used:
>
> import qualified Data.HashSet as S
>
> nub :: Hashable a => [a] -> [a]
> nub = S.toList . S.fromList
>
> And i can't think of any type which i can't write a Hashable instance, so
> this is extremely practical.
At Sun, 14 Jul 2013 07:31:05 -0400,
Clark Gaebel wrote:
> Similarly, I've always used:
>
> import qualified Data.HashSet as S
>
> nub :: Hashable a => [a] -> [a]
> nub = S.toList . S.fromList
>
> And i can't think of any type which i can't write a Hashable instance, so
> this is extremely practi
Something like that should definitely be included in Data.List.
Thanks for working on it.
Roman
* Niklas Hambüchen [2013-07-14 19:20:52+0800]
> tldr: nub is abnormally slow, we shouldn't use it, but we do.
>
>
> As you might know, Data.List.nub is O(n²). (*)
>
> As you might not know, almost
One of my main points is:
Should we not add such a function (ord-based, same output as nub,
stable, no sorting) to base?
As the package counting shows, if we don't offer an alternative, people
obviously use it, and not to our benefit.
(Not to say it this way:
We could make the Haskell world fa
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 free function in Data.HashSet. If stability is
a concern then there's a way to easily account for that using HashMap.
- Clark
On Jul 14, 2013 7:48 AM,
Similarly, I've always used:
import qualified Data.HashSet as S
nub :: Hashable a => [a] -> [a]
nub = S.toList . S.fromList
And i can't think of any type which i can't write a Hashable instance, so
this is extremely practical.
On Jul 14, 2013 7:24 AM, "Niklas Hambüchen" wrote:
> tldr: nub is a
tldr: nub is abnormally slow, we shouldn't use it, but we do.
As you might know, Data.List.nub is O(n²). (*)
As you might not know, almost *all* practical Haskell projects use it,
and that in places where an Ord instance is given, e.g. happy, Xmonad,
ghc-mod, Agda, darcs, QuickCheck, yesod, shak
34 matches
Mail list logo
