Creating a parametric graph type in Scala

Question

I would like to create a general type hierarchy for representing graphs. In particular, I would like to have Graph and Node classes, and I want for each Graph type to exist a corresponding Node type, and if I create a general function for manipulating graphs, I want this function to use the actual Node type. The example I tried

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 ...

but it didn’t work, because when I did

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

the dfs function will not accept a type function ConcreteGraph#Node=>Unitas nodeAction, but only AnyRef=>Unitor GNode[ConcreteGraph]=>Unit.

To be clearer, if I did this in C ++, I would do something like

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/node/124

. , - , GNode , ConcreteGraph node, 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")})

- -dfs. - , 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 , .