I tried to encode the information that a BinaryTree
ADT will have an element with scala.math.Ordering
instance in scope in this post.
enum BinaryTree[+A : Ordering]:
case Leaf extends BinaryTree[Nothing]
case Node[T : Ordering](left: BinaryTree[T], value: T, right: BinaryTree[T]) extends BinaryTree[T]
I wrote a function to transform the binary tree by replacing the left node with a leaf node.
import scala.math.Ordering
def doSomething[A](tree: BinaryTree[A]): BinaryTree[A] =
import BinaryTree._
tree match
case Leaf => Leaf
case a@Node(_, _, _) => a.copy(left = Leaf)
Now the compiler gives this error message
[error] 22  case a@Node(_, _, _) => a.copy(left = Leaf)
[error]  ^
[error] No implicit Ordering defined for T$1
[error] 
[error] where: T$1 is a type in method doSomething with bounds <: A
[error] ..
[error] I found:
[error] 
[error]  math.Ordering.ordered[A](
[error]  {
[error]  def $anonfun(x: T$1): Comparable[? >: T$1] = int2Integer(x)
[error]  closure($anonfun)
[error]  }
[error]  )
[error] 
[error] But method int2Integer in object Predef does not match type math.Ordering.AsComparable[A].
Why is it trying to prove that A
has an Ordering
instance when that is proved by the existence of the BInaryTree[A]
method parameter?
As discussed in the other thread, this only requires a given Ordering[A]
to be available at construction time (where itâ€™s not actually used, as it stands)  it doesnâ€™t â€śproveâ€ť anything about A
in general.
1 Like
okay, whatâ€™s the way to make the method compile?
You need to require an Ordering[A]
in the method signature.
Further:

Leaf
is a BinaryTree[Nothing]
(and Nothing
is a subtype of any type).

Ordering
is not covariant.
 The assignment to
left
would be applicable to any subtype of A
.
Thus youâ€™ll have to declare that you specifically mean Leaf
to take the role of a BinaryTree[A]
in this case. You could do this explicitly at the usage site (i.e. left = Leaf: BinaryTree[A]
), but it may be more convenient in the long run to provide a â€śfactory methodâ€ť
object BinaryTree:
def empty[A]: BinaryTree[A] = Leaf
â€¦so you can use left = empty[A]
.
You need to require an Ordering[A]
in the method signature.
you mean this?
def doSomething[A : Ordering](tree: BinaryTree[A]): BinaryTree[A] =
import BinaryTree._
tree match
case Leaf => Leaf
case a@Node(_, _, _) => a.copy(left = Leaf)
?
even that doesnâ€™t compile
gives this error
[error] 22  case a@Node(_, _, _) => a.copy(left = Leaf)
[error]  ^
[error] No implicit Ordering defined for T$1
[error] 
[error] where: T$1 is a type in method doSomething with bounds <: A
[error] ..
[error] I found:
[error] 
[error]  math.Ordering.ordered[A](
[error]  {
[error]  def $anonfun(x: T$1): Comparable[? >: T$1] = int2Integer(x)
[error]  closure($anonfun)
[error]  }
[error]  )
[error] 
[error] But method int2Integer in object Predef does not match type math.Ordering.AsComparable[A].
Yes, thatâ€™s still missing the second part of my suggestion: In left = Leaf
, the RHS (i.e. Leaf
) potentially might be of type BinaryTree[T$1]
for any subtype T$1
of A
, and thereâ€™s no Ordering[T$1]
available. You need to declare that you mean exactly A
, see above.
1 Like
yes, that did the trick. Sorry I missed the part  Ordering is invariant
. Thank you:)