0
# Backported Collections
1

2
Scala 2.13 collection types made available on Scala 2.11 and 2.12, enabling forward compatibility for code that targets multiple Scala versions.
3

4
## LazyList
5

6
A lazy, immutable linked list that evaluates elements only when needed. `LazyList` is the replacement for `Stream` in Scala 2.13+.
7

8
### LazyList Class
9

10
```scala { .api }
11
final class LazyList[+A] private (private[this] var lazyState: () => LazyList.State[A])
12
    extends AbstractSeq[A] with LinearSeq[A] with LinearSeqOptimized[A, LazyList[A]] {
13
  
14
  def head: A
15
  def tail: LazyList[A]
16
  def isEmpty: Boolean
17
  def force: this.type
18
  def knownSize: Int
19
}
20
```
21

22
#### Core Methods
23

24
##### head / tail
25

26
```scala { .api }
27
def head: A
28
def tail: LazyList[A]
29
```
30

31
Access the first element and remaining elements. Elements are computed lazily.
32

33
**Usage:**
34
```scala
35
val lazyList = LazyList(1, 2, 3, 4, 5)
36
val first = lazyList.head      // 1
37
val rest = lazyList.tail       // LazyList(2, 3, 4, 5)
38
```
39

40
##### isEmpty
41

42
```scala { .api }
43
def isEmpty: Boolean
44
```
45

46
Check if the lazy list is empty.
47

48
##### force
49

50
```scala { .api }
51
def force: this.type
52
```
53

54
Force evaluation of all elements in the lazy list. Detects and handles cycles.
55

56
**Usage:**
57
```scala
58
val infinite = LazyList.from(1)
59
// infinite.force  // Would not terminate
60
val finite = LazyList(1, 2, 3).force  // Forces evaluation of all elements
61
```
62

63
##### knownSize
64

65
```scala { .api }
66
def knownSize: Int
67
```
68

69
Returns the known size without forcing evaluation, or -1 if unknown.
70

71
### LazyList Companion Object
72

73
```scala { .api }
74
object LazyList extends SeqFactory[LazyList] {
75
  def empty[A]: LazyList[A]
76
  def apply[A](elems: A*): LazyList[A]
77
  def from[A](coll: GenTraversableOnce[A]): LazyList[A]
78
  def iterate[A](start: => A)(f: A => A): LazyList[A]
79
  def continually[A](elem: => A): LazyList[A]
80
  def unfold[A, S](init: S)(f: S => Option[(A, S)]): LazyList[A]
81
  def concat[A](xss: collection.Iterable[A]*): LazyList[A]
82
  def from(start: Int): LazyList[Int]
83
  def from(start: Int, step: Int): LazyList[Int]
84
  def fill[A](n: Int)(elem: => A): LazyList[A]
85
  def tabulate[A](n: Int)(f: Int => A): LazyList[A]
86
}
87
```
88

89
#### Factory Methods
90

91
##### from
92

93
```scala { .api }
94
def from[A](coll: GenTraversableOnce[A]): LazyList[A]
95
def from(start: Int): LazyList[Int]
96
def from(start: Int, step: Int): LazyList[Int]
97
```
98

99
Create a `LazyList` from a collection or generate an infinite sequence of integers.
100

101
**Usage:**
102
```scala
103
LazyList.from(List(1, 2, 3))        // LazyList(1, 2, 3)
104
LazyList.from(1)                    // LazyList(1, 2, 3, 4, ...)
105
LazyList.from(0, 2)                 // LazyList(0, 2, 4, 6, ...)
106
```
107

108
##### iterate
109

110
```scala { .api }
111
def iterate[A](start: => A)(f: A => A): LazyList[A]
112
```
113

114
Create an infinite `LazyList` by repeatedly applying a function.
115

116
**Usage:**
117
```scala
118
LazyList.iterate(1)(_ * 2)          // LazyList(1, 2, 4, 8, 16, ...)
119
LazyList.iterate("a")(_ + "a")      // LazyList("a", "aa", "aaa", ...)
120
```
121

122
##### continually
123

124
```scala { .api }
125
def continually[A](elem: => A): LazyList[A]
126
```
127

128
Create an infinite `LazyList` with the same element repeated.
129

130
**Usage:**
131
```scala
132
LazyList.continually(42)            // LazyList(42, 42, 42, ...)
133
LazyList.continually(scala.util.Random.nextInt())  // Random numbers
134
```
135

136
##### unfold
137

138
```scala { .api }
139
def unfold[A, S](init: S)(f: S => Option[(A, S)]): LazyList[A]
140
```
141

142
Create a `LazyList` by unfolding a state with a generating function.
143

