Encoding a Binary Tree in Scala 3

Question
1

I am trying to write type of a BinaryTree in Scala 3. I would like to encode the information that the element should have an Ordering instance.

import scala.math.Ordering

enum BinaryTree[+A : Ordering]:
    case Leaf
    case Node(left: BinaryTree[A], value: A, right: BinaryTree[A]) // compiler error here

But I get an error saying

error] 7 |    case Node(left: BinaryTree[A], value: A, right: BinaryTree[A])
[error]   |    ^
[error]   |No implicit Ordering defined for A..

But I have already told that A has an instanceof Ordering` during the enum declaration. Why does it say that it did not find an Ordering implicit for A? How can I make this work?

EDIT

This worked

enum BinaryTree[+A : Ordering]:
    case Leaf extends BinaryTree[Nothing]
    case Node[T : Ordering](left: BinaryTree[T], value: T, right: BinaryTree[T]) extends BinaryTree[T]

But I am not clear as to why the first method did not work.

2

The “: Ordering” constraint is not a type level feature, but rather declares an additional, anonymous using parameter.

enum BinaryTree[+A : Ordering]:
  case Leaf
  case Node[+T : Ordering](
    left: BinaryTree[T],
    value: T,
    right: BinaryTree[T]
  ) extends BinaryTree[T]

is shorthand for

enum BinaryTree[+A](using ord: Ordering[A]):
  case Leaf
  case Node[+T](
    left: BinaryTree[T],
    value: T,
    right: BinaryTree[T])(
    using ord: Ordering[T]
  ) extends BinaryTree[T]

which in turn desugars to something like

sealed trait BinaryTree[+A](using ord: Ordering[A])

object BinaryTree:
  case object Leaf extends BinaryTree[Nothing]
  case class Node[+T](
    left: BinaryTree[T],
    value: T,
    right: BinaryTree[T])(
    using ord: Ordering[T]
  ) extends BinaryTree[T]

In other words, the type constraint requires a given Ordering[A] to be available for all BinaryTree constructors (either being in scope or provided as a using parameter) - but this instance is not used or kept around.

2 Likes