CODEWITHSUNDEEP
listscala
disshethard
disshethard

Reputation: 83

Split a list into half by even and odd indexes? TailRecursive + match

Define a tail recursive function:def divide[A](l: List[A]): (List[A], List[A]) that will split the list into two. In the first, there will be elements on even indexes, in the second, there will be elements on odd indexes. for List (1, 3, 5, 6, 7), the function should return: (List (1, 5, 7), List (3, 6)).

import scala.annotation.tailrec
object Main extends App {
  def divide[A](l: List[A]): (List[A], List[A]) = {
    @tailrec
    def helper(l1: List[A], l2: List[A]) = {
      ... match {
      case

Any help would be great, i dont even know how to start, because i cant simply use x % 2 == 0 with case..

Upvotes: 2

Views: 835

Answers (2)

Tomer Shetah
Tomer Shetah

Reputation: 8529

Another option you have, which is not a tailrec, but does not reverse the list, is:

def divide[A](l: List[A]): (List[A], List[A]) = {
  def helper(l: List[A]): (List[A], List[A]) = l match {
    case Nil => (Nil, Nil)
    case head :: Nil => (List(head), Nil)
    case even :: odd :: rest =>
      val (evenList, oddList) = helper(rest)
      (even :: evenList, odd :: oddList)
  }

  helper(l)
}

Code run at Scastie.

If you'd like to do that in the functional way, you can do:

val (evenWithIndex, oddWithIndex) = List(1, 3, 5, 6, 7).zipWithIndex.partition(_._2 % 2 == 0)
val even = evenWithIndex.map(_._1)
val odd = oddWithIndex.map(_._1)

Upvotes: 1

Swapan Pramanick
Swapan Pramanick

Reputation: 175

Maybe you could think of the base case first - A list with one element. In that case, you need to put that in the list of odd indices. If you have more elements, you need to call the same method, but for the second call, you need to put the element in the list of event indices.

Also, you may notice that, if you have an odd number of elements in the list, you have more numbers in the list of odd indices than that of the even. In case if you have an even number of elements, you have an equal number of elements in both lists. So you may think of a function like below,

import scala.annotation.tailrec
def divide[A](l: List[A]): (List[A], List[A]) = {
    @tailrec
    def helper(l: List[A], list1:List[A], list2:List[A]):(List[A], List[A]) = {
        l match {
            case Nil if list1.size > list2.size => (list1.reverse, list2.reverse) // case 1: odd number of elements
            case Nil if list1.size < list2.size => (list2.reverse, list1.reverse) // case 2: odd number of elements
            case Nil if list1.size == list2.size => (list1.reverse, list2.reverse) // case 3: even number of elements
            case head::tail => helper(tail, list2, head::list1) 
        }
    }
    helper(l, List(), List())
}

Now if you see closely, case 1 never occurs as we are swapping the positions of the lists of the odd and even indices. So, we can remove this.

import scala.annotation.tailrec
def divide[A](l: List[A]): (List[A], List[A]) = {
    @tailrec
    def helper(l: List[A], list1:List[A], list2:List[A]):(List[A], List[A]) = {
        l match {
            case Nil if list1.size < list2.size  => (list2.reverse, list1.reverse) // case 1: odd number of elements
            case Nil                             => (list1.reverse, list2.reverse) // case 2: even number of elements
            case head::tail                      => helper(tail, list2, head::list1) 
        }
    }
    helper(l, List(), List())
}

Update

Based on the comment by @Dima, I have removed the extra check from the second case. Also, the code based on the approach he mentioned is,

import scala.annotation.tailrec
def divide[A](l: List[A]): (List[A], List[A]) = {
    @tailrec
    def helper(l: List[A],
            i: Int,
            result:(List[A], List[A])):(List[A], List[A]) = l match {
        case Nil  => (result._1.reverse, result._2.reverse)
        case head::tail if i%2 == 0 => helper(tail, (i+1), (head::result._1, result._2))
        case head::tail => helper(tail, (i+1), (result._1, head::result._2)) 
    }
    helper(l, 0, (List(), List()))
}

Upvotes: 0

Related Questions