# Encoding a Binary Tree in Scala 3 - II

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)
``````

?

Yes, exactly.

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:)