0
# Sized Collections
1

2
Sized collections in shapeless provide compile-time verification of collection lengths, enabling type-safe operations that depend on size constraints. They wrap existing collections with static size information tracked at the type level.
3

4
## Core Types
5

6
### Sized Wrapper
7

8
```scala { .api }
9
/**
10
 * Wrapper witnessing statically known collection size
11
 * Repr - underlying collection type, L - size as type-level natural number  
12
 */
13
abstract class Sized[+Repr, L <: Nat](r: Repr) {
14
  type A  // Element type
15
  def unsized = r  // Extract underlying collection
16
}
17
```
18

19
## Factory Methods
20

21
### Sized Object
22

23
```scala { .api }
24
object Sized {
25
  /**
26
   * Create sized collection factory for given collection type
27
   */
28
  def apply[CC[_]] = new SizedBuilder[CC]
29
  
30
  /**
31
   * Create empty sized collection
32
   */
33
  def apply[CC[_]]()(implicit cbf: CanBuildFrom[Nothing, Nothing, CC[Nothing]]): Sized[CC[Nothing], _0]
34
  
35
  /**
36
   * Wrap existing collection with size witness
37
   */
38
  def wrap[A0, Repr, L <: Nat](r: Repr): Sized[Repr, L]
39
}
40
```
41

42
**Usage Examples:**
43

44
```scala
45
import shapeless._
46
import syntax.sized._
47

48
// Create sized collections with known size
49
val sizedList: Sized[List[Int], _3] = Sized[List](1, 2, 3)
50
val sizedVector: Sized[Vector[String], _2] = Sized[Vector]("hello", "world")
51

52
// Verify size at runtime, get sized collection
53
val maybeList: Option[Sized[List[Int], _4]] = List(1, 2, 3, 4).sized(_4)
54
val maybeTooShort: Option[Sized[List[Int], _5]] = List(1, 2, 3).sized(_5)  // None
55

56
maybeList match {
57
  case Some(sized) => println(s"Got sized list of ${sized.unsized}")
58
  case None => println("Size mismatch")
59
}
60
```
61

62
## Size Conversion
63

64
### SizedConv
65

66
```scala { .api }
67
/**
68
 * Provides sizing operations for collections
69
 */
70
class SizedConv[A, Repr <% GenTraversableLike[A, Repr]](r: Repr) {
71
  /**
72
   * Try to create sized collection of specified length (safe)
73
   */
74
  def sized[L <: Nat](implicit toInt: ToInt[L]): Option[Sized[Repr, L]]
75
  
76
  /**
77
   * Create sized collection of specified length (unsafe - throws on mismatch)
78
   */
79
  def ensureSized[L <: Nat](implicit toInt: ToInt[L]): Sized[Repr, L]  
80
}
81
```
82

83
**Usage Examples:**
84

85
```scala
86
import shapeless._
87
import syntax.sized._
88

89
val numbers = List(1, 2, 3, 4, 5)
90

91
// Safe sizing - returns Option
92
val sized5: Option[Sized[List[Int], _5]] = numbers.sized(_5)       // Some(...)
93
val sized3: Option[Sized[List[Int], _3]] = numbers.sized(_3)       // None (wrong size)
94

95
// Unsafe sizing - throws exception on mismatch
96
val ensured: Sized[List[Int], _5] = numbers.ensureSized(_5)        // Works
97
// val failed = numbers.ensureSized(_3)                            // Throws exception
98

99
// Use with different collection types  
100
val stringVec = Vector("a", "b", "c")
101
val sizedVec: Option[Sized[Vector[String], _3]] = stringVec.sized(_3)  // Some(...)
102
```
103

104
## Sized Operations
105

106
### SizedOps Enhancement
107

108
Sized collections are enhanced with safe operations through `SizedOps[A, Repr, L <: Nat]`:
109