144
**Usage:**
145
```scala
146
// Generate Fibonacci sequence
147
LazyList.unfold((0, 1)) { case (a, b) =>
148
  Some((a, (b, a + b)))
149
}  // LazyList(0, 1, 1, 2, 3, 5, 8, ...)
150

151
// Generate sequence up to a limit
152
LazyList.unfold(0) { n =>
153
  if (n < 10) Some((n, n + 1)) else None
154
}  // LazyList(0, 1, 2, ..., 9)
155
```
156

157
##### fill / tabulate
158

159
```scala { .api }
160
def fill[A](n: Int)(elem: => A): LazyList[A]
161
def tabulate[A](n: Int)(f: Int => A): LazyList[A]
162
```
163

164
Create finite `LazyList`s with repeated elements or computed elements.
165

166
**Usage:**
167
```scala
168
LazyList.fill(5)("x")               // LazyList("x", "x", "x", "x", "x")  
169
LazyList.tabulate(5)(n => n * n)    // LazyList(0, 1, 4, 9, 16)
170
```
171

172
### LazyList Construction Operators
173

174
#### cons Object
175

176
```scala { .api }
177
object cons {
178
  def apply[A](hd: => A, tl: => LazyList[A]): LazyList[A]
179
  def unapply[A](xs: LazyList[A]): Option[(A, LazyList[A])]
180
}
181
```
182

183
Alternative construction and pattern matching for `LazyList`.
184

185
#### #:: Operator
186

187
```scala { .api }
188
object #:: {
189
  def unapply[A](s: LazyList[A]): Option[(A, LazyList[A])]
190
}
191

192
implicit def toDeferrer[A](l: => LazyList[A]): Deferrer[A]
193

194
final class Deferrer[A] private[LazyList] (private val l: () => LazyList[A]) {
195
  def #::[B >: A](elem: => B): LazyList[B]
196
  def #:::[B >: A](prefix: LazyList[B]): LazyList[B]
197
}
198
```
199

200
Lazy cons operators for constructing `LazyList`s.
201

202
**Usage:**
203
```scala
204
val lazyList = 1 #:: 2 #:: 3 #:: LazyList.empty
205
val infinite = 1 #:: infinite.map(_ + 1)
206

207
// Pattern matching
208
lazyList match {
209
  case head #:: tail => println(s"Head: $head, Tail: $tail")
210
  case _ => println("Empty")
211
}
212
```
213

214
## ArraySeq
215

216
An immutable sequence backed by an array, providing efficient indexed access with a small memory footprint.
217

218
### ArraySeq Class
219

220
```scala { .api }
221
abstract class ArraySeq[+T] extends AbstractSeq[T] with IndexedSeq[T] 
222
    with IndexedSeqOptimized[T, ArraySeq[T]] {
223
  
224
  def length: Int
225
  def apply(index: Int): T
226
  def unsafeArray: Array[T]
227
  def clone(): ArraySeq[T]
228
}
229
```
230

231
#### Core Methods
232

233
##### length / apply
234

235
```scala { .api }
236
def length: Int
237
def apply(index: Int): T
238
```
239

240
Standard indexed sequence operations with O(1) access time.
241

242
##### unsafeArray
243

244
```scala { .api }
245
def unsafeArray: Array[T]
246
```
247

248
Direct access to the underlying array. Use with caution as it breaks immutability guarantees if modified.
249

250
##### clone
251

252
```scala { .api }
253
def clone(): ArraySeq[T]
254
```
255

256
Create a deep copy of the `ArraySeq`, including cloning the underlying array.
257

258
### ArraySeq Companion Object
259

260
```scala { .api }
261
object ArraySeq {
262
  def empty[T <: AnyRef]: ArraySeq[T]
263
  def apply[T](elems: T*)(implicit elemTag: ClassTag[T]): ArraySeq[T]
264
  def unsafeWrapArray[T](x: Array[T]): ArraySeq[T]
265
  def newBuilder[T](implicit elemTag: ClassTag[T]): Builder[T, ArraySeq[T]]
266
  def unapplySeq[T](seq: ArraySeq[T]): Some[ArraySeq[T]]
267
}
268
```
269

270
#### Factory Methods
271

272
##### apply
273

274
```scala { .api }
275
def apply[T](elems: T*)(implicit elemTag: ClassTag[T]): ArraySeq[T]
276
```
277

278
Create an `ArraySeq` from variable arguments.
279

280
**Usage:**
281
```scala
282
ArraySeq(1, 2, 3, 4, 5)            // ArraySeq[Int]
283
ArraySeq("a", "b", "c")            // ArraySeq[String]
284
```
285

286
##### unsafeWrapArray
287

288
```scala { .api }
289
def unsafeWrapArray[T](x: Array[T]): ArraySeq[T]
290
```
291

292
Wrap an existing array in an `ArraySeq` without copying. The array should not be modified after wrapping.
293

