`Ordered[Int]` example from Chp 18 of "Programming in Scala 5th edition"

spamegg1 · January 25, 2022, 8:00pm

Hello everyone ,

I am using Scala 3.1.0 I got from Homebrew, with JDK 11:

 ➜ scala
Welcome to Scala 3.1.0 (11.0.13, Java OpenJDK 64-Bit Server VM).
Type in expressions for evaluation. Or try :help.
                                                                    
scala>

I am on Chapter 18 “Type Parameterization” of the 5th edition, at the end of the Chapter on page 314-315. There is the example of the orderedMergeSort function:

def orderedMergeSort[T <: Ordered[T]](xs: List[T]): List[T] =
  def merge(xs: List[T], ys: List[T]): List[T] =
    (xs, ys) match
      case (Nil, _) => ys
      case (_, Nil) => xs
      case (x :: xs1, y :: ys1) =>
        if x < y then x :: merge(xs1, ys)
        else y :: merge(xs, ys1)
  val n = xs.length / 2
  if n == 0 then xs
  else
    val (ys, zs) = xs.splitAt(n)
    merge(orderedMergeSort(ys), orderedMergeSort(zs))

Then there is an example showing why this won’t work with Int because Int is not a subtype of Ordered[Int]. The book says:

scala> val wontCompile = orderedMergeSort(List(3, 2, 1))
<console>:5: error: inferred type arguments [Int] do
   not conform to method orderedMergeSort's type
     parameter bounds [T <: Ordered[T]]
       val wontCompile = orderedMergeSort(List(3, 2, 1))
                         ˆ

However I get the following from the REPL:

click to expand

scala> val wontCompile = orderedMergeSort(List(3,2,1))
-- Error:
1 |val wontCompile = orderedMergeSort(List(3,2,1))
  |                                        ^
  |Found:    (3 : Int)
  |Required: Ordered[
  |  Ordered[
  |    Ordered[
  |      Ordered[
  |        Ordered[
  |          Ordered[
  |            Ordered[
  |              Ordered[
  |                Ordered[
  |                  Ordered[
  |                    Ordered[
  |                      Ordered[Ordered[Ordered[Ordered[...[...]]]]]
  |                    ]
  |                  ]
  |                ]
  |              ]
  |            ]
  |          ]
  |        ]
  |      ]
  |    ]
  |  ]
  |]
  |
  |One of the following imports might fix the problem:
  |
  |  import math.BigDecimal.int2bigDecimal
  |  import math.BigInt.int2bigInt
  |
-- Error:
1 |val wontCompile = orderedMergeSort(List(3,2,1))
  |                                          ^
  |Found:    (2 : Int)
  |Required: Ordered[
  |  Ordered[
  |    Ordered[
  |      Ordered[
  |        Ordered[
  |          Ordered[
  |            Ordered[
  |              Ordered[
  |                Ordered[
  |                  Ordered[
  |                    Ordered[
  |                      Ordered[Ordered[Ordered[Ordered[...[...]]]]]
  |                    ]
  |                  ]
  |                ]
  |              ]
  |            ]
  |          ]
  |        ]
  |      ]
  |    ]
  |  ]
  |]
  |
  |One of the following imports might fix the problem:
  |
  |  import math.BigDecimal.int2bigDecimal
  |  import math.BigInt.int2bigInt
  |
-- Error:
1 |val wontCompile = orderedMergeSort(List(3,2,1))
  |                                            ^
  |Found:    (1 : Int)
  |Required: Ordered[
  |  Ordered[
  |    Ordered[
  |      Ordered[
  |        Ordered[
  |          Ordered[
  |            Ordered[
  |              Ordered[
  |                Ordered[
  |                  Ordered[
  |                    Ordered[
  |                      Ordered[Ordered[Ordered[Ordered[...[...]]]]]
  |                    ]
  |                  ]
  |                ]
  |              ]
  |            ]
  |          ]
  |        ]
  |      ]
  |    ]
  |  ]
  |]
  |
  |One of the following imports might fix the problem:
  |
  |  import math.BigDecimal.int2bigDecimal
  |  import math.BigInt.int2bigInt
  |

If I supply the type parameter [Int] then it gives a message that is closer to the book (but still different):

scala> val wontCompile = orderedMergeSort[Int](List(3,2,1))
-- Error:
1 |val wontCompile = orderedMergeSort[Int](List(3,2,1))
  |                                   ^
  |Type argument Int does not conform to upper bound Ordered[Int]

I wonder if this is an issue with the compiler, or the book, or have things changed since the book was written. Is there an explanation for the nested recursive Ordered[...]s going on? I suppose the type inference is stuck in some loop, then stops at some point?

MarkCLewis · January 25, 2022, 8:27pm

What edition of the book do you have? The error from the book looks like what you would get under 2.x. You are getting the new style. Looks to me like they say the same thing though. I know there was a lot of effort put into trying to make the error messages in Scala 3 more readable.

spamegg1 · January 25, 2022, 8:34pm

Thank you, it’s the 5th edition (June 14 2021) I guess I should mention that. I agree they say the same thing when I provide [Int]. I was curious about the nested Ordered[]s, looked weird, like a bug.

MarkCLewis · January 25, 2022, 8:51pm

That’s not a bug. That’s a valid syntax for giving a type bound. I’m guessing that is part of why they changed the error message to simplify it.

smarter · January 25, 2022, 10:00pm

