Scala Type-Inference для конструктора типов

Существует проблема, с которой стоит начать вывод C[X] = (X,X). Предположим, вы передаете (String, String) где-то, где компилятор ожидает C[String] и должен вывести C, C[X] может быть (X, X), (X, String), (String, X) или даже (String, String) с X фантомом.

Объявление псевдонима Pair не помогает. Я считаю, что вам придется объявить case class Pair[A](_1: A, _2: A) разрешенным, вывод C[X] = Pair[String] и X фантом все еще возможен, но, к счастью, компилятор этого не делает.

Тем не менее, когда вы пишете Tree(1, Pair(Leaf(2), Leaf(3)), это не будет означать C в листьях. Я не очень уверен, почему. Но в любом случае, он никак не мог вывести это, когда вы просто пишете val l = Leaf(2).

Я думаю, вы можете добиться чего-то, сделав все ковариантным.

sealed trait Tree[+C[+X], +A]
case class Leaf[+A](a: A) extends Tree[Nothing, A]
case class Node[+C[+X], +A](a: A, c: C[Tree[C,A]]) extends Tree[C,A]

с ковариацией вы удаляете C из листа, поэтому его не нужно выводить

case class Pair[+A](left: A, right: A)

val tree = Node(1, Pair(Leaf(2), Node(3, Pair(Leaf(3), Leaf(4)))))
tree: Node[Pair,Int] = Node(1,Pair(Leaf(2),Node(3,Pair(Leaf(3),Leaf(4)))))

Побочное замечание, не было бы больше смысла иметь

case object Empty extends Tree[Nothing, Nothing]

а не Leaf. С Leaf есть формы двоичного дерева, которые вы не можете получить.

Обновление относительно ваших комментариев:

Во-первых, не стоит слишком заморачиваться с фантомным типом, я не должен был упоминать об этом. Если вы определяете тип T[X], а X не появляется иначе в определении T, он называется фантомным типом. С этим можно написать умный код, чтобы гарантировать, что некоторые свойства будут проверены во время компиляции, но это не главное.

На самом деле, когда компилятору scala задаются некоторые типы T и X, и он должен вывести C, так что C[X] является (супертипом) T - в моем примере это было T = (String, String) и X = String — это будет работать, только если T (или супертип) является параметризацией типа ровно с одним параметром типа. В более общем смысле, столько параметров типа, сколько имеет параметр типа C. Поскольку C имеет один, а Tuple2 - два (вы определили псевдоним Pair не в счет), он не может работать.

Я пытался указать, что без такого правила у компилятора будет много вариантов для C. Если бы я знал, что (String, Int) — это C[String], и что я должен угадать, что такое C, то я бы подумал, что C[X] — это (X, Int). Когда вы пишете если передано (String, Int), не будет, если выводить (Any, Any), это не имеет смысла, учитывая, что он пытается вывести конструктор типа. Ответ должен быть C[X] = something with X (за исключением возможности того, что X является фантомом). Совершенно другое было бы иметь Pair[X] = (String, Int) и выводить X. Тогда действительно получится X = Any. Итак, если C[String] = (String, String), C[X] = (X, String) является таким же решением, как и C[X] = (X,X).

Что касается вашего второго комментария относительно List, это та же проблема, которая существует и с Pair после того, как вы определили case class Pair (третий абзац в ответе выше), а именно то, что он не будет делать вывод, что такое C, когда вы пишете Leaf(2), где C не появляется . Именно здесь вступает в действие ковариация, избавляющая от параметра C в Leaf и, следовательно, от необходимости его выводить.

Единственный вариант, который пришел мне в голову, заключался в том, чтобы вместо этого аннотировать аргумент Pair. У других людей, я уверен, будут другие идеи.

object BinaryTreeTest {
  sealed trait Tree[C[_], A]
  case class Leaf[C[_], A](a: A) extends Tree[C, A]
  case class Node[C[_], A](a: A, c: C[Tree[C, A]]) extends Tree[C, A]

  type Pair[A] = (A, A)
  type BinaryTree[A] = Tree[Pair, A]

  val p: Pair[Tree[Pair, Int]] = (Leaf(2), Leaf(3))    
  val t: BinaryTree[Int] = Node(1, p)    
}