Function takes two List[Int] arguments and produces a List[Int]. SCALA

Question

The elements of the resulting list should alternate between the elements of the arguments. Assume that the two arguments have the same length.

USE RECURSION

My code as follows

val finalString = new ListBuffer[Int]
val buff2= new ListBuffer[Int]
def alternate(xs:List[Int], ys:List[Int]):List[Int] = {
    while (xs.nonEmpty) {
        finalString += xs.head + ys.head
        alternate(xs.tail,ys.tail)
    }
    return finalString.toList
}

EXPECTED RESULT:

alternate ( List (1 , 3, 5) , List (2 , 4, 6)) = List (1 , 2, 3, 4, 6)

As far for the output, I don't get any output. The program is still running and cannot be executed.

Are there any Scala experts?

Maybe alternate ( List (1 , 3, 5) , List (2 , 4, 6)) = List (1 , 2, 3, 4, **5**, 6)? — Dmytro Mitin, Apr 06 '19 at 10:25

Dima · Answer 1 · 2019-04-06T13:52:45.067

4

There are a few problems with the recursive solutions suggested so far (including yours, which would actually work, if you replace while with if): appending to end of list is a linear operation, making the whole thing quadratic (taking a .length of a list too, as well ас accessing elements by index), don't do that; also, if the lists are long, a recursion may require a lot of space on the stack, you should be using tail-recursion whenever possible.

Here is a solution that is free of both those problems: it builds the output backwards, by prepending elements to the list (constant time operation) rather than appending them, and reverses the result at the end. It is also tail-recursive: the recursive call is the last operation in the function, which allows the compiler to convert it into a loop, so that it will only use a single stack frame for execution regardless of the size of the lists.

  @tailrec
  def alternate(
    a: List[Int], 
    b: List[Int], 
    result: List[Int] = Nil
  ): List[Int] = (a,b) match {
    case (Nil, _) | (_, Nil) => result.reversed
    case (ah :: at, bh :: bt) => alternate(at, bt, bh :: ah :: result)
  }

(if the lists are of different lengths, the whole thing stops when the shortest one ends, and whatever is left in the longer one is thrown out. You may want to modify the first case (split it into two, perhaps) if you desire a different behavior).

BTW, your own solution is actually better than most suggested here: it is actually tail recursive (or rather can be made one if you add else after your if, which is now while), and appending to ListBuffer isn't actually as bad as to a List. But using mutable state is generally considered "code smell" in scala, and should be avoided (that's one of the main ideas behind using recursion instead of loops in the first place).

edited Apr 06 '19 at 13:52

answered Apr 06 '19 at 11:49

Dima

39,570
6
44
70

Better to put the recursive function inside a wrapper function. This avoids having unnecessary parameters to the main function and makes it work as a method. – Tim Apr 06 '19 at 16:34
I verily agree that having mutable state makes code unmanageable in the long run, but that advise has a context where that state is shared with other functions. If the state is only local to a function, the function can be a pure one. In fact, various implementations of pure functions within Scala library's source code use such mutable constructs for efficiency. The immutable [List](https://github.com/scala/scala/blob/2.13.x/src/library/scala/collection/immutable/List.scala) class itself uses `ListBuffer` in various functions that we know as pure because that state is local. – Aman Agnihotri Apr 06 '19 at 17:01
@Tim I don't like unnecessary nesting, there is no point. The default value for the parameter does goo enough IMO. – Dima Apr 06 '19 at 21:51
@AmanAgnihotri mutable state is bad by itself. A shared mutable state is just (A LOT) worse. Yes, scala library code has it, and yes, sometimes your application code needs it too. It's just a good idea to avoid it until you have enough handle of the language to be able to determine for certain the cases where you need it and the exact reason _why_. Some java library code uses `goto`, that doesn't make it a good idea to use it in your application, does it? – Dima Apr 06 '19 at 21:54
Mutable state is considered "code smell" precisely because seeing it in some code makes the reader pause and wonder whether it is being shared globally, and whether it is being used correctly. It is best to avoid it for that reason alone. – Dima Apr 06 '19 at 21:58
@Dima As you imply in your remarks, sensible use of concepts is appropriate and in that case mutable state cannot be bad in itself either. That was my point which suggested that to deem mutable state as always bad undermines its legitimate use-cases as well which come from their respective contexts. My showing List class's source code was merely to bolster the claim that we must not diss on mutations in an absolute manner for the criticism of mutable state is nuanced and contextual. The same goes for goto. – Aman Agnihotri Apr 07 '19 at 00:37
The remark that the use of local mutable state can make readers pause and wonder about its use in global contexts seems contrived and does not give any consideration to the existence of lexical scoping which also dispels such doubts. The concern for "correct use" exists for immutable constructs as well. – Aman Agnihotri Apr 07 '19 at 00:38
This code conflicts with SOLID principles. Specifically, it violates the DIP because the abstraction `alternate` should not depend on the details of a particular implementation. And remember that your code may not compile if used as a method. – Tim Apr 07 '19 at 07:08
@Tim it does compile. Just needs to be `final`. As for the "principles" ... My goals when writing code are for it to be readable, reliable, maintainable and performant, not to satisfy some abstract principles with cryptic abbreviations. And no, the "abstraction" does not depend on "implementation". – Dima Apr 07 '19 at 12:10
@AmanAgnihotri I am sorry if some of my remarks "seem contrived" to you. I assure you they are really not. Lexical scoping can indeed make the problem somewhat better, but it won't prevent it from being a problem. If you don't use mutable state, you don't need lexical scoping to make your code easy to reason about. – Dima Apr 07 '19 at 12:12

