In scala 3, how to get a given Factory for both something like Iteratable and an Array?

Question

I'm trying to create a trait for sorting functions like this:

trait Sorting:
  def sort[A, B >: A, C <: IterableOnce[A]](list: C)(using ord: Ordering[B], factory: Factory[A, C]): C

and here is the implementation:

object InsertionSorting extends Sorting:
  override def sort[A, B >: A, C <: IterableOnce[A]](list: C)(using ord: Ordering[B], factory: Factory[A, C]): C =
    list.iterator
      .foldLeft(ListBuffer.empty[A]) { (acc, x) =>
        {
          val index = acc.view.takeWhile(y => ord.lt(y, x)).size
          acc.insert(index, x)
          acc
        }
      }
      .to(factory)

With a test:

class InsertionSortingSpec extends AnyFlatSpec with should.Matchers:
  "A Sorting" should "sort correctly" in {
    val sorting: Sorting = InsertionSorting
    val input = Seq(31, 41, 59, 26, 41, 58)
    val actual = sorting.sort(input)
    actual shouldBe sorted
  }

It works, so far so good.

But when I'm trying to replace the input in the test with an Array

class InsertionSortingSpec extends AnyFlatSpec with should.Matchers:
  "A Sorting" should "sort correctly" in {
    val sorting: Sorting = InsertionSorting
    val input = Array(31, 41, 59, 26, 41, 58)
    val actual = sorting.sort(input)
    actual shouldBe sorted
  }

Compile failed:

[error] 11 |    val actual = sorting.sort(input)
[error]    |                                    ^
[error]    |no implicit argument of type collection.Factory[A, scala.collection.mutable.ArraySeq.ofInt] was found for parameter factory of method sort in trait Sorting
[error]    |
[error]    |where:    A is a type variable with constraint >: Int

So I had to add another method for Array in Sorting:

trait Sorting:
  def sort[A, B >: A, C <: IterableOnce[A]](list: C)(using ord: Ordering[B], factory: Factory[A, C]): C

  def sort[A: ClassTag, B >: A](array: Array[A])(using Ordering[B]): Array[A] =
    sort(array.iterator).toArray[A]

It works again. I know.

I just wondering is there any way that we can do it in one method?

BTW, the to method for IterableOnce, why the parameter factory is not implicit?

def to[C1](/*using*/ factory: Factory[A, C1]): C1

Update 2022-06-09

Based on the correct answer, I rewrite it like this:

object InsertionSorting extends Sorting:
  override def sort[A, B >: A: Ordering, C](
      xs: C
  )(using view: C => IterableOnce[A], factory: Factory[A, C])(using ClassTag[A]): C =
    import math.Ordered.orderingToOrdered
    view(xs).iterator
      .foldLeft(ListBuffer.empty[A]) { (acc, x) =>
        {
          val index = acc.view.takeWhile(_ < x).size
          acc.insert(index, x)
          acc
        }
      }
      .to(factory)

Just add some syntactic sugar (Context Bounds, Given Imports)

Answer 1

How about this:

Welcome to Scala 3.1.3-RC3 (17.0.3.1, Java Java HotSpot(TM) 64-Bit Server VM).
Type in expressions for evaluation. Or try :help.

scala> import scala.reflect.ClassTag
scala> import scala.collection.mutable.ListBuffer
scala> import scala.collection.Factory

scala> object InsertionSorting:
     |   def sort[C, A](list: C)(using view: C => IterableOnce[A], tag: ClassTag[A], factory: Factory[A, C], ord: Ordering[A]): C =
     |     view(list).iterator
     |       .foldLeft(ListBuffer.empty[A]) { (acc, x) =>
     |         {
     |           val index = acc.view.takeWhile(y => ord.lt(y, x)).size
     |           acc.insert(index, x)
     |           acc
     |         }
     |       }
     |       .to(factory)
     |
// defined object InsertionSorting

scala> InsertionSorting.sort(Array(3, 4, 5, 9, 1, 2))
val res0: Array[Int] = Array(1, 2, 3, 4, 5, 9)

scala> InsertionSorting.sort(List(3, 4, 5, 9, 1, 2))
val res1: List[Int] = List(1, 2, 3, 4, 5, 9)

scala> InsertionSorting.sort(Seq(3, 4, 5, 9, 1, 2))
val res2: Seq[Int] = List(1, 2, 3, 4, 5, 9)

scala> InsertionSorting.sort("abcABC123")
val res3: String = 123ABCabc