294
**Usage:**
295
```scala
296
val array = Array(1, 2, 3, 4, 5)
297
val arraySeq = ArraySeq.unsafeWrapArray(array)
298
```
299

300
##### empty
301

302
```scala { .api }
303
def empty[T <: AnyRef]: ArraySeq[T]
304
```
305

306
Create an empty `ArraySeq`.
307

308
### Specialized ArraySeq Types
309

310
`ArraySeq` provides specialized implementations for primitive types to avoid boxing:
311

312
```scala { .api }
313
final class ofRef[T <: AnyRef](val unsafeArray: Array[T]) extends ArraySeq[T]
314
final class ofInt(val unsafeArray: Array[Int]) extends ArraySeq[Int]
315
final class ofDouble(val unsafeArray: Array[Double]) extends ArraySeq[Double]
316
final class ofLong(val unsafeArray: Array[Long]) extends ArraySeq[Long]
317
final class ofFloat(val unsafeArray: Array[Float]) extends ArraySeq[Float]
318
final class ofChar(val unsafeArray: Array[Char]) extends ArraySeq[Char]
319
final class ofByte(val unsafeArray: Array[Byte]) extends ArraySeq[Byte]
320
final class ofShort(val unsafeArray: Array[Short]) extends ArraySeq[Short]
321
final class ofBoolean(val unsafeArray: Array[Boolean]) extends ArraySeq[Boolean]
322
final class ofUnit(val unsafeArray: Array[Unit]) extends ArraySeq[Unit]
323
```
324

325
## Usage Examples
326

327
### LazyList Examples
328

329
#### Infinite Sequences
330

331
```scala
332
import scala.collection.compat.immutable._
333

334
// Fibonacci sequence
335
val fibs: LazyList[BigInt] = BigInt(0) #:: BigInt(1) #:: 
336
  fibs.zip(fibs.tail).map { case (a, b) => a + b }
337

338
fibs.take(10).foreach(println)  // Print first 10 Fibonacci numbers
339

340
// Prime numbers using sieve
341
def sieve(s: LazyList[Int]): LazyList[Int] = 
342
  s.head #:: sieve(s.tail.filter(_ % s.head != 0))
343

344
val primes = sieve(LazyList.from(2))
345
primes.take(10).toList  // List(2, 3, 5, 7, 11, 13, 17, 19, 23, 29)
346
```
347

348
#### Finite Lazy Computation
349

350
```scala
351
// Expensive computation with memoization
352
def expensiveCompute(n: Int): Int = {
353
  Thread.sleep(100)  // Simulate expensive operation
354
  n * n
355
}
356

357
val lazyResults = LazyList.tabulate(10)(expensiveCompute)
358
// Only computed when accessed
359
val firstFew = lazyResults.take(3).toList
360
```
361

362
### ArraySeq Examples
363

364
#### Efficient Indexed Access
365

366
```scala
367
import scala.collection.compat.immutable._
368

369
val seq = ArraySeq(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
370

371
// O(1) access
372
val element = seq(5)  // 6
373
val length = seq.length  // 10
374

375
// Efficient operations
376
val doubled = seq.map(_ * 2)
377
val filtered = seq.filter(_ % 2 == 0)
378
```
379

380
#### Working with Primitive Arrays
381

382
```scala
383
// Specialized for primitives - no boxing
384
val intSeq = ArraySeq(1, 2, 3, 4, 5)        // ArraySeq.ofInt
385
val doubleSeq = ArraySeq(1.0, 2.0, 3.0)     // ArraySeq.ofDouble
386
val boolSeq = ArraySeq(true, false, true)   // ArraySeq.ofBoolean
387

388
// Wrap existing arrays
389
val array = Array(10, 20, 30, 40, 50)
390
val wrapped = ArraySeq.unsafeWrapArray(array)
391
```
392

393
## Performance Characteristics
394

395
### LazyList
396
- **Head access**: O(1) for evaluated elements
397
- **Tail access**: O(1) for evaluated elements  
398
- **Memory**: Elements are memoized after first evaluation
399
- **Evaluation**: Lazy - elements computed only when needed
400
- **Best for**: Infinite sequences, expensive computations, streaming data
401

402
### ArraySeq
403
- **Indexed access**: O(1)
404
- **Length**: O(1)  
405
- **Memory**: Compact array storage, specialized for primitives
406
- **Prepend/append**: O(n) - creates new array
407
- **Best for**: Frequent random access, small memory footprint, primitive collections
408

409
## Migration Notes
410

411
- `LazyList` replaces `Stream` in Scala 2.13+
412
- `ArraySeq` provides an immutable alternative to `Vector` with different performance characteristics
413
- Both types are available as backports for Scala 2.11/2.12 through this compatibility library