title: How can I create a recursively typed graph(a graph of graph)?
body: <p>I want to create a graph structure which can be used to represent higher level graphs too. I think the problem is best expressed through a figure:
  <img src="https://i.stack.imgur.com/Qczhh.png" alt="Recursive Graph"></p>
  
  <p>As you may have noticed, a graph of level <code>n-1</code> contains nodes of level <code>n</code>. There are no mixed graphs i.e. all nodes in the graph have the same level.</p>
  
  <p>Another aspect of my use case is that the node is basically just a function. So a level 1 graph is an interconnection of functions(think neural networks).</p>
  
  <p>I also need the connection matrix of the graph to be an independent object rather than a property of the node(i.e. I need some object to represent all connections, rather than <code>Node.Next</code> as a property on every node).</p>
  
  <p>A psedocode approach I have in mind is:</p>
  
  <pre><code>class Node&lt;T&gt;:
      func :: T -&gt; T //The function 'func' takes a value of type 'T' and returns another value of type 'T'.
  
  class Network&lt;T where T is instance of Node&gt; inherits Node&lt;T2&gt;:
      ConnectionMatrix&lt;T&gt; matrix;
      override/implement func :: T2 -&gt; T2;
  
  //I'm applying some sort of pattern matching on types here:
  type ConnectionMatrix&lt;Network&lt;T&gt;&gt; = 
      Dictionary&lt;Nerwork&lt;T&gt;, Dictionary&lt;Nerwork&lt;T&gt;, ConnectionMatrix&lt;T&gt;&gt;&gt;
  type ConnectionMatrix&lt;Node&gt; = Dictionary&lt;Node, Dictionary&lt;Node, Integer&gt;&gt;
  </code></pre>
  
  <p>But as you can see it is incomplete, and as it stands can't be represented in any language I know.</p>
  
  <p>The language of implementation should not be an issue as long as it isn't dynamically typed.</p>
  
  <p><strong>Edit:</strong>
  The following solution(as suggested in an answer) will not work by my design:</p>
  
  <pre><code>data Connection = Connection {
      weight :: Double,
      length :: Int
  } deriving (Eq, Show)
  
  data Graph a = Graph {
      nodes :: M.Map Int a,
      edges :: M.Map (Int, Int) Connection
  } deriving (Eq, Show)
  
  data Network a = Simple a | Nested (Network (Graph a))
      deriving (Eq, Show)
  </code></pre>
  
  <p>The reason is that I need a weighted graph such that:</p>
  
  <ul>
  <li>Connection between two Level 0 graphs(i.e. simple nodes) is the same as the above defined <code>Connection</code> type.</li>
  <li>Connections between two Level 1 graphs will be of type <code>M.Map (Int, Int) Connection</code>, hence the edges of the graph should will be of type <code>M.Map (Int, Int) (M.Map (Int, Int) Connection)</code>. This means that each edge in a level 1 graph returns a set of connections between the inner nodes of the level 0 graph.</li>
  <li>Similarly, for a Level n graph, the type of the connection should be <code>M.Map (Int, Int) &lt;Type of connection for Level n-1 graph&gt;</code>.</li>
  </ul>
  
  <p><strong>Edit:</strong> Actually the above representation can work for me; I just need to store the edges in a reduced form. But is it possible to write a program to satisfy the above conditions? </p>