typalg.scala

/**
 * build.sbt:
 * 
 * name := "typalg"
 * 
 * scalaVersion := "2.11.1"
 * 
 * libraryDependencies += "org.spire-math" %% "spire" % "0.7.5"
 * 
 * sample sbt session:
 * 
 * scala> import typalg._
 * import typalg._
 * 
 * scala> Card[Boolean]
 * res0: spire.math.Natural = 2
 * 
 * scala> Card[Int]
 * res1: spire.math.Natural = 4294967296
 * 
 * scala> Card[Long]
 * res2: spire.math.Natural = 18446744073709551616
 * 
 * scala> Card[(Long, Long)]
 * res3: spire.math.Natural = 340282366920938463463374607431768211456
 * 
 * scala> Card[Either[Byte, Byte]]
 * res4: spire.math.Natural = 512
 * 
 * scala> Card[Byte => Byte]
 * res5: spire.math.Natural = 32317006071311007300714876688669951960444102669715484032130345427524655138867890893197201411522913463688717960921898019494119559150490921095088152386448283120630877367300996091750197750389652106796057638384067568276792218642619756161838094338476170470581645852036305042887575891541065808607552399123930385521914333389668342420684974786564569494856176035326322058077805659331026192708460314150258592864177116725943603718461857357598351152301645904403697613233287231227125684710820209725157101726931323469678542580656697935045997268352998638215525166389437335543602135433229604645318478604952148193555853611059596230656
 * 
 */
package typalg

import spire.math.{UInt, SafeLong, Natural}

case class Card[A](n: Natural)

object Card {

  import Natural.{zero, one}

  def apply[A](implicit ev: Card[A]): Natural = ev.n

  implicit val nothing: Card[Nothing] = Card(zero)
  implicit val unit: Card[Unit] = Card(one)
  implicit val boolean: Card[Boolean] = Card(Natural(2))
  implicit val byte: Card[Byte] = Card(Natural(256))
  implicit val short: Card[Short] = Card(byte.n * byte.n)
  implicit val char: Card[Char] = Card(short.n)
  implicit val int: Card[Int] = Card(short.n * short.n)
  implicit val float: Card[Float] = Card(int.n)
  implicit val long: Card[Long] = Card(int.n * int.n)
  implicit val double: Card[Double] = Card(long.n)

  implicit def option[A: Card]: Card[Option[A]] =
    Card(Card[A] + one)

  implicit def either[A: Card, B: Card]: Card[Either[A, B]] =
    Card(Card[A] + Card[B])

  implicit def tuple2[A: Card, B: Card]: Card[(A, B)] =
    Card(Card[A] * Card[B])

  implicit def function0[A: Card]: Card[() => A] =
    Card(Card[A])

  implicit def function1[A: Card, B: Card]: Card[A => B] =
    Card(Card[B] pow Card[A])

  implicit def function2[A: Card, B: Card, C: Card]: Card[(A, B) => C] =
    Card(Card[C] pow (Card[A] + Card[B]))

  implicit def set[A: Card]: Card[Set[A]] =
    Card(Card[A => Boolean])

  implicit def map[A: Card, B: Card]: Card[Map[A, B]] =
    Card(Card[A => Option[B]])

  implicit def array[A: Card]: Card[Array[A]] =
    if (Card[A] == 0) Card(zero)
    else if (Card[A] == 1) Card(Natural(0x80000000L))
    else Card { 
      val a = SafeLong(Card[A])
      val x: SafeLong = a pow 0x40000000
      val n = SafeLong.one - (x pow 2)
      val d = SafeLong.one - a
      Natural((n / d).toBigInt)
    }
}