Preferred way to create a scala list

Question

There are several ways to construct an immutable list in scala (see contrived example code below). You can use a mutable ListBuffer, create a var list and modify it, use a tail recursive method, and probably others that I don't know about.

Instinctively, I use the ListBuffer but don't have a good reason for doing so. Is there a preferred or idiomatic method for creating a list, or are there situations that are best for one method over another?

import scala.collection.mutable.ListBuffer

// THESE are all the same as: 0 to 3 toList.
def listTestA() ={
    var list:List[Int] = Nil

    for(i <- 0 to 3) list = list ::: List(i)

    list
}


def listTestB()={
    val list = new ListBuffer[Int]()

    for (i <- 0 to 3) list += i

    list.toList
}


def listTestC() ={

    def _add(l:List[Int], i:Int):List[Int] = i match {
     case 3 => l ::: List(3)
     case _ => _add(l ::: List(i), i +1)
    }
    _add(Nil, 0)

}

Answer 1

ListBuffer is a mutable list which has constant-time append, and constant-time conversion into a List.

List is immutable and has constant-time prepend and linear-time append.

How you construct your list depends on the algorithm you'll use the list for and the order in which you get the elements to create it.

For instance, if you get the elements in the opposite order of when they are going to be used, then you can just use a List and do prepends. Whether you'll do so with a tail-recursive function, foldLeft, or something else is not really relevant.

If you get the elements in the same order you use them, then a ListBuffer is most likely a preferable choice, if performance is critical.

But, if you are not on a critical path and the input is low enough, you can always reverse the list later, or just foldRight, or reverse the input, which is linear-time.

What you DON'T do is use a List and append to it. This will give you much worse performance than just prepending and reversing at the end.

Answer 2

Uhmm.. these seem too complex to me. May I propose

def listTestD = (0 to 3).toList

or

def listTestE = for (i <- (0 to 3).toList) yield i

Answer 3

I always prefer List and I use "fold/reduce" before "for comprehension". However, "for comprehension" is preferred if nested "folds" are required. Recursion is the last resort if I can not accomplish the task using "fold/reduce/for".

so for your example, I will do:

((0 to 3) :\ List[Int]())(_ :: _)

before I do:

(for (x <- 0 to 3) yield x).toList

Note: I use "foldRight(:\)" instead of "foldLeft(/:)" here because of the order of "_"s. For a version that does not throw StackOverflowException, use "foldLeft" instead.

Answer 4

And for simple cases:

val list = List(1,2,3)

:)

Answer 5

The Scala collection classes are going to be redesigned as of Scala 2.8, so be prepared to change the way you create lists very soon.

What is the forward compatible way of creating a List? I have no idea since I haven't read the 2.8 docs yet.

A PDF document describing the proposed changes of the collection classes