Scala - Use predicate function to summarize list of strings

user_6382162 0
Viewed 66

I need to write a function to analyze some text files. For that, there should be a function that splits the file via a predicate into sublists. It should only get the values after the first time the predicate evaluates to True and afterwards start a new sublist after the predicate was True again.
For Example:
List('ignore','these','words','x','this','is','first','x','this','is','second')
with predicate
x=>x.equals('x')
should produce
List(List('this','is','first'),List('this','is','second'))

I've already done the reading of the file into a List[String] and tried to use foldLeft with a case statement to iterate over the List.

words.foldLeft(List[List[String]]()) {
      case (Nil, s) => List(List(s))
      case (result, "x") => result :+ List()
      case (result, s) => result.dropRight(1) :+ (result.last :+ s)
    }

There are 2 problems with this though and I can't figure them out:

  • This does not ignore the words before the first time the predicate evaluates to True
  • I can't use an arbitrary predicate function

If anyone could tell me what I have to do to fix my problems it would be highly appreciated.

scala functional-programming
2 Answers

I modified your example a little bit:

def foldWithPredicate[A](predicate: A => Boolean)(l: List[A]) =
  l.foldLeft[List[List[A]]](Nil){
      case (acc, e) if predicate(e) => acc :+ Nil //if predicate passed add new list at the end
      case (Nil, _) => Nil //empty list means we need to ignore elements
      case (xs :+ x, e) => xs :+ (x :+ e) //append an element to the last list
  }

val l = List("ignore","these","words","x","this","is","first","x","this","is","second")
val predicate: String => Boolean = _.equals("x")

foldWithPredicate(predicate)(l) // List(List(this, is, first), List(this, is, second))

There's one problem performance related to your approach: appending is very slow on immutable lists. It might be faster to prepend elements on the list, but then, of course, all lists will have elements in reversed order (but they could be reversed at the end).

def foldWithPredicate2[A](predicate: A => Boolean)(l: List[A]) =
  l.foldLeft[List[List[A]]](Nil){
      case (acc, e) if predicate(e) => Nil :: acc
      case (Nil, _) => Nil
      case (x :: xs, e) => (e :: x) :: xs
  }.map(_.reverse).reverse
user_13033240

An alternative approach is to use span to split the items into the next sublist and the rest in a single call. The following code assumes Scala 2.13 for List.unfold:

def splitIntoBlocks[T](items: List[T])(startsNewBlock: T => Boolean): List[List[T]] = {
  def splitBlock(items: List[T]): (List[T], List[T]) = items.span(!startsNewBlock(_))

  List.unfold(splitBlock(items)._2) {
    case blockIndicator :: rest => Some(splitBlock(rest))
    case _ => None
  }
}

And the usage:

scala> splitIntoBlocks(List(
  "ignore", "these", "words",
  "x", "this", "is", "first",
  "x", "this", "is", "second")
)(_ == "x")

res0: List[List[String]] = List(List(this, is, first), List(this, is, second))
user_10982300
Related