Appending lists in the standard library

[phischu]

Extracted from a discussion in #830

The implementation of append in the list module reverses stuff twice instead of doing the naive thing:

def append[A](l: List[A], other: List[A]): List[A] = l match {
  case Nil() => other
  case Cons(a, rest) => Cons(a, append(rest, other))
}

This implementation is faster on the LLVM backend but slower on the JS backend for the following program:

def main() = {
  val l1 = fill(100000, 1)
  val l2 = l1.append(l1).append(l1).append(l1).append(l1)
  println(l2.sum)
}

[jiribenes]

I'm for adding the main here as a microbenchmark with the given append defined in the same file and seeing where that goes :)

[jiribenes]

Question:

Should we then also change map and other list function functions to be the "simple" implementation?

def map[A, B](l: List[A]) { f: A => B } : List[B] = l match {
  case Nil() => Nil()
  case Cons(a, as) => Cons(f(a), l.map {f})
}

(or the variant with an accumulator?)

For reference, currently it's:

def map[A, B](l: List[A]) { f: A => B } : List[B] = {
  var acc = Nil[B]()
  l.foreach { el => acc = Cons(f(el), acc) }
  acc.reverse
}

(so the list is iterated over twice)

[b-studios]

Ultimately yes, but I would wait with it