Creating a parametric graph type in Scala

Question

I'd like to create a generic type hierarchy for representing graphs. In particular, I'd like like to have classes Graph and Node, and I want that for every Graph type, there is a corresponding Node type and if I create a generic function for manipulating Graphs, I want this function to use the actual Node type. An example that 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 this didn't work, because when I did

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

the dfs function would not accept a function of type ConcreteGraph#Node=>Unit as nodeAction, but only AnyRef=>Unit or GNode[ConcreteGraph]=>Unit.

To be clearer, If I did it in C++, I'd 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

A very good example of an extensible graph structure is at http://www.scala-lang.org/node/124

I have thee ways to write yours. Note that in all cases there were some type changes required - i.e. GNode's type parameter needs to be covariant, and ConcreteGraph needs to be written with both a distinct node class and a type bound for Node.

Once done, the first way to write dfs is to make it a method (it can be final if you want to avoid virtual dispatch overhead).

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")}

The second, with dfs not a method, seems to require just a bit of extra type hinting to use it.

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

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

The third way is with a curried dfs. Because of the way Scala's type inference works, that actually results in a cleaner interface

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

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

Answer 2

I don't see why all these parameters are necessary. Inner classes in Scala (unlike Java) have types that depend on the specific instance of the outer object. In particular:

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

Granted, you can't define dfs outside of graph if you want to depend on dependant types.