Optimize distinct/distinctBy implementations for non-empty collections

[satorg]

A follow up for #4608 (see my comment #4608 (comment)).
For an example of a pretty well optimized implementation one could check out the corresponding methods in Chain:

cats/core/src/main/scala/cats/data/Chain.scala

Lines 797 to 813 in 930f25c

	def distinct[AA >: A](implicit O: Order[AA]): Chain[AA] = {
	if (isEmptyOrSingleton) this
	else {
	implicit val ord: Ordering[AA] = O.toOrdering
	val bldr = Vector.newBuilder[AA]
	val seen = mutable.TreeSet.empty[AA]
	val it = iterator
	while (it.hasNext) {
	val next = it.next()
	if (seen.add(next))
	bldr += next
	}
	// Result can contain a single element only.
	Chain.fromSeq(bldr.result())
	}
	}

cats/core/src/main/scala/cats/data/Chain.scala

Lines 826 to 842 in 930f25c

	def distinctBy[B](f: A => B)(implicit O: Order[B]): Chain[A] = {
	if (isEmptyOrSingleton) this
	else {
	implicit val ord: Ordering[B] = O.toOrdering
	val bldr = Vector.newBuilder[A]
	val seen = mutable.TreeSet.empty[B]
	val it = iterator
	while (it.hasNext) {
	val next = it.next()
	if (seen.add(f(next)))
	bldr += next
	}
	// Result can contain a single element only.
	Chain.fromSeq(bldr.result())
	}
	}

[sinpat]

Hi,
I would like to implement this optimization.
I haven't contributed yet and I think this could be a good first issue.

[BartekBH]

Hi,

@sinpat Are you still working on this issue?

@satorg I took a look at it, and I believe I can implement this optimization. However, I want to clarify what exactly needs to be done. Based on your comments, is the optimization required only for NonEmptyList, NonEmptySeq, and NonEmptyVector? Am I correct? Also, should I provide some proof that the optimization is effective?

[sinpat]

Hi @BartekBH
feel free to go ahead.
I have been slacking horribly on this.