Scala: Append element to list using cons method

Question

While reading Programming in Scala, 3rd Edition, it says

Class List does offer an "append" operation—it's written :+ But this operation is rarely used, because the time it takes to append to a list grows linearly with the size of the list, whereas prepending with :: takes constant time.

If you want to build a list efficiently by appending elements, you can prepend them and when you're done call reverse.

I am trying to understand, what is Scala idiomatic way of doing this? Is calling List.reverse twice acceptable and efficient vs ListBuffer (since ListBuffer is mutable)?

// Scala Recommended way - but reverse twice?
val alist = List("A", "B")
// cons is O(1)
// This will print (A, B, C)
println(("C" :: alist.reverse).reverse)

// Scala also Recommended: Use ListBuffer
val alb = ListBuffer("A", "B")
alb.append("C")
val clist2 = alb.toList
// This will print (A, B, C)
println(clist2)

// DO NOT do this, its O(n)

val clist3 = alist :+ "C"
// This will print (A, B, C)
println(clist3)

P.S: I'm not referring to code optimization here. Which one is generally recommended and will not received WTH expression.

I moved from java to scala 8 months ago. The code I wrote in the first 6 months is loaded with mutable collections. Now I never use them and care deeply about performance. Once you are runing seriously big data you will see why for yourself. Its a self-discovery project. For now, trust the documents. :) — Jake, Jun 30 '18 at 14:42
I am a bit confused by your comment above the third code snippet. What do you mean by "DO NOT do this, its O(n)"? All three snippets are O(n). `List.reverse` is O(n) and `ListBuffer.toList` is O(n) and `List.:+` is O(n). — Jörg W Mittag, Jun 30 '18 at 14:57
@JörgWMittag I think `ListBuffer.toList` is actually constant time (unless you re-use the ListBuffer after converting it toList) — joel, Jun 30 '18 at 14:59
@joelb: You're right. Interesting. So, mutating the buffer after calling toList will trigger an O(n) copy lazily, but the original call is O(1). Clever. — Jörg W Mittag, Jun 30 '18 at 15:06
This has the answer for all of it. https://docs.scala-lang.org/overviews/collections/performance-characteristics.html — Shankar Shastri, Jun 30 '18 at 15:38
[this](https://stackoverflow.com/questions/1241166/preferred-way-to-create-a-scala-list) may help — joel, Jun 30 '18 at 17:04
@JoelBerkeley Thank You. that link helps and answered my question. — rohitmohta, Jun 30 '18 at 21:09

score 0 · Answer 1 · answered Sep 06 '19 at 04:26

Another implementation could be Difference Lists (also Prolog-based explanation available - Understanding Difference Lists).

That's how I implement DList in Scala:

abstract class DiffList[A](calculate: List[A] => List[A]) {
  def prepend(s: List[A]): DiffList[A]

  def append(s: List[A]): DiffList[A]

  def result: List[A]
}

final class DiffListImpl[A](listFunc: List[A] => List[A])
    extends DiffList[A](listFunc) {
  def prepend(s: List[A]): DiffListImpl[A] =
    new DiffListImpl[A](listFunc andThen (s ++ _))


  def append(s: List[A]): DiffListImpl[A] =
    new DiffListImpl[A](listFunc andThen (_ ++ s))

  def result: List[A] = listFunc(Nil)
}

And use it:

val l1 = List(1, 2)
val l2 = List(6, 7)
val l3 = List(3, 4, 5)
val dl = new DiffListImpl[Int](Nil)

val result = dl.prepend(l1).prepend(l2).append(l3).result

Result: List(6, 7, 1, 2, 3, 4, 5)

Difference list optimizes a large number of concatenation operations of small lists, so the `append` body should be `new DiffListImpl[A](listFunc compose (s ++ _))` for efficiency. — Vadim Shender, Sep 03 '20 at 23:43

Scala: Append element to list using cons method

1 Answers1