0
# Polymorphic Functions and Type-Level Programming
1

2
Shapeless provides sophisticated type-level programming capabilities including polymorphic functions that work across different types, natural transformations, type-level arithmetic with natural numbers, and advanced type-level logic for compile-time computations.
3

4
## Capabilities
5

6
### Polymorphic Functions (Poly)
7

8
Functions that can operate on different types while preserving type information and enabling type-dependent behavior.
9

10
```scala { .api }
11
// Base trait for polymorphic functions
12
trait Poly {
13
  // Apply to HList of arguments with case resolution
14
  def apply[L <: HList](args: L)(implicit cse: Case.Aux[this.type, L, Out]): Out
15
}
16

17
// Arity-specific polymorphic function traits
18
trait Poly0 extends Poly {
19
  def apply()(implicit cse: Case0[this.type]): cse.Result
20
}
21

22
trait Poly1 extends Poly {
23
  def apply[A](a: A)(implicit cse: Case1[A, this.type]): cse.Result  
24
}
25

26
trait Poly2 extends Poly {
27
  def apply[A, B](a: A, b: B)(implicit cse: Case2[A, B, this.type]): cse.Result
28
}
29

30
// Continue for higher arities...
31
```
32

33
### Case Definitions
34

35
Type-specific implementations for polymorphic functions with dependent result types.
36

37
```scala { .api }
38
// General case with dependent result type
39
trait Case[P, L <: HList] {
40
  type Result
41
  def apply(args: L): Result
42
}
43

44
// Convenience aliases for common arities
45
type Case0[P] = Case[P, HNil] 
46
type Case1[A, P] = Case[P, A :: HNil]
47
type Case2[A, B, P] = Case[P, A :: B :: HNil]
48

49
// Case for transducer-style operations
50
trait CaseTransducer[P, A] {
51
  type Out
52
  def apply(a: A): Out
53
}
54

55
// Usage pattern:
56
object myPoly extends Poly1 {
57
  implicit def intCase = at[Int](i => i * 2)
58
  implicit def stringCase = at[String](s => s.toUpperCase)
59
  implicit def boolCase = at[Boolean](b => !b)
60
}
61
```
62

63
### Polymorphic Function Combinators
64

65
Operations for composing and transforming polymorphic functions.
66

67
```scala { .api }
68
// Function composition (F ∘ G)
69
trait Compose[F, G] extends Poly1 {
70
  def apply[A](a: A)(implicit 
71
    gCase: G.Case1[A],
72
    fCase: F.Case1[gCase.Result]
73
  ): fCase.Result
74
}
75

76
// Rotate function arguments left by N positions
77
trait RotateLeft[P, N <: Nat] extends Poly
78

79
// Rotate function arguments right by N positions  
80
trait RotateRight[P, N <: Nat] extends Poly
81

82
// Usage:
83
val composed = Compose(f, g)  // Applies g then f
84
val rotated = RotateLeft(myPoly, Nat._2)
85
```
86

87
### Built-in Polymorphic Functions
88

89
Common polymorphic functions provided by Shapeless.
90

91
```scala { .api }
92
// Identity function - returns input unchanged
93
object identity extends Poly1 {
94
  implicit def default[A] = at[A](a => a)
95
}
96

97
// Constant function returning fixed value
98
def const[T](value: T): Poly1 = new Poly1 {
99
  implicit def default[A] = at[A](_ => value)
100
}
101

102
// Convert values to singleton types
103
object singleton extends Poly1 {
104
  implicit def default[A] = at[A](a => a: a.type)
105
}
106

107
// Convert to string representation
108
object stringify extends Poly1 {
109
  implicit def default[A] = at[A](_.toString)
110
}
111
```
112

113
### Natural Transformations
114

115
Polymorphic functions between type constructors (functors).
116

