The Trial of Types

Factorial.scala

package sandbox

import Nat._

trait Factorial[N <: Nat] {
    type Out <: Nat
}

trait FactorialInstances0 {
    type Aux[I <: Nat, O <: Nat] = Factorial[I] { type Out = O}

    implicit def factorial2[A <: Nat, B <: Nat, C <: Nat](implicit
        fact: Aux[A, B],
        prod: Prod.Aux[Succ[A], B, C]
    ): Aux[Succ[A], C] = new Factorial[Succ[A]] {
        type Out = C
    }
}

object Factorial extends FactorialInstances0{
    def apply[N <: Nat](implicit fact: Factorial[N]) = new {
        def value(implicit toInt: ToInt[fact.Out]): Int = toInt()
    }
    
    implicit val factorial0: Aux[Zero, _1] = new Factorial[Zero] { type Out = _1 }
    implicit val factorial1: Aux[_1, _1] = new Factorial[_1] { type Out = _1 }
}

FizzBuzz.Scala

package sandbox

import Nat._
import FizzBuzz._

sealed trait FizzBuzz

object FizzBuzz {
    case object Fizz extends FizzBuzz
    case object Buzz extends FizzBuzz
    case object FizzAndBuzz extends FizzBuzz
    trait Other[N <: Nat] extends FizzBuzz {
        val nr: Int
    }
}

trait NatToFizzBuzz[N <: Nat] {
    type Out <: FizzBuzz
    val value: Out
}

sealed trait NatToFizzBuzzInstances1 {
    type Aux[N <: Nat, O <: FizzBuzz] = NatToFizzBuzz[N] { type Out = O }

    implicit def other[N <: Nat](implicit toInt: ToInt[N]): Aux[N, Other[N]] = new NatToFizzBuzz[N] {
        type Out = Other[N]
        val value: FizzBuzz.Other[N] = new Other[N] {
            val nr: Int = toInt()
        }
    }
}

sealed trait NatToFizzBuzzInstances0 extends NatToFizzBuzzInstances1 {
    implicit def fizz[N <: Nat](implicit mod: Mod.Aux[N, _3, _0]): Aux[N, Fizz.type] = new NatToFizzBuzz[N] {
        type Out = Fizz.type
        val value = Fizz
    }

    implicit def buzz[N <: Nat](implicit mod: Mod.Aux[N, _5, _0]): Aux[N, Buzz.type] = new NatToFizzBuzz[N] {
        type Out = Buzz.type
        val value = Buzz
    }
}

object  NatToFizzBuzz extends NatToFizzBuzzInstances0 {
    def apply[N <: Nat](implicit ev: NatToFizzBuzz[N]): NatToFizzBuzz[N] = ev

    implicit def fizzbuzz[N <: Nat](implicit 
            mod: Mod.Aux[N, _15, _0]
            ): Aux[N, FizzAndBuzz.type] = new NatToFizzBuzz[N] {
        type Out = FizzAndBuzz.type
        val value = FizzAndBuzz
    }
}

sealed trait FizzBuzzResult[N <: Nat] { 
    def result: List[FizzBuzz]
}

object FizzBuzzResult {   
    def fizzBuzzToString(fbz: FizzBuzz): String = fbz match {
        case Buzz => "buzz"
        case Fizz => "fizz"
        case FizzAndBuzz => "fizzbuzz"
        case number: Other[_] => number.nr.toString()
    }

    def apply[N <: Nat](implicit res: FizzBuzzResult[N]): String = res.result.map(fizzBuzzToString).reverse.mkString("\n")

    type Aux[N <: Nat] = FizzBuzzResult[N] { type Out = NatToFizzBuzz[N] }

    implicit val fizzbuzz0 = new FizzBuzzResult[Zero] {
        def result: List[FizzBuzz] = List.empty
    }

    implicit def fizzbuzz1[A <: Nat](implicit
       fz: FizzBuzzResult[A],
       next: NatToFizzBuzz[Succ[A]]      
    ): FizzBuzzResult[Succ[A]] = new FizzBuzzResult[Succ[A]] {
        def result: List[FizzBuzz] = next.value :: fz.result
    }
}

Nat.scala

package sandbox

object Nat {
    sealed trait Nat {
      type N <: Nat
    }
    class Zero extends Nat {
      type N = Zero
    }
    case class Succ[P <: Nat]() extends Nat {
      type N = Succ[P]
    }
  
    type _0 = Zero
    type _1 = Succ[Zero]
    type _2 = Succ[_1]
    type _3 = Succ[_2]
    type _4 = Succ[_3]
    type _5 = Succ[_4]
    type _6 = Succ[_5]
    type _7 = Succ[_6]
    type _8 = Succ[_7]
    type _9 = Succ[_8]
    type _10 = Succ[_9]
    type _11 = Succ[_10]
    type _12 = Succ[_11]
    type _13 = Succ[_12]
    type _14 = Succ[_13]
    type _15 = Succ[_14]
    type _16 = Succ[_15]

    trait Sum[A <: Nat, B <: Nat] {
      type Out <: Nat
    }
  