score 2 · Answer 2 · answered Apr 06 '19 at 10:29

2

Condition xs.nonEmpty is true always so you have infinite while loop.

Maybe you meant if instead of while.

answered Apr 06 '19 at 10:29

Dmytro Mitin

48,194
3
28
66

Yes, I'm learning Scala right now and switching from Java. Scala is really great and easy language, but with the semantics of this language I got confused. – oohar Apr 06 '19 at 22:13

sachav · Answer 3 · 2019-04-06T11:10:25.933

2

A more Scala-ish approach would be something like:

def alternate(xs: List[Int], ys: List[Int]): List[Int] = {
  xs.zip(ys).flatMap{case (x, y) => List(x, y)}
}

alternate(List(1,3,5), List(2,4,6))
// List(1, 2, 3, 4, 5, 6)

edited Apr 06 '19 at 11:10

answered Apr 06 '19 at 11:04

sachav

1,316
8
11

Tim · Answer 4 · 2019-04-06T12:54:17.953

A recursive solution using match

def alternate[T](a: List[T], b: List[T]): List[T] =
  (a, b) match {
    case (h1::t1, h2::t2) =>
      h1 +: h2 +: alternate(t1, t2)
    case _ =>
      a ++ b
  }

This could be more efficient at the cost of clarity.

Update

This is the more efficient solution:

def alternate[T](a: List[T], b: List[T]): List[T] = {
  @annotation.tailrec
  def loop(a: List[T], b: List[T], res: List[T]): List[T] =
    (a, b) match {
      case (h1 :: t1, h2 :: t2) =>
        loop(t1, t2, h2 +: h1 +: res)
      case _ =>
        a ++ b ++ res.reverse
    }

  loop(a, b, Nil)
}

This retains the original function signature but uses an inner function that is an efficient, tail-recursive implementation of the algorithm.

senjin.hajrulahovic · Answer 5 · 2019-04-06T10:42:37.210

You're accessing variables from outside the method, which is bad. I would suggest something like the following:

object Main extends App {
    val l1 = List(1, 3, 5)
    val l2 = List(2, 4, 6)

    def alternate[A](l1: List[A], l2: List[A]): List[A] = {
        if (l1.isEmpty || l2.isEmpty) List()
        else List(l1.head,l2.head) ++ alternate(l1.tail, l2.tail)
    }

    println(alternate(l1, l2))
}

Still recursive but without accessing state from outside the method.

Aman Agnihotri · Answer 6 · 2019-04-06T18:23:49.613

Assuming both lists are of the same length, you can use a ListBuffer to build up the alternating list. alternate is a pure function:

import scala.collection.mutable.ListBuffer

object Alternate extends App {
  def alternate[T](xs: List[T], ys: List[T]): List[T] = {
    val buffer = new ListBuffer[T]

    for ((x, y) <- xs.zip(ys)) {
      buffer += x
      buffer += y
    }

    buffer.toList
  }

  alternate(List(1, 3, 5), List(2, 4, 6)).foreach(println)
}

Function takes two List[Int] arguments and produces a List[Int]. SCALA

USE RECURSION

EXPECTED RESULT:

Are there any Scala experts?

6 Answers6