title: Creating a parametric graph type in Scala
body: <p>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</p>
  
  <pre><code>trait GNode[Graph]
  {
   ... functions to get edges from this vertex, etc. ...
  }
  
  trait Graph
  {
    type Node &lt;: GNode[Graph]
  }
  
  def dfs[G &lt;: Graph](g : G, nodeAction : G#Node =&gt; Unit) = ... code ...
  </code></pre>
  
  <p>but this didn't work, because when I did</p>
  
  <pre><code>class ConcreteGraph extends Graph
  {
    class Node extends GNode[ConcreteGraph] { ... }
  }
  </code></pre>
  
  <p>the dfs function would not accept a function of type <code>ConcreteGraph#Node=&gt;Unit</code> as <code>nodeAction</code>, but only <code>AnyRef=&gt;Unit</code> or <code>GNode[ConcreteGraph]=&gt;Unit</code>.</p>
  
  <p>To be clearer, If I did it in C++, I'd do something like</p>
  
  <pre><code>template &lt;class T&gt; struct graph_traits;
  template &lt;&gt; struct graph_traits&lt;concrete_graph&gt; 
  { typedef concrete_graph::node node_type; }
  
  template &lt;class G&gt;
  void dfs(const G&amp; g, boost::function&lt;void(
             const graph_traits&lt;G&gt;::node_type&amp;)&gt; action) { ... }
  </code></pre>