Idiomatic scala solution to combining sequences

Question

Imagine a function combineSequences: (seqs: Set[Seq[Int]])Set[Seq[Int]] that combines sequences when the last item of first sequence matches the first item of the second sequence. For example, if you have the following sequences:

(1, 2)
(2, 3)
(5, 6, 7, 8)
(8, 9, 10)
(3, 4, 10)

The result of combineSequences would be:

(5, 6, 7, 8, 8, 9, 10)
(1, 2, 2, 3, 3, 4, 10)

Because sequences 1, 2, and 5 combine together. If multiple sequences could combine to create a different result, the decisions is arbitrary. For example, if we have the sequences:

(1, 2)
(2, 3)
(2, 4)

There are two correct answers. Either:

(1, 2, 2, 3)
(2, 4)

Or:

(1, 2, 2, 4)
(2, 3)

I can only think of a very imperative and fairly opaque implementation. I'm wondering if anyone has a solution that would be more idiomatic scala. I've run into related problems a few times now.

Answer 1

Certainly not the most optimized solution but I've gone for readability.

def combineSequences[T]( seqs: Set[Seq[T]] ): Set[Seq[T]] = {
  if ( seqs.isEmpty ) seqs
  else {
    val (seq1, otherSeqs) = (seqs.head, seqs.tail)
    otherSeqs.find(_.headOption == seq1.lastOption) match {
      case Some( seq2 ) => combineSequences( otherSeqs - seq2 + (seq1 ++ seq2) )
      case None =>
        otherSeqs.find(_.lastOption == seq1.headOption) match {
          case Some( seq2 ) => combineSequences( otherSeqs - seq2 + (seq2 ++ seq1) )
          case None => combineSequences( otherSeqs ) + seq1
        }
    }
  }
}

REPL test:

scala> val seqs = Set(Seq(1, 2), Seq(2, 3), Seq(5, 6, 7, 8), Seq(8, 9, 10), Seq(3, 4, 10))
seqs: scala.collection.immutable.Set[Seq[Int]] = Set(List(1, 2), List(2, 3), List(8, 9, 10), List(5, 6, 7, 8), List(3, 4, 10))
scala> combineSequences( seqs )
res10: Set[Seq[Int]] = Set(List(1, 2, 2, 3, 3, 4, 10), List(5, 6, 7, 8, 8, 9, 10))
scala> val seqs = Set(Seq(1, 2), Seq(2, 3, 100), Seq(5, 6, 7, 8), Seq(8, 9, 10), Seq(100, 4, 10))
seqs: scala.collection.immutable.Set[Seq[Int]] = Set(List(100, 4, 10), List(1, 2), List(8, 9, 10), List(2, 3, 100), List(5, 6, 7, 8))
scala> combineSequences( seqs )
res11: Set[Seq[Int]] = Set(List(5, 6, 7, 8, 8, 9, 10), List(1, 2, 2, 3, 100, 100, 4, 10))