110
```scala { .api }
111
/**
112
 * Enhanced operations for sized collections
113
 */
114
class SizedOps[A, Repr, L <: Nat] {
115
  // Safe access (requires evidence that size > 0)
116
  def head(implicit ev: _0 < L): A
117
  def tail(implicit pred: Pred[L]): Sized[Repr, pred.Out]
118
  
119
  // Size-preserving slicing  
120
  def take[M <: Nat](implicit diff: Diff[L, M], ev: ToInt[M]): Sized[Repr, M]
121
  def drop[M <: Nat](implicit diff: Diff[L, M], ev: ToInt[M]): Sized[Repr, diff.Out]
122
  def splitAt[M <: Nat](implicit diff: Diff[L, M], ev: ToInt[M]): (Sized[Repr, M], Sized[Repr, diff.Out])
123
  
124
  // Size-changing operations
125
  def +:(elem: A)(implicit cbf: CanBuildFrom[Repr, A, Repr]): Sized[Repr, Succ[L]]
126
  def :+(elem: A)(implicit cbf: CanBuildFrom[Repr, A, Repr]): Sized[Repr, Succ[L]]
127
  def ++[B >: A, That, M <: Nat](that: Sized[That, M]): Sized[That, sum.Out] // where sum.Out = L + M
128
  
129
  // Size-preserving transformations
130
  def map[B, That](f: A => B)(implicit cbf: CanBuildFrom[Repr, B, That]): Sized[That, L]
131
}
132
```
133

134
### Safe Access Operations
135

136
```scala
137
import shapeless._
138
import syntax.sized._
139

140
val sizedList = List(1, 2, 3, 4, 5).ensureSized(_5)
141

142
// Safe head - compiles because _0 < _5
143
val head: Int = sizedList.head           // 1
144

145
// Safe tail - type shows decremented size
146
val tail: Sized[List[Int], _4] = sizedList.tail  // List(2, 3, 4, 5) with size _4
147

148
// Empty list would fail to compile:
149
val empty = List.empty[Int].ensureSized(_0) 
150
// empty.head  // Compile error: can't prove _0 < _0
151
```
152

153
### Safe Slicing Operations
154

155
```scala
156
import shapeless._
157
import syntax.sized._
158

159
val sizedList = List("a", "b", "c", "d", "e").ensureSized(_5)
160

161
// Take operations with compile-time size checking
162
val first3: Sized[List[String], _3] = sizedList.take(_3)       // List("a", "b", "c")
163
val last2: Sized[List[String], _2] = sizedList.drop(_3)        // List("d", "e")
164

165
// Split preserves size relationships
166
val (prefix, suffix) = sizedList.splitAt(_2)
167
// prefix: Sized[List[String], _2] = List("a", "b")  
168
// suffix: Sized[List[String], _3] = List("c", "d", "e")
169

170
// This would fail at compile time:
171
// val tooMany = sizedList.take(_6)  // Error: can't prove _6 <= _5
172
```
173

174
### Size-changing Operations
175

176
```scala
177
import shapeless._
178
import syntax.sized._
179

180
val sized3 = List(1, 2, 3).ensureSized(_3)
181

182
// Prepend and append increment size
183
val sized4: Sized[List[Int], _4] = 0 +: sized3        // List(0, 1, 2, 3)  
184
val sized4b: Sized[List[Int], _4] = sized3 :+ 4       // List(1, 2, 3, 4)
185

186
// Concatenation adds sizes
187
val other2 = List(10, 20).ensureSized(_2)
188
val sized5: Sized[List[Int], _5] = sized3 ++ other2   // List(1, 2, 3, 10, 20)
189
```
190

191
### Size-preserving Transformations
192

193
```scala
194
import shapeless._
195
import syntax.sized._
196

197
val numbers = List(1, 2, 3, 4).ensureSized(_4)
198

199
// Map preserves size
200
val doubled: Sized[List[Int], _4] = numbers.map(_ * 2)        // List(2, 4, 6, 8)
201
val strings: Sized[List[String], _4] = numbers.map(_.toString) // List("1", "2", "3", "4")
202

203
// Size is preserved even with different collection types
204
val sizedVec: Sized[Vector[Int], _4] = numbers.map(identity)(Vector.canBuildFrom)
205
```
206

207
## Advanced Usage Patterns
208

209
### Size Constraints in Functions
210