@MarkCLewis I think you might have missed the long error message hidden behind the “click to expand” link in the original message.

@spamegg1 I’d say that’s a bug yeah, it seems no one actually reran that example with Scala 3 to check the error message (3.0.0 behaves the same so this doesn’t seem to be a regression from a previous Scala 3 release).

spamegg1 · January 26, 2022, 6:40am

Thank you @smarter . Should I report it as a bug on Github? I asked it in compiler discussions on Github (didn’t know where else) but Seth told me to ask it here.

I was able to minimize it somewhat:

scala> def f[T <: Ordered[T]](t: T): T = t
def f[T <: Ordered[T]](t: T): T
                                                                                                                                         
scala> f('a')
-- Error:
1 |f('a')
  |  ^^^
  |Found:    ('a' : Char)
  |Required: Ordered[
  |  Ordered[Ordered[Ordered[Ordered[Ordered[Ordered[Ordered[Ordered[Ordered[Ordered[Ordered[Ordered[Ordered[Ordered[...[...]]]]]]]]]]]]]]]
  |]
  |
  |One of the following imports might make progress towards fixing the problem:
  |
  |  import math.BigDecimal.int2bigDecimal
  |  import math.BigInt.int2bigInt
  |  import math.BigDecimal.long2bigDecimal
  |  import math.BigInt.long2bigInt
  |  import math.BigDecimal.double2bigDecimal
  |  import collection.Searching.search
  |

It works with pretty much anything in place of 'a'. With 1 or Nil or whatever…
Also happens in 3.1.1.

spamegg1 · January 26, 2022, 8:09am

I have the file a.scala

def f[T <: Ordered[T]](t: T): T = t
@main def hi = println(f(1))

Using 3.1.1’s -explain option

*Click To Expand*

 ➜ ./scalac a.scala -explain
-- [E007] Type Mismatch Error: a.scala:3:25 ---------------------------------------------------------------------------------------------
3 |@main def hi = println(f(1))
  |                         ^
  |Found:    (1 : Int)
  |Required: Ordered[
  |  Ordered[Ordered[Ordered[Ordered[Ordered[Ordered[Ordered[Ordered[Ordered[Ordered[Ordered[Ordered[Ordered[Ordered[...[...]]]]]]]]]]]]]]]
  |]
  |
  |One of the following imports might fix the problem:
  |
  |  import math.BigDecimal.int2bigDecimal
  |  import math.BigInt.int2bigInt
  |

Explanation
===========

Tree: 1

I tried to show that
  (1 : Int)
conforms to
  T
but the comparison trace ended with `false`:
          
  ==> (1 : Int)  <:  T
    ==> (1 : Int)  <:  T (recurring)
      ==> (1 : Int)  <:  T (recurring)
        ==> (1 : Int)  <:  T in frozen constraint
          ==> (1 : Int)  <:  T (recurring) in frozen constraint
            ==> (1 : Int)  <:  Nothing (recurring) in frozen constraint
              ==> Int  <:  Nothing (left is approximated) in frozen constraint
                ==> Int  <:  Nothing (recurring) in frozen constraint
                <== Int  <:  Nothing (recurring) in frozen constraint = false
              <== Int  <:  Nothing (left is approximated) in frozen constraint = false
            <== (1 : Int)  <:  Nothing (recurring) in frozen constraint = false
            ==> Int  <:  T (left is approximated) in frozen constraint
              ==> Int  <:  T (recurring) in frozen constraint
                ==> Int  <:  Nothing (recurring) in frozen constraint
                <== Int  <:  Nothing (recurring) in frozen constraint = false
              <== Int  <:  T (recurring) in frozen constraint = false
            <== Int  <:  T (left is approximated) in frozen constraint = false
          <== (1 : Int)  <:  T (recurring) in frozen constraint = false
        <== (1 : Int)  <:  T in frozen constraint = false
        ==> add constraint T >: (1 : Int) false, constraint =  uninstantiated variables: T
 constrained types: [T <: Ordered[T]](t: T): T
 bounds: 
     T <: Ordered[T]
 ordering: 
          ==> lub(Nothing, (1 : Int), canConstrain=false, isSoft=true)
          <== lub(Nothing, (1 : Int), canConstrain=false, isSoft=true) = (1 : Int)
          ==> (1 : Int)  <:  Ordered[T]
            ==> (1 : Int)  <:  Ordered[T] (recurring)
              ==> Int  <:  Ordered[T] (left is approximated)
                ==> Int  <:  Ordered[T] (recurring)
                <== Int  <:  Ordered[T] (recurring) = false
              <== Int  <:  Ordered[T] (left is approximated) = false
            <== (1 : Int)  <:  Ordered[T] (recurring) = false
          <== (1 : Int)  <:  Ordered[T] = false
        <== add constraint T >: (1 : Int) false, constraint =  uninstantiated variables: T
 constrained types: [T <: Ordered[T]](t: T): T
 bounds: 
     T <: Ordered[T]
 ordering:  = false
      <== (1 : Int)  <:  T (recurring) = false
    <== (1 : Int)  <:  T (recurring) = false
  <== (1 : Int)  <:  T = false

The tests were made under a constraint with:
 uninstantiated variables: T
 constrained types: [T <: Ordered[T]](t: T): T
 bounds: 
     T <: Ordered[T]
 ordering: 

1 error found

smarter · January 26, 2022, 10:38am

Please do! Though it’s likely to be low priority since it’s mostly cosmetic.