Extract areas from a Scala array

Question

I don’t know how to describe what I am doing, but this example should help:

val vals = Array( (0, true), (1, true), (2,true), (3,true), (4,false), (5, true), (6, true), (7, false), (8, true), (9,true)) 

I am looking to identify the first and last elements in each of the “true” areas, although breaking the array when cost changes can also work. I could do it imperatively, but what is the best way to do this in scala?

Answer 1

If you don't mind adding some infrastructure to handle the groupedWhile function, you can steal from Rex Kerr the answer to the scala collection extension . Use the section that processes the array in the second part of the answer.

Then this is a breeze:

 scala> vals.groupedWhile(_._2 == _._2).filter(_.head._2 == true).map{g => (g.head, g.last)}.foreach(println) ((0,true),(3,true)) ((5,true),(6,true)) ((8,true),(9,true)) 

Edit:

I came up with a solution that does not require groupedWhile . It is based on using Iterator.iterate , which starts with a seed and re-uses the span function to retrieve the next group of elements that have the same logical property. In this case, the seed is a tuple of the following group, and the rest is processed:

 type Arr = Array[(Int, Boolean)] // type alias for easier reading val res = Iterator.iterate[(Arr, Arr)]((Array(), vals)){ case (same, rest) => // repeatedly split in (same by boolean, rest of data) // by using span and comparing against head rest.span(elem => elem._2 == rest.head._2) }.drop(1).takeWhile{ case (same, _) => // drop initial empty seed array same.nonEmpty // stop when same becomes empty }.collect{ case (same, _) if same.head._2 == true => // keep "true" groups and extract (first, last) (same.head, same.last) }.foreach(println) // print result 

Which prints the same result as above. Note that the span for empty arrays does not raise a predicate, so we don't get an exception on rest.head if the remainder is empty.

Answer 2

Well, there are a lot of questions about list partitions in sublists. They are usually recursive, although iterative solutions exist. Once you do this, getting the first and last is trivial.

In this particular case, since you discard all signatures false , you can specialize. For instance:

 def regions(l: Seq[(Int, Boolean)]): Seq[(Int, Int)] = if (l.isEmpty) Seq.empty else if (!l.head._2) regions(l dropWhile (!_._2)) else { val (first, rest) = l span (_._2) (first.head._1, first.last._1) +: regions(rest) } 

Iteratively, I would probably use unfold from Scalaz. The code looks something like this:

 def regions(l: Seq[(Int, Boolean)]): Seq[(Int, Int)] = { l.unfold[Seq, (Int, Int)] { ll => val tl = ll dropWhile (!_._2) if (tl.isEmpty) None else { val (first, rest) = tl span (_._2) Some(((first.head._1, first.last._1), rest)) } } } 

Answer 3

For a non-recursive solution, you can do this:

 val ss = (0, false) +: vals :+ (0, false) sliding 2 toList val starts = ss filter (i => !i(0)._2 && i(1)._2) map (_(1)) val ends = ss filter (i => !i(1)._2 && i(0)._2) map (_(0)) 

which gives you lists of starting and ending elements.

For regions, you can simply archive the lists together:

 scala> starts zip ends foreach println ((0,true),(3,true)) ((5,true),(6,true)) ((8,true),(9,true)) 

Answer 4

 @tailrec def regions(l: Seq[(Int, Boolean)], nl : Seq[(Int, Int)]): Seq[(Int, Int)] = if (l.isEmpty) nl else if (!l.head._2) regions(l dropWhile (!_._2), nl) else { val (first, rest) = l span (_._2) regions(rest, (first.head._1, first.last._1) +: nl) } 

Taking Daniel's original answer and making the tail recursive.

Answer 5

Using foldLeft:

 type Region = (Int, Boolean) type RegionPair = (Region, Region) type Acc = (Option[Region], Region, List[RegionPair]) val initAcc: Acc = (None, (0, false), Nil) //optional first, dummy last, empty regions def groupRegions(s: Acc, region: Region): Acc = { val (first, last, regions) = s first match { case Some(f) => if (!region._2) (None, last, (f, last) :: regions) else (first, region, regions) case _ => (Some(region), region, regions) } } val (remFirst, remLast, regions) = (initAcc /: vals)(groupRegions) val solution = remFirst map ((_, remLast) :: regions) getOrElse regions //reverse if you want 

Answer 6

Fold Solution:

 val result = vals.foldLeft(List(List.empty[Int])) { case (head::tail, (x, true)) => (x::head)::tail case (xs, (_, false)) => Nil::xs }.map { xs => xs.head::xs.last::Nil } result: List[List[Int]] = List(List(9, 8), List(6, 5), List(3, 0)) 

every time we encounter false, we add a new new list to the drive.

The next version is even more efficient (but may not be so clear):

 val result = vals.foldLeft(List(List.empty[Int])) { case (head::tail, (x, true)) => head match { case Nil => (x::Nil)::tail case last::Nil => (x::last::Nil)::tail case first::last => (x::last)::tail } case (xs, (_, false)) => Nil::xs } result: List[List[Int]] = List(List(9, 8), List(6, 5), List(3, 0))