Find all subsequences in the sequence

Nikita Zonov — Fri, 16 Aug 2019 09:26:34 +0000

Let's start with the signature of our function

def groupSubseq[T](in: Seq[T])(p: (T, T) => Boolean): Seq[Seq[T]]

Here p is predicate we use before add item to the existing subseq or create new one

We are going to use foldLeft

def groupSubseq[T](in: Seq[T])(p: (T, T) => Boolean): Seq[Seq[T]] = in
  .foldLeft(Seq.empty[Seq[T]])((seq, item) => seq match {
    case Nil => Seq(Seq(item)) // processing first element
    case currentSeq +: tail =>
      if (p(currentSeq.head, item)) {
        // new element satisfies the condition, add it to the subsequence
        (item +: currentSeq) +: tail 
      } else {
        // new element not satisfies the condition, start new subsequence
        Seq(item) +: seq
      }
  })

Looks like we've done here. But let me explain ))... This post is a result of a few similar tasks I've faced recently.

Task 1

Find all the sequences of the same character in the given string and count number of the character in each sequence

def countChar(seq: String): Seq[Char, Int] = ???

val test1 = "aaabbaaaabbb"

countChar(test1)

//res0: List((a,3), (b,2), (a,4), (b,3))

Task 2

Count number of all the sequences of the same sign in the given sequence of Int

def countSign(seq: Set[Int]): Int = ???

val test1 = Seq(1, 2, 3, -3, -2, 6, 7, 8, 9, -3, -1, -6, 7)

countSign(test1)

//res0: 3

Using our recent invention we may solve it easily

def countChar(seq: String) =
  groupSubseq(seq)(_ == _).map(seq => seq.head -> seq.length).reverse

countChar("aaabbaaacddddd")

// res0: Seq[(Char, Int)] = List((a,3), (b,2), (a,3), (c,1), (d,5))


def countSign(seq: Seq[Int]) = groupSubseq(seq)(_ * _ > 0).count(_.length > 2)

countSign(Seq(1, 2, 3, 4, -1, 1, -1, -2, -3, -4, 0, 0, 0))

// res1: Int = 2

I hope to see your pros and cons in the comments. Thanks for reading.

Count the number of identical objects in List[_]

Nikita Zonov — Thu, 17 May 2018 06:10:18 +0000

Let's assume we have a list of objects


case class Cake(id: Int, name: String, expired: Long)

val l = List(Cake(1,"keks"), Cake(1,"keks"), Cake(1,"keks"), Cake(4,"pie"))

start to count

l.groupBy(_.id).map(pair => (pair._1, pair._2.length))

// res0: scala.collection.immutable.Map[Int,Int] = Map(4 -> 1, 1 -> 3)

good, but what if we wanna get all object as a key

l.groupBy(_.id)
  .map({
    case (_, items) => items.head -> items.length
  })

// res1: scala.collection.immutable.Map[Cake,Int] = Map(Cake(4,pie) -> 1, Cake(1,keks) -> 3)

Match better. When pull request with this code come to review I get comment from my colleague

head is not safety so it's bad

So, we need to change it

l.groupBy(_.id)
  .map({
    case (_, items) => items.headOption.map(_ -> items.length)
  })
// res2: scala.collection.immutable.Iterable[Option[(Cake, Int)]] = List(Some((Cake(4,pie),1)), Some((Cake(1,keks),3)))

And then beautiful trick with List[Option[_]]

l.groupBy(_.id)
  .map({
    case (_, items) => items.headOption.map(_ -> items.length)
  }).flatten

//res3: scala.collection.immutable.Iterable[(Cake, Int)] = List((Cake(4,pie),1), (Cake(1,keks),3))

finishing touch

l.groupBy(_.id)
  .flatMap({
    case (_, items) => items.headOption.map(_ -> items.length)
  })

//res4: scala.collection.immutable.Iterable[(Cake, Int)] = List((Cake(4,pie),1), (Cake(1,keks),3))

Question: Do you agree with my colleague opinion?

Forem: Nikita Zonov

Find all subsequences in the sequence

Count the number of identical objects in List[_]