Scala: find all chains in a list

Question

Say I have a list of items:

Seq(A, B, B, B, B, G, G, S, S, S, B, A, G)

And I want to find all the chains and get a sequence of them like so:

Seq(Seq(A), Seq(B, B, B, B), Seq(G, G), Seq(S, S, S), Seq(B), Seq(A), Seq(G))

I want to maintain order, and use a custom comparison function to decide if two objects are the "same". I'm thinking a fold or a scan may be what I need, but I'm having trouble coming up with the exact case. I'm using Scala.

EDIT: I've modified the answer from that similar question to get this:

def collapse(input: Seq[Stmt]): Seq[Seq[Stmt]] = {
    val (l, r) = input.span(_.getClass == input.head.getClass)
    l :: collapse(r)
}

Possible duplicate of [Splitting string into groups](http://stackoverflow.com/questions/5248065/splitting-string-into-groups) — Haspemulator, Nov 05 '15 at 08:09

yǝsʞǝla · Accepted Answer · 2015-11-05T09:10:37.230

Cleaner solution:

  def pack[T](input: List[T]): List[List[T]] =
    input.foldRight(Nil : List[List[T]]) ((e, accu) => accu match {
      case Nil => List(List(e))
      case curList@(h :: t) if e == h => List(e) :: curList
      case curList@(h :: t) => List(List(e)) ::: curList
  })

Not using any library functions (ugly):

  def pack[T](input: List[T]): List[List[T]] = {
    def packWithPrevious(remaining: List[T])(previous: List[T]): List[List[T]] =
      remaining match {
        case List() => List(previous)
        case head :: tail =>
          val nextIter = packWithPrevious(tail)(_)
          previous match {
            case List() => nextIter(List(head))
            case prevHead :: _ =>
              if (head != prevHead)
                previous :: nextIter(List(head))
              else
                nextIter(head :: previous)
          }
      }
    packWithPrevious(input)(List())
  }

scala> val s = List('A', 'B', 'B', 'B', 'B', 'G', 'G', 'S', 'S', 'S', 'B', 'A', 'G')
s: List[Char] = List(A, B, B, B, B, G, G, S, S, S, B, A, G)

scala> pack(s)
res2: List[List[Char]] = List(List(A), List(B, B, B, B), List(G, G), List(S, S, S), List(B), List(A), List(G))

Source: https://github.com/izmailoff/scala-s-99/blob/master/src/main/scala/s99/p09/P09.scala

Test: https://github.com/izmailoff/scala-s-99/blob/master/src/test/scala/s99/p09/P09Suite.scala

score 1 · Answer 2 · answered Nov 05 '15 at 10:28

Similar to existing answers but I find using a partial function directly in foldLeft as a clean solution:

val s = Seq("A", "B", "B", "B", "B", "G", "G", "S", "S", "S", "B", "A", "G")

s.foldLeft(Seq[Seq[String]]()) {
  case (Seq(), item) => Seq(Seq(item))
  case (head::tail, item) if head.contains(item) => (item +: head) +: tail
  case (seq, item) => Seq(item) +: seq
}.reverse

res0: Seq[Seq[String]] = List(List(A), List(B, B, B, B), List(G, G), List(S, S, S), List(B), List(A), List(G))

Nyavro · Answer 3 · 2015-11-05T09:05:03.073

0

Consider following solution:

seq.foldLeft(List(List(seq.head))) { case (acc,item)=> 
  if(acc.head.head==item) (item::acc.head)::acc.tail else List(item)::acc  
}.reverse

seq may be empty, so:

seq.foldLeft(List(seq.headOption.toList)) { case (acc,item)=> 
  if(acc.head.head==item) (item::acc.head)::acc.tail else List(item)::acc  
}.reverse

edited Nov 05 '15 at 09:05

answered Nov 05 '15 at 08:49

Nyavro

8,806
2
26
33

What happens if the `seq` is empty? – yǝsʞǝla Nov 05 '15 at 08:58
Each sublist is backwards, but I can fix that. Thanks. Also I'll add a check for empty list. – sargunv Nov 05 '15 at 09:04

score 0 · Answer 4 · answered Nov 05 '15 at 09:52

I thought groupBy would be helpful here, but my solution got slightly awkward:

val seq = Seq("A", "B", "B", "B", "B", "G", "G", "S", "S", "S", "B", "A", "G")
val parts = {
  var lastKey: Option[(Int, String)] = None
  seq.groupBy(s => {
    lastKey = lastKey.map((p: (Int, String)) =>
      if (p._2.equalsIgnoreCase(s)) p else (p._1 + 1, s)) orElse Some((0, s))
    lastKey.get
  }).toSeq.sortBy(q => q._1).flatMap(q => q._2)
}

(using equalsIgnoreCase as example for a comparision function)

Scala: find all chains in a list

4 Answers4