CODEWITHSUNDEEP
scalalistscala-collections
Michael
Michael

Reputation: 42050

Drop a given number of positive items of a given list

Suppose I need a function List[Int] => Option[List[Int]] to drop exactly n elements of a given list if and only if all of them > 0. If the list size <= n the function should return None.

For instance:

def posn(n: Int): List[Int] => Option[List[Int]] = ???
val pos4: List[Int] => Option[List[Int]] = posn(4)

scala> pos4(Nil)
res18: Option[List[Int]] = None

scala> pos4(List(-1))
res19: Option[List[Int]] = None

scala> pos4(List(-1, 2, 3))
res20: Option[List[Int]] = None

scala> pos4(List(1, 2, 3))
res21: Option[List[Int]] = None

scala> pos4(List(1, 2, 3, 4, 5))
res22: Option[List[Int]] = Some(List(5))

scala> pos4(List(1, 2, 3, -4, 5))
res23: Option[List[Int]] = None

I am writing posn like that:

def posn(n: Int): List[Int] => Option[List[Int]] = xs => 
  if (xs.size >= n && xs.take(n).forall(_ > 0)) Some(xs.drop(n)) else None

This function seems working bit it doesn't seem elegant and idiomatic. How would you re-write it ?

Upvotes: 2

Views: 91

Answers (4)

Tzach Zohar
Tzach Zohar

Reputation: 37832

Another (non-recursive) alternative: use zipWithIndex and dropWhile to drop the first N positive numbers, and then check head to see whether the first remaining item is exactly at position n: if it is, we got what we want, otherwise we can return None:

def posn(n: Int): List[Int] => Option[List[Int]] = xs =>
  Some(xs.zipWithIndex.dropWhile { case (v, i) => v > 0 && i < n })
    .find(_.headOption.exists(_._2 == n)) // first index should be n 
    .map(_.map(_._1)) // remove indices

Upvotes: 1

Lee
Lee

Reputation: 144136

I would write a generic version and use that to define posn:

def dropWhen[T](n: Int, p: T => Boolean, l: List[T]): Option[List[T]] = {
    val (f, s) = l.splitAt(n)
    if (f.length >= n && f.forall(p)) { Some(s) } else { None }
}

def posn(n: Int): List[Int] => Option[List[Int]] = l => dropWhen(n, (i : Int) => i > 0, l)

Note this method scans the prefix of length n twice

Upvotes: 2

Cyrille Corpet
Cyrille Corpet

Reputation: 5315

I don't know if there is an idiomatic or elegant way to do this. There seems to be no generic pattern that can be extracted from your logic, except what you have already done (using drop and take), so I don't believe you will find some more useful predefined method

However, you are traversing your list a few times, and this could be avoided:

def posn(n: Int): List[Int] => Option[List[Int]] = xs => {
  val (head, tail) = xs.splitAt(n) //does take and drop in one run
  if (head.lengthCompare(n) == 0 && head.forall(_ > 0)) Some(tail) // lengthCompare does not compute the whole length if there is no need to
  else None 
}

This is still not perfect, and more verbose than your version.

You could also do all of it at once, with tail recursion (here assuming n>=0):

def posn(n: Int): List[Int] => Option[List[Int]] = xs =>
  if (n == 0) Some(xs) 
  else if (xs.isEmpty || xs.head <= 0) None
  else posn(n - 1)(xs.tail)

This would be more efficient if List was naively implemented, but I really doubt you will see any improvement.

Upvotes: 2

Tzach Zohar
Tzach Zohar

Reputation: 37832

Here's an (arguably) more idiomatic implementation using Pattern Matching and a recursive call to posn - but I'm not sure it's preferable to your suggested implementation:

def posn(n: Int): List[Int] => Option[List[Int]] = xs => (n, xs) match {
  case (0, _) => Some(xs) // stop if enough objects dropped
  case (_, head :: tail) if head > 0 => posn(n - 1)(tail) // drop positive and move on
  case _ => None // found a negative item or end of xs => "fail"
}

Upvotes: 4

Related Questions