scala: append two lists

Question

I have the following snippet of scala code:

   def append(as: List[Int], bs: List[Int]): List[Int] = as match {
      case Nil => bs
      case x::xs => x::append(xs, bs)
    }

I don't understand the x:: in the line where x::append(xs, bs) is. I know that when the list as is empty then bs will be returend (with an appended as when as was not empty before). But how does scala know in the mentioned line that is should append as to bs with x::(..,..)

The code is pretty simple. The `::` _"operator"_ _(pronounced cons. And since in Scalar there are not operators, this is really just a method on the List class)_ prepends the element of the left to the list of the right. Thus, if you try to execute the code on paper, you will see that it will perpend all elements of as to bs. — Luis Miguel Mejía Suárez, Sep 17 '19 at 11:14
OK. So x::append(xs, bs) simply means: if as is a not-empty list (min 1 element), take this element (or the head-element in case that there are more elements inside the list) and append it to bs, and also (recursively) call append(..,..) again with one element less in as. Am I right? — seas, Sep 17 '19 at 11:23
not really, you were too close. It means call append with bs and the tail of as. And peeped the head to the result. - Not this function will blow up the stack for big lists. Mario's answer should help you understand what is happening. Also, as I said, it would help if you _"execute"_ the algorithm by hand on a paper or whiteboard. — Luis Miguel Mejía Suárez, Sep 17 '19 at 12:10

Mario Galic · Answer 1 · 2019-09-17T11:59:05.733

Perhaps it would help if we desugar append a bit

def append(as: List[Int], bs: List[Int]): List[Int] = 
  as match {
    case Nil => bs
    case ::(x, xs) =>
      val list = append(xs, bs)
      list.::(x)
  }

Note how :: appears twice, however the first one in

case ::(x, xs)

is actually a case class, even though its symbolic name seems strange, and its declaration looks a bit like this

case class :: (head: A, next: List[A])

whilst, on the other hand, the second :: in

list.::(x)

is actually a right-associative method which Adds an element at the beginning of this list and looks something like so

def :: (elem: B): List[B]

Note how x :: list is equivalent to list.::(x) and not x.::(list) meaning :: is invoked on the right argument.

scala: append two lists

1 Answers1