fizzbuzz in the scala type system

fizzbuzz.scala

package fizzbuzz

// This is church encoding of natural numbers
sealed trait Num {
  def toInt : Int
  override def toString = toInt.toString
}

final case object Z extends Num {
  def toInt : Int = 0
}

final case class Succ[N <: Num](p: Num) extends Num {
  def toInt : Int = p.toInt + 1
}

object Num {
  implicit val zero : Z.type = Z
  implicit def next[N <: Num](implicit n: N) : Succ[N] = new Succ[N](n)

  // these are just for convenience,  they aren't strictly needed
  type _0 = Z.type
  type _1 = Succ[Z.type]
  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]; type _17 = Succ[_16]; type _18 = Succ[_17]; type _19 = Succ[_18]; type _20 = Succ[_19]; type _21 = Succ[_20]; type _22 = Succ[_21]; type _23 = Succ[_22]; type _24 = Succ[_23]; type _25 = Succ[_24]; type _26 = Succ[_25]
}

sealed trait FizzBuzzNum[N]

/**
 * A natural number divisible by neither 5 nor 3
 */
class Neither[T <: Num](n: T) extends FizzBuzzNum[T] {
  override def toString = n.toString
}

/**
 * A natural number divisible by 3
 */
class Fizz[T <: Num] extends FizzBuzzNum[T] {
  override def toString = "Fizz"
}

/**
 * A natural number divisible by 5
 */
class Buzz[T <: Num] extends FizzBuzzNum[T] {
  override def toString = "Buzz"
}

/**
 * A natural number divisible by both 5 and 3
 */
class FizzBuzz[T <: Num] extends FizzBuzzNum[T] {
  override def toString = "FizzBuzz"
}

// We create a subtype hierarchy to prioritize the implicits We need
// to do this so that FizzBuzz will be searched for before it tries to
// find a Fizz or a Buzz
trait FizzBuzzNum3 {
  import Num._

  /**
   * Lowest priority implicit, if nothing else was found, it is a Neither
   */
  implicit def notEither[N <: Num](implicit n: N) : Neither[N] = new Neither[N](n)

  /** zero is divisible by 3 */
  implicit val zeroThree : Fizz[_0] = new Fizz[_0]
}
trait FizzBuzzNum2 extends FizzBuzzNum3 {
  import Num._

  /**
   * if we can find implicit evidence that N is divisible by three,
   * then provide evidence that N+3 is also
   */
  implicit def three[N <: Num](implicit prevFizz: Fizz[N] ) : Fizz[Succ[Succ[Succ[N]]]] = new Fizz[Succ[Succ[Succ[N]]]]

  /** zero is divisible by 5 */
  implicit val zeroFive : Buzz[_0] = new Buzz[_0]
}
trait FizzBuzzNum1 extends FizzBuzzNum2 {
  import Num._

  /**
   * if we can find implicit evidence that N is divisible by five,
   * then provide evidence that N+5 is also
   */
  implicit def five[N <: Num](implicit prevBuzz : Buzz[N]) : Buzz[Succ[Succ[Succ[Succ[Succ[N]]]]]] = new Buzz[Succ[Succ[Succ[Succ[Succ[N]]]]]]
  import Num._

  /** zero is divisible by 15 */
  implicit val zeroFifteen : FizzBuzz[_0] = new FizzBuzz[_0]
}
trait FizzBuzzNum0 extends FizzBuzzNum1 {
  import Num._

  /**
   * if we can find implicit evidence that N is divisible by fifteen,
   * then provide evidence that N+15 is also
   */
  implicit def fifteen[N <: Num](implicit prevFizzBuzz: FizzBuzz[N]): FizzBuzz[Succ[Succ[Succ[Succ[Succ[Succ[Succ[Succ[Succ[Succ[Succ[Succ[Succ[Succ[Succ[N]]]]]]]]]]]]]]]] = new FizzBuzz[Succ[Succ[Succ[Succ[Succ[Succ[Succ[Succ[Succ[Succ[Succ[Succ[Succ[Succ[Succ[N]]]]]]]]]]]]]]]]
}

object FizzBuzzNum extends FizzBuzzNum0

sealed trait FBList[To <: Num]

case class ::[N <: Num, T <: FBList[N]](head: FizzBuzzNum[Succ[N]], tail: T) extends FBList[Succ[N]] {
  // print backwards, since we are consing up the list in reverse
  override def toString = tail.toString + "," + head.toString
}

/**
 * End of the list, which is allways FizzBuzz(1)
 */
case object FBNil extends FBList[Num._1] {
  override def toString = "1"
}
 
object FBList {
  import FizzBuzzNum._
  import Num._

  // All lists end in 1
  implicit val endOfList : FBList[_1] = FBNil

  // Go find implicit evidence of the tail of the list, then find the FizzBuzzNum to stick on the head
  implicit def moreOfList[N <: Num](implicit fblist: FBList[N], fbb: FizzBuzzNum[Succ[N]]) : FBList[Succ[N]] = fizzbuzz.::(fbb, fblist)

}

// $ scala -cp . fizzbuzz.Main 
// 1,2,Fizz,4,Buzz,Fizz,7,8,Fizz,Buzz,11,Fizz,13,14,FizzBuzz,16,17,Fizz,19,Buzz,Fizz,22,23,Fizz,Buzz,26

object Main extends App {
  import Num._
  
  val l = implicitly[FBList[_26]]
  println(l)
}