>>noneRepeated xs = xs == nub xs > Not quite as bad, nub is O(n^2)
You are correct of course. Still, it will probably be a bit less inefficient if the length of the lists are compared (as opposed to the elements): noneRepeated xs = length xs == length (nub xs) On 23 February 2010 14:09, Daniel Fischer <daniel.is.fisc...@web.de> wrote: > Am Dienstag 23 Februar 2010 13:59:49 schrieb Ertugrul Soeylemez: >> Jonas Almström Duregård <jonas.dureg...@gmail.com> wrote: >> > Ertugrul: while your solution is minimalistic, Rafael deemed his >> > ~n*log n implementation too inefficient. Thus your ~n^3 implementation >> > is hardly an improvement... > > Not quite as bad, nub is O(n^2). > >> >> My variant has an advantage, though. It is completely lazy, so it will >> take a shortcut, as soon as a duplicate is found. Depending on his >> application, this may be useful or not. >> >> I think the nub-based solution is the best one in general, but it's the >> base library implementation of nub, which is unfortunate. In fact, with >> a better nub implementation, this becomes an O(n * log n) time > > How can you nub in O(n*log n)? Remember, you only have Eq for nub. > >> algorithm, too, but with the additional laziness advantage. The article >> you linked to contains such an implementation, I think. >> >> >> Greets >> Ertugrul > > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe > _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
