Дженерики с экзистенциальными типами в Scala

Question

Рассказ о двух чертах, которые кажутся похожими, должен хорошо сочетаться, но это не так, и я не могу понять, почему этот код не работает или что ошибка компиляции ДЕЙСТВИТЕЛЬНО пытается сказать мне.

Итак ... у нас есть

Черта для родителей ...

trait PolyTreeHasParents[P <: PolyTreeHasChildren[_]]  { 


val _parents: ListBuffer[P] = ListBuffer()

def isRootNode = _parents.size == 0

def parents: List[P] = _parents.readOnly

def addParent(parent: P): PolyTreeHasParents[P] = {

    println(parent)

    if (parent == this)
        throw new IllegalArgumentException()

    _parents += parent

    // 

    this
}




} 

и черта для детей ...

trait PolyTreeHasChildren[C <: PolyTreeHasParents[_]]  {   


val _children: ListBuffer[C] = ListBuffer()

def isLeafNode = children == ListBuffer()

def children: List[C] = _children.readOnly

def += (child: C) : PolyTreeHasChildren[C] = {
    addChild(child)
}

def addChild(child: C): PolyTreeHasChildren[C] = {


    if (child == this)
        throw new IllegalArgumentException()

    _children += child

    child.addParent(this)  // <= ERROR HERE

    this

}

}

Указатель на ОШИБКУ сообщает, что найдено несоответствие типов.

PolyTreeHasChildren.this.type(with underlying type PolyTreeHasChildren[C]) required: _$1 where type _$1 

Я бы подумал, что добавление

P :< PolyTreeHasParents[_]

позволил бы мне добавить ссылку на родителей ребенка.

Вот странная часть ... для обзора, ошибка:

required: _$1 where type _$1 

Что !?

