title: Capturing rules of graph using types in Scala, OCaml and Haskell
body: <p>I am trying to describe a complex graph with many different types of nodes and edges which can only be connected to each other according to a set of rules. I would like these rules to be checked at compile time using the type system of the language. There are many different node and edge types in my real application.</p>
  
  <p>I have easily created a simple example in Scala:</p>
  
  <pre><code>sealed trait Node {
    val name: String
  }
  case class NodeType1(override val name: String) extends Node
  case class NodeType2(override val name: String) extends Node
  case class NodeType3(override val name: String) extends Node
  
  sealed trait Edge
  case class EdgeType1(source: NodeType1, target: NodeType2) extends Edge
  case class EdgeType2(source: NodeType2, target: NodeType1) extends Edge
  
  object Edge {
    def edgeSource(edge: Edge): Node = edge match {
      case EdgeType1(src, _) =&gt; src
      case EdgeType2(src, _) =&gt; src
    }
  }
  
  object Main {
    def main(args: Array[String]) {
      val n1 = NodeType1("Node1")
      val n2 = NodeType2("Node2")
      val edge = EdgeType1(n1, n2)
      val source = Edge.edgeSource(edge)
      println(source == n1)  // true
    }
  }
  </code></pre>
  
  <p>A valid graph can only connect a given edge type between the given types of nodes as shown in the Scala example above. The function "edgeSource" extracts the source node from the edge, as simple as that.</p>
  
  <p>Here comes a non working example of what I would like to write in OCaml:</p>
  
  <pre><code>type node =
      NodeType1 of string
    | NodeType2 of string
  
  type edge =
      EdgeType1 of NodeType1 * NodeType2
    | EdgeType2 of NodeType2 * NodeType1
  
  let link_source (e : edge) : node =
    match e with
    | EdgeType1 (src, _) -&gt; src
    | EdgeType2 (src, _) -&gt; src
  </code></pre>
  
  <p>The problem here is that "NodeTypeX" are constructors and not types. Hence, I am unable to use them when I describe the tuples with source and target for which the edges are defined. The "link_source" function can only return one type and "node" is the variant which can return something.</p>
  
  <p>I have been trying out how to fix this in both OCaml and Haskell and here is an example of one go in OCaml where the node type wraps node_type_X:</p>
  
  <pre><code>type node_type_1 = NodeType1 of string
  type node_type_2 = NodeType2 of string
  
  type node =
      NodeType1Node of node_type_1
    | NodeType2Node of node_type_2
  
  type edge =
      EdgeType1 of node_type_1 * node_type_2
    | EdgeType2 of node_type_2 * node_type_1
  
  let link_source (e : edge) : node =
    match e with
    | EdgeType1 (src, _) -&gt; NodeType1Node src
    | EdgeType2 (src, _) -&gt; NodeType2Node src
  </code></pre>
  
  <p>But the problem with this is that I am duplicating the type information. I am specifying the source node type in the definition of edge, and it is also given when matching the edge in link_source as NodeTypeXNode.</p>
  
  <p>Obviously I am not understanding how to solve this problem. I am stuck thinking in class hierarchies. What would be the correct way to express what I am achieving in the Scala code above in OCaml or Haskell?</p>