Создание параметрического типа графа в Scala

Question

Я хотел бы создать общую иерархию типов для представления графиков. В частности, я хотел бы иметь классы Graph и Node, и я хочу, чтобы для каждого типа Graph был соответствующий тип Node, и если я создаю универсальную функцию для манипулирования Graphs, я хочу, чтобы эта функция использовала реальный Node тип. Пример, который я пробовал

trait GNode[Graph]
{
 ... functions to get edges from this vertex, etc. ...
}

trait Graph
{
  type Node <: GNode[Graph]
}

def dfs[G <: Graph](g : G, nodeAction : G#Node => Unit) = ... code ...

но это не сработало, потому что когда я это сделал

class ConcreteGraph extends Graph
{
  class Node extends GNode[ConcreteGraph] { ... }
}

функция dfs не будет принимать функцию типа ConcreteGraph#Node=>Unit как nodeAction, но только AnyRef=>Unit или GNode[ConcreteGraph]=>Unit.

Проще говоря, если бы я делал это в C ++, я бы сделал что-то вроде

template <class T> struct graph_traits;
template <> struct graph_traits<concrete_graph> 
{ typedef concrete_graph::node node_type; }

template <class G>
void dfs(const G& g, boost::function<void(
           const graph_traits<G>::node_type&)> action) { ... }

Answer 1

Очень хорошим примером расширяемой структуры графа является http://www.scala -lang.org / узел / 124

У тебя есть способы написать свой. Обратите внимание, что во всех случаях требовались некоторые изменения типа - то есть параметр типа GNode должен быть ковариантным, а ConcreteGraph должен быть написан как с отдельным классом узла, так и с типом, связанным для Node.

После этого первый способ написать dfs - это сделать его методом (он может быть окончательным, если вы хотите избежать накладных расходов на виртуальную диспетчеризацию).

trait GNode[+Graph] {
//... functions to get edges from this vertex, etc. ...
}

trait Graph {
  type Node <: GNode[Graph]

  def dfs(nodeAction : Node => Unit) = print("dfsing!")
}

class ConcreteGraph extends Graph {
  class CGNode extends GNode[ConcreteGraph]
  type Node <: CGNode
}

new ConcreteGraph dfs {node => println("foo")}

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

def dfs[G <: Graph](graph : G, nodeAction : G#Node => Unit) = print("dfsing!")

dfs[ConcreteGraph](new ConcreteGraph, {node => println("foo")})

Третий путь - с карри. Из-за того, как работает вывод типов в Scala, на самом деле получается более чистый интерфейс

def dfs[G <: Graph](graph : G)(nodeAction : G#Node => Unit) = print("dfsing!")

dfs(new ConcreteGraph){node => println("foo")}

Answer 2

Не понимаю, зачем нужны все эти параметры. Внутренние классы в Scala (в отличие от Java) имеют типы, которые зависят от конкретного экземпляра внешнего объекта. В частности:

trait Graph {
  trait Node
  def dfs(n: Node) = println("DFSing!")
}

val graphA = new Graph {}
val nodeA = new graphA.Node {}
val graphB = new Graph {}
val nodeB = new graphB.Node {}
graphA.dfs(nodaA)  // prints "DFSing!"
graphB.dfs(nodeB)  // prints "DFSing!"
graphA.dfs(nodeB)  // type mismatch; found: graphB.Node required: graphA.Node
graphB.dfs(nodeA)  // type mismatch; found: graphA.node required: graphB.Node

Конечно, вы не можете определять dfs вне графика, если хотите зависеть от зависимых типов.