CODEWITHSUNDEEP
scala
johnnydas
johnnydas

Reputation: 3

scala: function which removes elements out of a list with a bigger predecessor

I want to write a tail-recursive function in scala biggerPredecessor which removes elements out of a list which have a bigger predecessor.

for example:

(1,3,2,5,7)

should result in:

(1,3,5,7)

Here is what I have so far but now I got stuck.

def biggerPredecessor(xs: List[Int]) : List[Int] = (xs) match
  {
    def finalElements(ys: List[Int], xs: List[Int]) : List[Int] = (ys, xs) match
    {
      case (Nil, x::xs) => finalElements(new List(x), xs)
      case (y::ys, x::xs) if x > y => x::xs // insert in reverse order into list
      case (y::ys, Nil) => // ...
    }
  }

Upvotes: 0

Views: 151

Answers (4)

pme
pme

Reputation: 14803

My solution would go with foldLeft:

  val seq = List(1,3,2,5,7)

  val result = seq.foldLeft(List[Int]()){
    case (Nil, x: Int) => List(x)
    case (ys, x) if x > ys.last => ys :+ x
    case (ys, x) => ys
  }

  println(result)

Here the version suggested by Luis Miguel Mejía Suárez:

 val result2 = seq.foldLeft(List.empty[Int]){
    case (Nil, x) => List(x)
    case (ys, x) if x > ys.head => x :: ys
    case (ys, x) => ys
  }.reverse

Ok, here the recursive translation suggested by jwvh:

  def biggerPredecessor(list: List[Int],
                        results: List[Int] = List.empty[Int]): List[Int] = (list, results) match {
    case (Nil, _) => results.reverse
    case (x::xs, Nil) => biggerPredecessor(xs, List(x))
    case (x::xs, y::_) if x > y => biggerPredecessor( xs,x :: results)
    case (_::xs, _) => biggerPredecessor(xs, results)
  }

  println(biggerPredecessor(seq))

This needs one more case, when the list is done.

You can paste this in Scalafiddle and check yourself.

Upvotes: 2

Bogdan Vakulenko
Bogdan Vakulenko

Reputation: 3390

if you just need non-recursive solution then here it is:

def biggerPredecessor(ls: List[Int]) =
  ls.take(1) ++ ls
    .zip(ls.drop(1))
    .collect {
      case (l,r) if !(l>r) => r
    }

Upvotes: 1

ygor
ygor

Reputation: 1756

I am a big fan of the sliding function:

def biggerPredecessor(xs: List[Int]) : List[Int] =
  (null.asInstanceOf[Int] :: xs) // null is the sentinel, because first item is always included
    .sliding(2)
    .flatMap {
      case List(a,b) => if (a > b) None else Some(b)
      case List(_) => None // special handling for empty xs
    }
    .toList


println(biggerPredecessor(List()))
println(biggerPredecessor(List(1)))
println(biggerPredecessor(List(1,2)))
println(biggerPredecessor(List(2,1)))
println(biggerPredecessor(List(1,3,2,5,7)))

ScalaFiddle

Upvotes: 0

hasumedic
hasumedic

Reputation: 2167

You could do something like this:

def biggerPredecessor(xs: List[Int]): List[Int] = {
    @tailrec
    def finalElements (xs: List[Int], acc: List[Int] ): List[Int] = xs match {
        case Nil => acc
        case head :: tail => finalElements(tail, if(acc.headOption.getOrElse(0) > head) acc else head :: acc)
    }

    finalElements(xs, List.empty[Int]).reverse
}

Or a bit more concise, using foldLeft:

foldLeft(List.empty[Int])((acc, elem) => if(acc.lastOption.getOrElse(0) > elem) acc else acc :+ elem))

Upvotes: 2

Related Questions