117
```scala { .api }
118
// Natural transformation between unary type constructors
119
trait ~>[F[_], G[_]] {
120
  def apply[A](fa: F[A]): G[A]
121
}
122

123
// Natural transformation between binary type constructors
124
trait ~~>[F[_, _], G[_, _]] {
125
  def apply[A, B](fab: F[A, B]): G[A, B]
126
}
127

128
// Example transformations:
129
val optionToList = new (Option ~> List) {
130
  def apply[A](opt: Option[A]): List[A] = opt.toList
131
}
132

133
val listToVector = new (List ~> Vector) {
134
  def apply[A](list: List[A]): Vector[A] = list.toVector
135
}
136
```
137

138
### Natural Numbers (Nat)
139

140
Compile-time natural numbers for type-level arithmetic and indexing.
141

142
```scala { .api }
143
// Base sealed trait with associated type member
144
sealed trait Nat {
145
  type N <: Nat
146
}
147

148
// Successor type representing S(n) = n+1
149
sealed trait Succ[P <: Nat] extends Nat {
150
  type N = Succ[P]
151
}
152

153
// Zero type and value object
154
sealed trait _0 extends Nat {
155
  type N = _0
156
}
157
case object _0 extends _0
158

159
// Nat companion object
160
object Nat {
161
  // Convert runtime Int to compile-time Nat
162
  def apply(i: Int): Nat = macro NatMacros.materialize
163
  
164
  // Convert compile-time Nat to runtime Int
165
  def toInt[N <: Nat](implicit toInt: ToInt[N]): Int = toInt()
166
  
167
  // Type aliases for common numbers
168
  type _1 = Succ[_0]
169
  type _2 = Succ[_1] 
170
  type _3 = Succ[_2]
171
  // ... continues to _22 and beyond
172
}
173
```
174

175
### Nat Operations
176

177
Type-level arithmetic operations on natural numbers.
178

179
```scala { .api }
180
// Type-level addition A + B
181
trait Sum[A <: Nat, B <: Nat] {
182
  type Out <: Nat
183
}
184

185
// Type-level subtraction A - B (when A >= B)
186
trait Diff[A <: Nat, B <: Nat] {
187
  type Out <: Nat  
188
}
189

190
// Type-level multiplication A * B
191
trait Prod[A <: Nat, B <: Nat] {
192
  type Out <: Nat
193
}
194

195
// Type-level division A / B
196
trait Div[A <: Nat, B <: Nat] {
197
  type Out <: Nat
198
}
199

200
// Type-level modulo A % B
201
trait Mod[A <: Nat, B <: Nat] {
202
  type Out <: Nat
203
}
204

205
// Comparison operations
206
trait LT[A <: Nat, B <: Nat]      // A < B
207
trait LTEq[A <: Nat, B <: Nat]    // A <= B
208
trait GT[A <: Nat, B <: Nat]      // A > B
209
trait GTEq[A <: Nat, B <: Nat]    // A >= B
210

211
// Min and Max operations
212
trait Min[A <: Nat, B <: Nat] { type Out <: Nat }
213
trait Max[A <: Nat, B <: Nat] { type Out <: Nat }
214
```
215

216
### Finite Types (Fin)
217

218
Finite types with exactly N inhabitants for type-safe indexing.
219

220
```scala { .api }
221
// Finite type with exactly N inhabitants (0, 1, ..., N-1)
222
sealed trait Fin[N <: Nat] {
223
  def toInt: Int
224
}
225

226
object Fin {
227
  // Create Fin value from Int with bounds checking
228
  def apply[N <: Nat](i: Int)(implicit toInt: ToInt[N]): Option[Fin[N]]
229
  
230
  // Unsafe creation (no bounds checking)
231
  def unsafeFrom[N <: Nat](i: Int): Fin[N]
232
  
233
  // Convert to Int
234
  def toInt[N <: Nat](fin: Fin[N]): Int
235
}
236

237
// Usage for type-safe array indexing
238
def safeGet[A, N <: Nat](arr: Array[A], index: Fin[N]): Option[A] = {
239
  if (index.toInt < arr.length) Some(arr(index.toInt)) else None
240
}
241
```
242

243
### Singleton Types and Witnesses
244

245
Working with singleton types and compile-time constants.
246

