scala - Getting a read-only sublist view of a List

Question

I would like a List, Seq, or even an Iterable that is a read-only view of a part of a List, in my specific case, the view will always start at the first element.

List.slice, is O(n) as is filter. Is there anyway of doing better than this - I don't need any operations like +, - etc. Just apply, map, flatMap, etc to provide for list comprehension syntax on the sub list.

Is the answer to write my own class whose iterators keep a count to know where the end is?

Answer 1

How about Stream? Stream is Scala's way to laziness. Because of Stream's laziness, Stream.take(), which is what you need in this case, is O(1). The only caveat is that if you want to get back a List after doing a list comprehension on a Stream, you need to convert it back to a List. List.projection gets you a Stream which has most of the opeations of a List.

scala> val l = List(1, 2, 3, 4, 5)
l: List[Int] = List(1, 2, 3, 4, 5)

scala> val s = l.projection.take(3)
s: Stream[Int] = Stream(1, ?)

scala> s.map(_ * 2).toList
res0: List[Int] = List(2, 4, 6)

scala> (for (i <- s) yield i * 2).toList
res1: List[Int] = List(2, 4, 6)

Answer 2

List.slice and List.filter both return Lists -- which are by definition immutable.The + and - methods return a different List, they do not change the original List. Also, it is hard to do better than O(N). A List is not random access, it is a linked list. So imagine if the sublist that you want is the last element of the List. The only way to access that element is to iterate over the entire List.