Polymorphic Functions and Type-Level Programming

// Base trait for polymorphic functions
trait Poly {
  // Apply to HList of arguments with case resolution
  def apply[L <: HList](args: L)(implicit cse: Case.Aux[this.type, L, Out]): Out
}

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

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

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

// Continue for higher arities...

// General case with dependent result type
trait Case[P, L <: HList] {
  type Result
  def apply(args: L): Result
}

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

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

// Usage pattern:
object myPoly extends Poly1 {
  implicit def intCase = at[Int](i => i * 2)
  implicit def stringCase = at[String](s => s.toUpperCase)
  implicit def boolCase = at[Boolean](b => !b)
}

// Function composition (F ∘ G)
trait Compose[F, G] extends Poly1 {
  def apply[A](a: A)(implicit 
    gCase: G.Case1[A],
    fCase: F.Case1[gCase.Result]
  ): fCase.Result
}

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

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

// Usage:
val composed = Compose(f, g)  // Applies g then f
val rotated = RotateLeft(myPoly, Nat._2)

// Identity function - returns input unchanged
object identity extends Poly1 {
  implicit def default[A] = at[A](a => a)
}

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

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

// Convert to string representation
object stringify extends Poly1 {
  implicit def default[A] = at[A](_.toString)
}

// Natural transformation between unary type constructors
trait ~>[F[_], G[_]] {
  def apply[A](fa: F[A]): G[A]
}

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

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

val listToVector = new (List ~> Vector) {
  def apply[A](list: List[A]): Vector[A] = list.toVector
}

// Base sealed trait with associated type member
sealed trait Nat {
  type N <: Nat
}

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

// Zero type and value object
sealed trait _0 extends Nat {
  type N = _0
}
case object _0 extends _0

// Nat companion object
object Nat {
  // Convert runtime Int to compile-time Nat
  def apply(i: Int): Nat = macro NatMacros.materialize
  
  // Convert compile-time Nat to runtime Int
  def toInt[N <: Nat](implicit toInt: ToInt[N]): Int = toInt()
  
  // Type aliases for common numbers
  type _1 = Succ[_0]
  type _2 = Succ[_1] 
  type _3 = Succ[_2]
  // ... continues to _22 and beyond
}

// Type-level addition A + B
trait Sum[A <: Nat, B <: Nat] {
  type Out <: Nat
}

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

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

// Type-level division A / B
trait Div[A <: Nat, B <: Nat] {
  type Out <: Nat
}

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

// Comparison operations
trait LT[A <: Nat, B <: Nat]      // A < B
trait LTEq[A <: Nat, B <: Nat]    // A <= B
trait GT[A <: Nat, B <: Nat]      // A > B
trait GTEq[A <: Nat, B <: Nat]    // A >= B

// Min and Max operations
trait Min[A <: Nat, B <: Nat] { type Out <: Nat }
trait Max[A <: Nat, B <: Nat] { type Out <: Nat }

// Finite type with exactly N inhabitants (0, 1, ..., N-1)
sealed trait Fin[N <: Nat] {
  def toInt: Int
}

object Fin {
  // Create Fin value from Int with bounds checking
  def apply[N <: Nat](i: Int)(implicit toInt: ToInt[N]): Option[Fin[N]]
  
  // Unsafe creation (no bounds checking)
  def unsafeFrom[N <: Nat](i: Int): Fin[N]
  
  // Convert to Int
  def toInt[N <: Nat](fin: Fin[N]): Int
}

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

// Witness that T is a singleton type
trait Witness[T] {
  type Out = T
  val value: T
}

object Witness {
  // Type alias for witness with specific singleton type
  type Aux[T] = Witness[T] { type Out = T }
  
  // Create witness for singleton type
  def apply[T](implicit w: Witness[T]): Witness.Aux[T] = w
}

// Witness with additional type class constraint
trait WitnessWith[TC[_]] {
  type Out
  val value: Out
  val typeClass: TC[Out]
}

// Usage:
val intWitness = Witness(42)        // Witness for 42.type
val stringWitness = Witness("test")  // Witness for "test".type

// Type-level boolean values
sealed trait Bool
sealed trait True extends Bool
sealed trait False extends Bool

// Logical operations
trait Not[B <: Bool] { type Out <: Bool }
trait And[A <: Bool, B <: Bool] { type Out <: Bool }  
trait Or[A <: Bool, B <: Bool] { type Out <: Bool }

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

// Evidence for type relationships
trait =:=[A, B]    // Type equality
trait <:<[A, B]    // Subtype relationship  
trait =:!=[A, B]   // Type inequality
trait <:!<[A, B]   // Subtype exclusion

import shapeless._

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

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

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

// Compile-time arithmetic
type Five = Succ[Succ[Succ[Succ[Succ[_0]]]]]  // or Nat._5
type Three = Succ[Succ[Succ[_0]]]             // or Nat._3

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

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

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

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

// Define container transformations
val optionToEither = new (Option ~> ({ type λ[A] = Either[String, A] })#λ) {
  def apply[A](opt: Option[A]): Either[String, A] = 
    opt.toRight("None value")
}

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

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

val listValue: List[String] = List("a", "b", "c")  
val headValue = listToNel(listValue)         // Some("a")

object double extends Poly1 {
  implicit def intCase = at[Int](_ * 2)
  implicit def stringCase = at[String](s => s + s)
}

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

// Compose functions
val doubleThincrement = Compose(increment, double)

val result1 = doubleThincrement(5)      // double(5) = 10, increment(10) = 11
val result2 = doubleThincrement("hi")   // double("hi") = "hihi", increment("hihi") = "hihi!"

// Type-safe array access
def typeSafeArray[A](elements: A*): TypeSafeArray[A] = 
  new TypeSafeArray(elements.toArray)

class TypeSafeArray[A](private val arr: Array[A]) {
  def length: Nat = Nat(arr.length)
  
  def apply[N <: Nat](index: Fin[N])(implicit 
    ev: LT[N, length.type]
  ): A = arr(index.toInt)
  
  def get[N <: Nat](index: Fin[N]): Option[A] = {
    val i = index.toInt
    if (i < arr.length) Some(arr(i)) else None
  }
}

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

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

val elem0 = array.get(index0.get)  // Some("a")
val elem3 = array.get(index3.get)  // Some("d")

// Work with singleton types
val fortyTwo = Witness(42)
val hello = Witness("hello")

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

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

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

val constantFortyTwo: 42 = getValue[42]      // 42
val constantHello: "hello" = getValue["hello"] // "hello"

// Type-level list operations
trait Length[L <: HList] { type Out <: Nat }
trait Take[L <: HList, N <: Nat] { type Out <: HList }
trait Drop[L <: HList, N <: Nat] { type Out <: HList }

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

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

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

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