Рекурсивные типы в Scala со списком

Аналогично взаимно-рекурсивным типам в scala я пытаюсь создать взаимно-рекурсивный тип в Scala .

Я пытаюсь создать график, определенный с помощью этого типа (который компилируется):

 case class Node(val id : Int, val edges : Set[Node])

Но я не понимаю, как я вообще могу создать что-то с этим типом, потому что для того, чтобы инициализировать Node A с ребрами B и C, мне нужно как минимум иметь ленивую ссылку на B и C, но я не могу одновременно создать их наборы ребер.

Можно ли реализовать этот рекурсивный тип?

РЕДАКТИРОВАТЬ:

Вот решение, которое я сейчас использую для преобразования явного списка смежности в самореферентный.

def mapToGraph(edgeMap : Map[Int, mutable.Set[Int]]) : List[Node] = {
  lazy val nodeMap = edgeMap map  (kv => (kv._1, new Node(kv._1, futures.get(kv._1).get)))
  lazy val futures : Map[Int, Set[Node]] = edgeMap map (kv => {
    val edges = (kv._2 map (e => nodeMap.get(e).get)).toSet
    (kv._1, edges)
  })
  val eval = nodeMap.values.toList
  eval //to force from lazy to real - don't really like doing this
}

или, альтернативно, из списка краев

//reads an edgeList into a graph
def readEdgelist(filename : String) : List[Node] = {
  lazy val nodes = new mutable.HashMap[Int, Node]()
  lazy val edges = new mutable.HashMap[Int, mutable.Buffer[Node]]()
  Source.fromFile(filename).getLines() filter (x => x != None) foreach {edgeStr =>
    val edge = edgeStr.split('\t')
    if (edge.size != 2) goodbye("Not a well-formed edge : " + edgeStr + " size: " + edge.size.toString)
    val src = edge(0).toInt
    val des = edge(1).toInt
    if (!(nodes.contains(src))) nodes.put(src, new Node(src, futures.get(src).get))
    if (!(nodes.contains(des))) nodes.put(des, new Node(des, futures.get(des).get))
    edges.put(src, edges.getOrElse(src, mutable.Buffer[Node]()) += nodes.get(des).get)
  }
  lazy val futures : Map[Int, Set[Node]] = nodes map {node => (node._1, edges.getOrElse(node._1, mutable.Buffer[Node]()).toSet)} toMap
  val eval = nodes.values.toList
  eval
}

Спасибо всем за советы!


person Austin    schedule 12.10.2012    source источник
comment
val объявления в случае, если классы избыточны   -  person Nikita Volkov    schedule 13.10.2012
comment


Ответы (2)


Похоже, вам нужно работать снизу вверх

val b = Node(1, Set.empty)
val c = Node(2, Set.empty)
val a = Node(3, Set(b, c))

надеюсь, это поможет

person RKumsher    schedule 12.10.2012
comment
Восхождение снизу вверх не помогает, если ребра не направлены или если в графе есть циклы. - person Richard Sitze; 13.10.2012
comment
Кроме того, предположим, что вы не хотите строить гораздо больший график. Учтите, что у вас есть edgeList в форме List[(Int, Int)] — вы больше не храните ссылку на каждый узел, верно? - person Austin; 13.10.2012

Курица и яйцо... у вас есть три варианта:

  1. Ограничьте свои графики направленными ациклическими графами (DAG) и используйте предложение RKumsher.

  2. Чтобы сохранить неизменность, вам нужно будет отделить экземпляры узлов от наборов ребер (два разных класса: создать узлы, а затем создать наборы/график ребер).

  3. Если вы предпочитаете тесную корреляцию, рассмотрите возможность использования сеттера для наборов ребер, чтобы вы могли вернуться и установить их позже, после создания всех узлов.

person Richard Sitze    schedule 12.10.2012
comment
Решение, основанное на ленивой ссылке на курицу/яйцо, требует явного кода для создания каждой курицы/яйца (каждой ленивой ссылки); Он не подходит для массовой загрузки слабо структурированных (т. е. с переменным числом узлов и числом ребер на узел) данных, скажем, из файла. - person Richard Sitze; 14.10.2012