Encoding a Binary Tree in Scala 3 - II

Question
1

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?

2

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
3

okay, what’s the way to make the method compile?

4

You need to require an Ordering[A] in the method signature. :slight_smile:

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].

5

You need to require an Ordering[A] in the method signature. :slight_smile:

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)

?

6

Yes, exactly.

7

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].
8

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
9

yes, that did the trick. Sorry I missed the part - Ordering is invariant. Thank you:)