Scala given in lexical scope not found in called function

In Programming in Scala (5th ed), page 462, there is the following code:

def isort[T](xs: List[T])(using ord: Ord[T]): List[T] =
  if xs.isEmpty then Nil
    else insert(xs.head, isort(xs.tail))

def insert[T](x: T, xs: List[T])(using ord: Ord[T]): List[T] =
  if xs.isEmpty || ord.lteq(x, xs.head) then x :: xs
  else xs.head :: insert(x, xs.tail)

where Ord[T] is defined as:

trait Ord[T]:
  def compare(x: T, y: T): Int
  def lteq(x: T, y: T): Boolean = compare(x, y) < 1

I was trying to understand the need for the using parameter list in the isort function. I worked it out with chatgpt (reasonably well). It seems to make sense in the case where these are defined in one file and are called by a function in another file. In that case, the Ord[T] isn't defined in the compilation unit so it can't be provided to insert unless it first is provided to isort.

However, I then asked if the using param list is still required if the given (along with the calling function - like main) was also defined (or imported) in the same file. In that case it would be available to the insert function in the same way it is available to a calling function.

So, I tried the following in a single-file application:

trait Ord[T]:
  def compare(x: T, y: T): Int
  def lteq(x: T, y: T): Boolean = compare(x, y) < 1

given intOrd: Ord[Int] with
  def compare(x: Int, y: Int): Int = x - y

def isort[T](xs: List[T]): List[T] =
  if xs.isEmpty then Nil
  else insert(xs.head, isort(xs.tail))

def insert[T](x: T, xs: List[T])(using ord: Ord[T]): List[T] =
  if xs.isEmpty || ord.lteq(x, xs.head) then x :: xs
  else xs.head :: insert(x, xs.tail)

object Given {
  def main(args: Array[String]): Unit = {
    println(isort(List(3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5)))
  }
}

Here, I removed the (using ord: Ord[T]) from the isort function definition. And, like chatgpt seemed to indicate, I get the error:

No given instance of type Ord[T] was found for parameter ord of method insert
  else insert(xs.head, isort(xs.tail))

If I add the using parameter list back into the isort function definition then it works as expected.

I don't understand why main can find the proper given but isort cannot. The definition is in scope for all three functions: isort, insert, and main. Why is it not visible to isort and insert?

Solution

I don't understand why main can find the proper given but isort cannot.

Because in main you need Ord[Int] and it's defined as intOrd. But insert[T] and therefore isort[T] needs Ord[T] (for abstract T aka arbitrary T) and such instance isn't defined (*). So you need to assume (with (using ord: Ord[T])) that it will be present upon a call (when T is inferred to be Int).

(*) You can check that if you add

given tOrd[T]: Ord[T] with
  def compare(x: T, y: T): Int = ???

then (using ord: Ord[T]) wouldn't be necessary but such instance (the same for arbitrary T) doesn't make much sense.

BTW, if you put instances of a type class to its companion object

trait Ord[T]:
  ...

object Ord:
  given intOrd ...

  ...

then such instances can be found in other compilation units without import.