247
```scala { .api }
248
// Witness that T is a singleton type
249
trait Witness[T] {
250
  type Out = T
251
  val value: T
252
}
253

254
object Witness {
255
  // Type alias for witness with specific singleton type
256
  type Aux[T] = Witness[T] { type Out = T }
257
  
258
  // Create witness for singleton type
259
  def apply[T](implicit w: Witness[T]): Witness.Aux[T] = w
260
}
261

262
// Witness with additional type class constraint
263
trait WitnessWith[TC[_]] {
264
  type Out
265
  val value: Out
266
  val typeClass: TC[Out]
267
}
268

269
// Usage:
270
val intWitness = Witness(42)        // Witness for 42.type
271
val stringWitness = Witness("test")  // Witness for "test".type
272
```
273

274
### Type-Level Logic
275

276
Boolean logic and reasoning at the type level.
277

278
```scala { .api }
279
// Type-level boolean values
280
sealed trait Bool
281
sealed trait True extends Bool
282
sealed trait False extends Bool
283

284
// Logical operations
285
trait Not[B <: Bool] { type Out <: Bool }
286
trait And[A <: Bool, B <: Bool] { type Out <: Bool }  
287
trait Or[A <: Bool, B <: Bool] { type Out <: Bool }
288

289
// Type-level if-then-else
290
trait If[C <: Bool, T, F] { type Out }
291

292
// Evidence for type relationships
293
trait =:=[A, B]    // Type equality
294
trait <:<[A, B]    // Subtype relationship  
295
trait =:!=[A, B]   // Type inequality
296
trait <:!<[A, B]   // Subtype exclusion
297
```
298

299
## Usage Examples
300

301
### Basic Polymorphic Functions
302

303
```scala
304
import shapeless._
305

306
// Define polymorphic function
307
object size extends Poly1 {
308
  implicit def stringCase = at[String](_.length)
309
  implicit def listCase[A] = at[List[A]](_.size)
310
  implicit def optionCase[A] = at[Option[A]](_.size)
311
  implicit def intCase = at[Int](_ => 1)  // Size of Int is always 1
312
}
313

314
// Apply to different types
315
val stringSize = size("hello")        // 5
316
val listSize = size(List(1, 2, 3))    // 3  
317
val optionSize = size(Some(42))       // 1
318
val intSize = size(123)               // 1
319

320
// Use with HList
321
val mixed = "test" :: List(1, 2) :: Some(true) :: HNil
322
val sizes = mixed.map(size)  // 4 :: 2 :: 1 :: HNil
323
```
324

325
### Type-Level Arithmetic
326

327
```scala
328
// Compile-time arithmetic
329
type Five = Succ[Succ[Succ[Succ[Succ[_0]]]]]  // or Nat._5
330
type Three = Succ[Succ[Succ[_0]]]             // or Nat._3
331

332
// Type-level operations
333
type Eight = Sum[Five, Three]    // 5 + 3 = 8
334
type Two = Diff[Five, Three]     // 5 - 3 = 2  
335
type Fifteen = Prod[Five, Three] // 5 * 3 = 15
336

337
// Runtime conversion
338
val eight: Int = Nat.toInt[Eight]      // 8
339
val two: Int = Nat.toInt[Two]          // 2
340
val fifteen: Int = Nat.toInt[Fifteen]  // 15
341

342
// Comparison evidence
343
def compareNats[A <: Nat, B <: Nat](implicit lt: LT[A, B]): String = 
344
  "A is less than B"
345

346
val comparison = compareNats[Three, Five]  // "A is less than B"
347
```
348

349
### Natural Transformations
350

351
```scala
352
// Define container transformations
353
val optionToEither = new (Option ~> ({ type λ[A] = Either[String, A] })#λ) {
354
  def apply[A](opt: Option[A]): Either[String, A] = 
355
    opt.toRight("None value")
356
}
357

358
val listToNel = new (List ~> ({ type λ[A] = Option[A] })#λ) {
359
  def apply[A](list: List[A]): Option[A] = list.headOption
360
}
361

362
// Apply transformations
363
val someValue: Option[Int] = Some(42)
364
val eitherValue = optionToEither(someValue)  // Right(42)
365

366
val listValue: List[String] = List("a", "b", "c")  
367
val headValue = listToNel(listValue)         // Some("a")
368
```
369

