Cfrgtkky

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) => // ...

    }

  }

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))

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.

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

    }

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