211
```scala
212
import shapeless._
213
import syntax.sized._
214

215
// Function requiring minimum size
216
def processAtLeast3[A, Repr, N <: Nat]
217
  (sized: Sized[Repr, N])
218
  (implicit ev: _3 <= N, toInt: ToInt[N]): String = 
219
  s"Processing ${toInt()} elements (at least 3)"
220

221
val validList = List(1, 2, 3, 4).ensureSized(_4)
222
val result = processAtLeast3(validList)  // "Processing 4 elements (at least 3)"
223

224
val tooSmall = List(1, 2).ensureSized(_2)
225
// processAtLeast3(tooSmall)  // Compile error: can't prove _3 <= _2
226

227
// Function requiring exact size
228
def processPair[A, Repr](pair: Sized[Repr, _2]): String = "Processing pair"
229

230
val exactPair = List("a", "b").ensureSized(_2)
231
val pairResult = processPair(exactPair)  // Works
232

233
val notPair = List("a", "b", "c").ensureSized(_3)  
234
// processPair(notPair)  // Compile error: type mismatch
235
```
236

237
### Size Arithmetic
238

239
```scala
240
import shapeless._
241
import syntax.sized._
242

243
// Combine sized collections with known total size
244
def combineAndVerifySize[A, N <: Nat, M <: Nat]
245
  (left: Sized[List[A], N], right: Sized[List[A], M])
246
  (implicit sum: Sum[N, M]): Sized[List[A], sum.Out] = left ++ right
247

248
val list3 = List(1, 2, 3).ensureSized(_3)
249
val list2 = List(4, 5).ensureSized(_2)  
250
val list5: Sized[List[Int], _5] = combineAndVerifySize(list3, list2)  // List(1, 2, 3, 4, 5)
251
```
252

253
### Runtime Size Validation
254

255
```scala
256
import shapeless._
257
import syntax.sized._
258

259
// Create sized collection from user input
260
def createUserList[N <: Nat](elements: List[String])
261
  (implicit toInt: ToInt[N]): Either[String, Sized[List[String], N]] = {
262
  
263
  elements.sized[N] match {
264
    case Some(sized) => Right(sized)
265
    case None => Left(s"Expected ${toInt[N]} elements, got ${elements.length}")  
266
  }
267
}
268

269
val userInput = List("apple", "banana", "cherry")
270
val result: Either[String, Sized[List[String], _3]] = createUserList[_3](userInput)
271
// Right(Sized(...))
272

273
val wrongSize: Either[String, Sized[List[String], _5]] = createUserList[_5](userInput)  
274
// Left("Expected 5 elements, got 3")
275
```
276

277
### Integration with HLists
278

279
```scala
280
import shapeless._
281
import syntax.sized._
282

283
// Convert between sized collections and HLists
284
def sizedToHList[A, N <: Nat](sized: Sized[List[A], N]): HList = {
285
  // This would require complex type machinery in practice
286
  // Shown conceptually - real implementation needs more infrastructure
287
  ???
288
}
289

290
// Type-safe indexing matching HList capabilities
291
val sized = List("a", "b", "c").ensureSized(_3)
292
val first = sized.head        // "a" - safe because size >= 1
293
val second = sized.tail.head  // "b" - safe because size >= 2  
294
val third = sized.tail.tail.head  // "c" - safe because size >= 3
295
```
296

297
### Performance Considerations
298

299
```scala
300
import shapeless._
301
import syntax.sized._
302

303
// Sized collections don't add runtime overhead
304
val normalList = List(1, 2, 3, 4, 5)
305
val sizedList = normalList.ensureSized(_5)
306

307
// Operations compile to same bytecode as normal collections
308
val doubled = sizedList.map(_ * 2)  // No extra runtime cost
309
val underlying = doubled.unsized    // Extract original collection type
310

311
// Size checking happens only at creation time
312
val validated = normalList.sized(_5)  // O(n) to check size
313
// All subsequent operations are O(1) for size tracking
314
```
315

316
Sized collections provide compile-time guarantees about collection lengths while maintaining the performance characteristics of the underlying collections. They enable writing safer code by catching size-related errors at compile time rather than runtime.