CODEWITHSUNDEEP
scalacollections
Marcin
Marcin

Reputation: 4289

How to elegantly extract range of list based on specific criteria?

I want to extract range of elements from a list, meeting the following requirements:

This is very simple to program imperatively, but I am just wondering if there is some smart Scala-functional way to achieve it. Is it?

Upvotes: 3

Views: 1603

Answers (4)

Nikita Volkov
Nikita Volkov

Reputation: 43310

Good functional algorithm design practice is all about breaking complex problems into simpler ones. The principle is called Divide and Conquer.

It's easy to extract two simpler subproblems from the subject problem:

  1. Get a list of all elements after the matching one, preceded with this matching element, preceded with an element before it.

  2. Get a list of all elements up to the latest matching one, followed by the matching element and the element after it.

The named problems are simple enough for the appropriate functions to be implemented, so no subdivision is required.

Here's the implementation of the first function:

def afterWithPredecessor
  [ A ]
  ( elements : List[ A ] )
  ( test : A => Boolean ) 
  : List[ A ] 
  = elements match {
      case Nil => Nil
      case a :: tail if test( a ) => Nil // since there is no predecessor
      case a :: b :: tail if test( b ) => a :: b :: tail
      case a :: tail => afterWithPredecessor( tail )( test )
    }

Since the second problem can be seen as a direct inverse of the first one, it can be easily implemented by reversing the input and output:

def beforeWithSuccessor
  [ A ]
  ( elements : List[ A ] )
  ( test : A => Boolean ) 
  : List[ A ] 
  = afterWithPredecessor( elements.reverse )( test ).reverse

But here's an optimized version of this:

def beforeWithSuccessor
  [ A ]
  ( elements : List[ A ] )
  ( test : A => Boolean ) 
  : List[ A ] 
  = elements match {
      case Nil => Nil
      case a :: b :: tail if test( a ) => 
        a :: b :: beforeWithSuccessor( tail )( test )
      case a :: tail => 
        beforeWithSuccessor( tail )( test ) match {
          case Nil => Nil
          case r => a :: r
        }
    }

Finally, composing the above functions together to produce the function solving your problem becomes quite trivial:

def range[ A ]( elements : List[ A ] )( test : A => Boolean ) : List[ A ] 
  = beforeWithSuccessor( afterWithPredecessor( elements )( test ) )( test )

Tests:

scala> range( List(1,1,1,10,2,10,1,1,1) )( _ >= 10 )
res0: List[Int] = List(1, 10, 2, 10, 1)

scala> range( List(1,1,1,10,2,10,1,1,1) )( _ >= 1 )
res1: List[Int] = List()

scala> range( List(1,1,1,10,2,10,1,1,1) )( _ == 2 )
res2: List[Int] = List(10, 2, 10)

The second test returns an empty list since the outermost elements satisfying the predicate have no predecessors (or successors).

Upvotes: 2

itsbruce
itsbruce

Reputation: 4843

Zip and map to the rescue

val l = List(1, 1, 1, 10, 2, 1, 1, 1)

def test (i: Int) = i >= 10

((l.head :: l) zip (l.tail :+ l.last)) zip l filter {
  case ((a, b), c) => (test (a) || test (b) || test (c) )
} map { case ((a, b), c ) => c }

That should work. I only have my smartphone and am miles from anywhere I could test this, so apologise for any typos or minor syntax errors

Edit: works now. I hope it's obvious that my solution shuffles the list to the right and to the left to create two new lists. When these are zipped together and zipped again with the original list, the result is a list of tuples, each containing the original element and a tuple of its neighbours. This is then trivial to filter and map back to a simple list.

Making this into a more general function (and using collect rather than filter -> map)...

def filterWithNeighbours[E](l: List[E])(p: E => Boolean) = l match {
  case Nil => Nil
  case li if li.size < 3 => if (l exists p) l else Nil
  case _ => ((l.head :: l) zip (l.tail :+ l.last)) zip l collect {
    case ((a, b), c) if (p (a) || p (b) || p (c) ) => c
  }
}

This is less efficient than the recursive solution but makes the test much simpler and more clear. It can be difficult to match the right sequence of patterns in a recursive solution, as the patterns often express the shape of the chosen implementation rather than the original data. With the simple functional solution, each element is clearly and simply being compared to its neighbours.

Upvotes: 1

drexin
drexin

Reputation: 24423

Keeping it in the scala standard lib, I would solve this using recursion:

def f(_xs: List[Int])(cond: Int => Boolean): List[Int] = {
  def inner(xs: List[Int], res: List[Int]): List[Int] = xs match {
    case Nil => Nil
    case x :: y :: tail if cond(y) && res.isEmpty => inner(tail, res ++ (x :: y :: Nil))
    case x :: y :: tail if cond(x) && res.nonEmpty => res ++ (x :: y :: Nil)
    case x :: tail if res.nonEmpty => inner(tail, res :+ x)
    case x :: tail => inner(tail, res)
  }

  inner(_xs, Nil)
}

scala> f(List(1,1,1,10,2,10,1,1,1))(_ >= 10)
res3: List[Int] = List(1, 10, 2, 10, 1)

scala> f(List(2,10,2,10))(_ >= 10)
res4: List[Int] = List()

scala> f(List(2,10,2,10,1))(_ >= 10)
res5: List[Int] = List(2, 10, 2, 10, 1)

Maybe there is something I did not think of in this solution, or I missunderstood something, but I think you will get the basic idea.

Upvotes: 3

Nami
Nami

Reputation: 1235

def range[T](elements: List[T], condition: T => Boolean): List[T] = {
   val first = elements.indexWhere(condition)
   val last  = elements.lastIndexWhere(condition)

   elements.slice(first - 1, last + 2)
}

scala> range[Int](List(1,1,1,10,2,10,1,1,1), _ >= 10)
res0: List[Int] = List(1, 10, 2, 10, 1)

scala> range[Int](List(2,10,2,10), _ >= 10)
res1: List[Int] = List(2, 10, 2, 10)

scala> range[Int](List(), _ >= 10)
res2: List[Int] = List()

Upvotes: 1

Related Questions