Увы ... У меня закончились идеи, как заставить этот код работать: (

Answer 1

Вы можете избежать этой очевидной бесконечной округлости двумя способами:

Сначала удалите ненужные границы типов (https://stackoverflow.com/questions/1332574/common-programming-mistakes-for-scala-developers-to-avoid/5602321#5602321) - по крайней мере, в вашей текущей реализации PolyTreeHasParents, нетнужно сказать, что P должен быть подтипом PolyTreeHasChildren.

Во-вторых, вы можете добавить еще один аргумент типа к PolyTreeHasChildren, указав тип реализации, и использовать его как собственный тип.Я думаю, что это общий шаблон в библиотеке коллекций.

Это будет выглядеть так:

import collection.mutable.ListBuffer

trait PolyTreeHasParents[P] { 
   val _parents: ListBuffer[P] = ListBuffer()
   def isRootNode = _parents.size == 0
   def parents: List[P] = _parents.readOnly
   def addParent(parent: P): PolyTreeHasParents[P] = {
      require (parent != this)
      _parents += parent
      this
   }
}

trait PolyTreeHasChildren[Repr, C <: PolyTreeHasParents[Repr]] {   
   me: Repr =>

   val _children: ListBuffer[C] = ListBuffer()
   def isLeafNode = children == ListBuffer()
   def children: List[C] = _children.readOnly
   def += (child: C) : Repr = {
      addChild(child)
   }

   def addChild(child: C): Repr = {
      require (child != this)
      _children += child
      child.addParent(this)
      this
   }
}

Answer 2

Сообщение об ошибке кажется странным, но в этом безумии есть метод. Это говорит о том, что вы передаете параметр некоторого известного типа. Но вы указали его как параметр какого-то неизвестного типа, который в этом случае сколомизируется до _ $ 1.

В вашем коде вы можете полностью избавиться от параметров типа:

trait PolyTreeHasParents {
  type P = PolyTreeHasChildren
  val _parents: ListBuffer[P] = ListBuffer()
  def isRootNode = _parents.size == 0
  def parents: List[P] = _parents.readOnly

  def addParent(parent: P): PolyTreeHasParents = {

    if (!_parents.contains(parent)) {
      println(parent)
      if (parent == this) throw new IllegalArgumentException()
      _parents += parent
      parent.addChild(this)
    }
    this
  }
}

trait PolyTreeHasChildren {
  type C = PolyTreeHasParents
  val _children: ListBuffer[C] = ListBuffer()

  def isLeafNode = children == ListBuffer()

  def children: List[C] = _children.readOnly

  def +=(child: C): PolyTreeHasChildren = {
    addChild(child)
  }

  def addChild(child: C): PolyTreeHasChildren = {
    if (!_children.contains(child)) {
      println(child)
      if (child == this)
        throw new IllegalArgumentException()
      _children += child
      child.addParent(this)
    }
    this
  }
}

Смотрите это поведение:

object Test {
  def main(args: Array[String]) {
    trait X extends PolyTreeHasParents with PolyTreeHasChildren
    trait Y extends PolyTreeHasParents with PolyTreeHasChildren
    val x0, x1, x2 = new  X {}
    val y0, y1, y2 = new  Y {}
    x0.addChild(x1)
    x1.addChild(x2)
    y2.addParent(y1)
    y1.addParent(y0)
    x0.addParent(y2)
  }
}

Теперь давайте сравним это с поведением решения "n.m.":

object Test {
  def main(args: Array[String]) {
    trait X extends PolyTreeHasParents[X, X] with PolyTreeHasChildren[X, X]
    trait Y extends PolyTreeHasParents[Y, Y] with PolyTreeHasChildren[Y, Y]
    val x0, x1, x2 = new X {}
    val y0, y1, y2 = new Y {}
    x0.addChild(x1)
    x1.addChild(x2)
    y2.addParent(y1)
    y1.addParent(y0)
//    x0.addParent(y2) // will not compile
  }
}      

Answer 3

Сложность границ параметра типа связана с тем фактом, что ваше PolyTree состоит из 2 признаков.Один, содержащий родителей, и другой, содержащий детей.

Я не понимаю, каков вариант использования этих отдельных признаков.Поскольку в PolyTree, как правило, все ваши узлы могут иметь детей и / или родителей.Поэтому я думаю, что всегда можно смешать их в обоих.

Если это так, то можно избавиться от значительной части сложности границ параметра типа:

trait PolyTree[Self <: PolyTree[Self] ] {
  self: Self =>

  private val _parents: ListBuffer[Self] = ListBuffer()
  def isRootNode = _parents.isEmpty
  def parents: List[Self] = _parents.readOnly

  def addParent(parent: Self): Self = {

    if (!_parents.contains(parent)) {
      println(parent)
      if (parent == this) throw new IllegalArgumentException()
      _parents += parent
      parent.addChild(this)
    }
    this
  }

  private val _children: ListBuffer[Self] = ListBuffer()
  def isLeafNode = _children.isEmpty
  def children: List[Self] = _children.readOnly

  def addChild(child: Self): Self = {
    if (!_children.contains(child)) {
      println(child)
      if (child == this)
        throw new IllegalArgumentException()
      _children += child
      child.addParent(this)
    }
    this
  }

}

Вариант использования:

object UseCasePolyTree {
  trait X extends PolyTree[X]
  trait Y extends PolyTree[Y]
  val x0, x1, x2 = new X {}
  val y0, y1, y2 = new Y {}
  x0.addChild(x1)
  x1.addChild(x2)
  val xx1: X = x2.parents.head
  y2.addParent(y1)
  y1.addParent(y0)
//  x0.addParent(y2) // will not compile
}

Кроме этого:политическое дерево ациклическое.Вам все равно придется добавить код, чтобы предотвратить создание циклов.

Answer 4

Вы пробовали что-то вроде

 trait PolyTreeHasParents[P <: PolyTreeHasChildren[PolyTreeHasParents[P]]]  { }

 trait PolyTreeHasChildren[C <: PolyTreeHasParents[PolyTreeHasChildren[C]]]  { }

Экзистенциальные типы здесь не годятся.Вы обязательно говорите: «У моих родителей есть дети неизвестного типа».Вы должны сказать что-то вроде «у моих родителей есть дети, похожие на меня».

Отказ от ответственности: у меня еще не было возможности проверить это (нет реального компьютера поблизости, только мобильный телефон).

ОБНОВЛЕНИЕ: нет, это не работает.Если вам все еще интересно, ниже приведен рабочий код.Я добавил его симметрично (addParent вызывает addChild, addChild вызывает addParent), чтобы проиллюстрировать, как это работает, когда действительно необходимы циклические зависимости.Я использовал идею 0 __ здесь ввести sel-type.import scala.collection.mutable.ListBuffer

trait PolyTreeHasParents[Repr <: PolyTreeHasParents[Repr, P], 
      P <: PolyTreeHasChildren[P, Repr]]  {   

me: Repr =>

    val _parents: ListBuffer[P] = ListBuffer()
    def isRootNode = _parents.size == 0
    def parents: List[P] = _parents.readOnly
    def addParent(parent: P): Repr = { 
        if (! _parents.contains(parent) {
            println(parent)
            if (parent == this)
            throw new IllegalArgumentException()
            _parents += parent
            parent.addChild(this)
        }
        this
    }
}

trait PolyTreeHasChildren[Repr <: PolyTreeHasChildren[Repr, C],
      C <: PolyTreeHasParents[C, Repr]]  {

me: Repr =>

    val _children: ListBuffer[C] = ListBuffer()
    def isLeafNode = children == ListBuffer()
    def children: List[C] = _children.readOnly
    def += (child: C) : PolyTreeHasChildren[Repr, C] = { 
        addChild(child)
    }
    def addChild(child: C): Repr = { 
        if (! _children.contains(child) {
            println(child)
            if (child == this)
              throw new IllegalArgumentException()
            _children += child
            child.addParent(this)
        }
        this
    }
}

// Usage example
class PP extends PolyTreeHasChildren[PP, CC]
class CC extends PolyTreeHasParents[CC, PP]