GenTrie

/**
 * reference: http://www.cs.ox.ac.uk/ralf.hinze/publications/GGTries/Encode.lhs
 */
object GenTrie {

  sealed trait Bit
  case object △ extends Bit
  case object ▲ extends Bit

  type Bits = List[Bit]

  trait Encodable[A] {
    def encode(a: A): List[Bit]
  }

  implicit val encodableUnit = new Encodable[Unit] {
    override def encode(x: Unit): List[Bit] = List()
  }

  implicit val encodableBit = new Encodable[Bit] {
    override def encode(x: Bit): List[Bit] = List(x)
  }

  implicit def encodableList[V](implicit v0: Encodable[V]) = new Encodable[List[V]] {
    override def encode(x: List[V]): List[Bit] = x match {
      case Nil => List(△)
      case x :: xs => List(▲) ++ v0.encode(x) ++ encode(xs)
    }
  }

  implicit val encodablePosInt = new Encodable[Int] {
    override def encode(x: Int): List[Bit] = x.toBinaryString.toList.map {
      case '0' => △
      case '1' => ▲
    }
  }

}