370
### Advanced Polymorphic Function Composition
371

372
```scala
373
object double extends Poly1 {
374
  implicit def intCase = at[Int](_ * 2)
375
  implicit def stringCase = at[String](s => s + s)
376
}
377

378
object increment extends Poly1 {
379
  implicit def intCase = at[Int](_ + 1)  
380
  implicit def stringCase = at[String](_ + "!")
381
}
382

383
// Compose functions
384
val doubleThincrement = Compose(increment, double)
385

386
val result1 = doubleThincrement(5)      // double(5) = 10, increment(10) = 11
387
val result2 = doubleThincrement("hi")   // double("hi") = "hihi", increment("hihi") = "hihi!"
388
```
389

390
### Type-Safe Indexing with Fin
391

392
```scala
393
// Type-safe array access
394
def typeSafeArray[A](elements: A*): TypeSafeArray[A] = 
395
  new TypeSafeArray(elements.toArray)
396

397
class TypeSafeArray[A](private val arr: Array[A]) {
398
  def length: Nat = Nat(arr.length)
399
  
400
  def apply[N <: Nat](index: Fin[N])(implicit 
401
    ev: LT[N, length.type]
402
  ): A = arr(index.toInt)
403
  
404
  def get[N <: Nat](index: Fin[N]): Option[A] = {
405
    val i = index.toInt
406
    if (i < arr.length) Some(arr(i)) else None
407
  }
408
}
409

410
// Usage
411
val array = typeSafeArray("a", "b", "c", "d")
412

413
// Type-safe access (compile-time bounds checking)
414
val index0 = Fin[Nat._4](0).get  // Some(Fin[_4])
415
val index3 = Fin[Nat._4](3).get  // Some(Fin[_4])
416
val index4 = Fin[Nat._4](4)      // None (out of bounds)
417

418
val elem0 = array.get(index0.get)  // Some("a")
419
val elem3 = array.get(index3.get)  // Some("d")
420
```
421

422
### Singleton Type Programming
423

424
```scala
425
// Work with singleton types
426
val fortyTwo = Witness(42)
427
val hello = Witness("hello")
428

429
// Type-level string manipulation
430
type HelloWorld = "hello" + " " + "world"  // Requires recent Scala versions
431

432
// Singleton-typed collections
433
val singletonHList = 42 :: "test" :: true :: HNil
434
// Type: 42.type :: "test".type :: true.type :: HNil
435

436
// Extract singleton values at compile time
437
def getValue[S](implicit w: Witness.Aux[S]): S = w.value
438

439
val constantFortyTwo: 42 = getValue[42]      // 42
440
val constantHello: "hello" = getValue["hello"] // "hello"
441
```
442

443
### Complex Type-Level Computations
444

445
```scala
446
// Type-level list operations
447
trait Length[L <: HList] { type Out <: Nat }
448
trait Take[L <: HList, N <: Nat] { type Out <: HList }
449
trait Drop[L <: HList, N <: Nat] { type Out <: HList }
450

451
// Compute length at type level
452
type MyList = String :: Int :: Boolean :: HNil
453
type MyLength = Length[MyList]  // Nat._3
454

455
// Split operations
456
type FirstTwo = Take[MyList, Nat._2]   // String :: Int :: HNil  
457
type LastOne = Drop[MyList, Nat._2]    // Boolean :: HNil
458

459
// Type-level predicates
460
trait All[L <: HList, P[_]] { type Out <: Bool }
461
trait Any[L <: HList, P[_]] { type Out <: Bool }
462

463
// Check if all elements are numeric
464
trait IsNumeric[T] { type Out <: Bool }
465
type AllNumeric = All[Int :: Double :: Float :: HNil, IsNumeric]  // True
466
```