    object Sum {
      def apply[A <: Nat, B <: Nat](implicit sum: Sum[A, B]): Aux[A, B, sum.Out] =
        sum
  
      type Aux[A <: Nat, B <: Nat, C <: Nat] = Sum[A, B] { type Out = C }
  
      implicit def sum0[B <: Nat]: Aux[Zero, B, B] = new Sum[Zero, B] {
        type Out = B
      }
      implicit def sum[A <: Nat, B <: Nat, C <: Nat](
          implicit sum: Sum.Aux[A, Succ[B], C]
      ): Sum.Aux[Succ[A], B, C] = new Sum[Succ[A], B] { type Out = C }
    }
  
    trait Prod[A <: Nat, B <: Nat] {
      type Out <: Nat
    }
  
    object Prod {
      def apply[A <: Nat, B <: Nat](
          implicit prod: Prod[A, B]
      ): Aux[A, B, prod.Out] = prod
  
      type Aux[A <: Nat, B <: Nat, C <: Nat] = Prod[A, B] { type Out = C }
  
      implicit def prod0[B <: Nat]: Aux[Zero, B, Zero] = new Prod[Zero, B] {
        type Out = Zero
      }
      implicit def prod1[A <: Nat, B <: Nat, C <: Nat, D <: Nat](
          implicit
          prod: Aux[A, B, C],
          sum: Sum.Aux[B, C, D]
      ): Aux[Succ[A], B, D] = new Prod[Succ[A], B] { type Out = D }
    }
  
    trait Diff[A <: Nat, B <: Nat] {
      type Out <: Nat
    }
  
    object Diff {
      def apply[A <: Nat, B <: Nat](
          implicit diff: Diff[A, B]
      ): Aux[A, B, diff.Out] = diff
  
      type Aux[A <: Nat, B <: Nat, C <: Nat] = Diff[A, B] { type Out = C }
  
      implicit def diff0[A <: Nat]: Aux[A, Zero, A] = new Diff[A, Zero] {
        type Out = A
      }
      implicit def diff1[A <: Nat, B <: Nat, C <: Nat](
          implicit diff: Aux[A, B, C]
      ): Aux[Succ[A], Succ[B], C] = new Diff[Succ[A], Succ[B]] {
        type Out = C
      }
    }
  
    trait LT[A <: Nat, B <: Nat]
  
    object LT {
      def apply[A <: Nat, B <: Nat](implicit lt: A < B): LT[A, B] = lt
  
      type <[A <: Nat, B <: Nat] = LT[A, B]
  
      implicit def lt1[B <: Nat] = new <[Zero, Succ[B]] {}
      implicit def lt2[A <: Nat, B <: Nat](implicit lt: A < B) =
        new <[Succ[A], Succ[B]] {}
    }
  
    trait Div[A <: Nat, B <: Nat] {
      type Out <: Nat
    }
  
    object Div {
      def apply[A <: Nat, B <: Nat](implicit div: Div[A, B]): Aux[A, B, div.Out] =
        div
  
      type Aux[A <: Nat, B <: Nat, C <: Nat] = Div[A, B] { type Out = C }
  
      implicit def div1[A <: Nat]: Aux[Zero, A, Zero] = new Div[Zero, A] {
        type Out = Zero
      }
      implicit def div2[A <: Nat, B <: Nat](
          implicit lt: LT[A, B]
      ): Aux[A, B, Zero] = new Div[A, B] { type Out = Zero }
      implicit def div3[A <: Nat, B <: Nat, C <: Nat, D <: Nat](
          implicit diff: Diff.Aux[Succ[A], B, C],
          div: Aux[C, B, D]
      ): Aux[Succ[A], B, Succ[D]] =
        new Div[Succ[A], B] { type Out = Succ[D] }
  
    }
  
    trait Mod[A <: Nat, B <: Nat] {
      type Out <: Nat
    }
  
    object Mod {
      def apply[A <: Nat, B <: Nat](implicit mod: Mod[A, B]): Aux[A, B, mod.Out] =
        mod
  
      type Aux[A <: Nat, B <: Nat, C <: Nat] = Mod[A, B] { type Out = C }
  
      implicit def mod1[A <: Nat, B <: Nat, C <: Nat, D <: Nat, E <: Nat](
          implicit div: Div.Aux[A, B, C],
          prod: Prod.Aux[C, B, D],
          diff: Diff.Aux[A, D, E]
      ): Aux[A, B, E] = new Mod[A, B] { type Out = E }
    }
  
    trait ToInt[N <: Nat] {
      def apply(): Int
    }
  
    object ToInt {
      def apply[N <: Nat](implicit toInt: ToInt[N]): ToInt[N] = toInt
  
      class Inst[N <: Nat](i: Int) extends ToInt[N] {
        def apply(): Int = i
      }
  
      implicit val toInt0: ToInt[_0] = new Inst[_0](0)
  
      implicit def toIntSucc[N <: Nat](implicit toIntN: ToInt[N]) =
        new ToInt[Succ[N]] {
          def apply(): Int = toIntN() + 1
        }
  
    }
  }