Functional Union Find!

package _01UnionFind

object UnionFind {

  /***functional union find!  Need to define a data type for connections
   *
   * A node is an int and a char, which are the ID and the Value
   *
   * A connected group is a set of nodes connected to each other.  If an node
   * isnt connected to anything, it is in its own group.
   *
   * Connections is the set of all the connected groups.  Some of which may only have 1
   * element in them.
   */
  type ConnectedGroup = List[ ( Int, Char ) ]
  type Connections = List[ ConnectedGroup ]

  //Simple method to generate an intial Connections from a list of chars.
  def CreateConnections( inlist: List[ Char ] ): Connections = {
    def CreateLoop( in: List[ Char ], id: Int ): Connections = in match {
        case Nil => Nil
        case x::xs => List(( id, x ))::CreateLoop( xs, id+1 )
    }
    CreateLoop(inlist, 0)
  }

  /*** Now the fun stuff. ***/

  /* Union - given two IDs, combine them.
   * We want to return a new Connections that represents the updated set.  So as we step through the old
   * Connections, we can return, untouched, connected groups that do not contain p or q.  p and q's connected
   * groups need to be combined, and then have them returned.
   *
   */
  def union( inlist: Connections, p: Int, q: Int ): Connections = {
    def unionloop( in: Connections, carry: ConnectedGroup, p: Int, q: Int, found: Int ): Connections = in match {
      case Nil => Nil
      case node::nodes => {
        if ( (contains( node, p ) || contains( node, q )) && ( found < 0 ) ) unionloop( nodes, node, p, q, 1 )
        else if ( contains( node, p ) || contains( node, q ) ) ( carry:::node )::unionloop( nodes, carry, p, q, 1 )
        else node::unionloop( nodes, carry, p, q, found )
      }
    }
    unionloop( inlist, Nil, p, q, -1)
  }

  def contains( group: ConnectedGroup, id: Int ): Boolean = group match {
    case Nil => false
    case node::nodes => if( node._1 == id ) true else contains( nodes, id )
  }

  /* Find -Given an ID, return its value.
   *
   *  I'm lazy, so this is gonna return a list of the chars with that ID, which should only ever
   *  be a list of 1 or 0 char
   *
   *  Inefficient algo though, touches every single node to find the value, so N
   *
   */
  def find( inlist: Connections, p: Int ): List[Char] =
    for (group <- inlist; node <- group; if node._1 == p ) yield node._2
}