|
|
package generic
import Shapes._
/** enum Tree[T] {
* case True extends Tree[Boolean]
* case False extends Tree[Boolean]
* case Zero extends Tree[Int]
* case Succ(n: Tree[Int]) extends Tree[Int]
* case Pred(n: Tree[Int]) extends Tree[Int]
* case IsZero(n: Tree[Int]) extends Tree[Boolean]
* case If(cond: Boolean, thenp: Tree[T], elsep: Tree[T])
* }
*/
sealed trait Tree[TR] extends Enum
object Tree {
val True: Tree[Boolean] = new Tree[Boolean] {
def enumTag = 0
override def toString = "True"
}
implicit def TrueSingleton: Singleton[True.type] = new Singleton[True.type](True)
val False: Tree[Boolean] = new Tree[Boolean] {
def enumTag = 1
override def toString = "False"
}
implicit def FalseSingleton: Singleton[False.type] = new Singleton[False.type](False)
val Zero: Tree[Int] = new Tree[Int] {
def enumTag = 2
override def toString = "Zero"
}
implicit def ZeroSingleton: Singleton[Zero.type] = new Singleton[Zero.type](Zero)
abstract case class Succ(n: Tree[Int]) extends Tree[Int] {
def enumTag = 3
}
object Succ {
def apply(x: Tree[Int]): Tree[Int] = new Succ(x) {}
implicit def SuccShape: Succ `shaped` Tree[Int] = new (Succ `shaped` Tree[Int]) {
def toShape(x: Succ) = x.n
def fromShape(x: Tree[Int]) = new Succ(x) {}
}
}
abstract case class Pred(n: Tree[Int]) extends Tree[Int] {
def enumTag = 4
}
object Pred {
def apply(x: Tree[Int]): Tree[Int] = new Pred(x) {}
implicit def PredShape: Pred `shaped` Tree[Int] = new (Pred `shaped` Tree[Int]) {
def toShape(x: Pred) = x.n
def fromShape(x: Tree[Int]) = new Pred(x) {}
}
}
abstract case class IsZero(n: Tree[Int]) extends Tree[Boolean] {
def enumTag = 5
}
object IsZero {
def apply(x: Tree[Int]): Tree[Boolean] = new IsZero(x) {}
implicit def IsZeroShape: IsZero `shaped` Tree[Int] = new (IsZero `shaped` Tree[Int]) {
def toShape(x: IsZero) = x.n
def fromShape(x: Tree[Int]) = new IsZero(x) {}
}
}
abstract case class If[T](cond: Tree[Boolean], thenp: Tree[T], elsep: Tree[T]) extends Tree[T] {
def enumTag = 6
}
object If {
def apply[T](cond: Tree[Boolean], thenp: Tree[T], elsep: Tree[T]): Tree[T] = new If(cond, thenp, elsep) {}
type Shape[T] = Prod[Tree[Boolean], Prod[Tree[T], Tree[T]]]
implicit def IfShape[T]: If[T] `shaped` Shape[T] =
new (If[T] `shaped` Shape[T]) {
def toShape(x: If[T]) = Prod(x.cond, Prod(x.thenp, x.elsep))
def fromShape(x: Shape[T]) = new If(x.fst, x.snd.fst, x.snd.snd) {}
}
}
type Shape[T] =
Sum[
Sum[
Sum[True.type, False.type],
Sum[Zero.type, Succ]],
Sum[
Sum[Pred, IsZero],
If[T]]]
implicit def TreeShape[TS]: Tree[TS] `unfolds` Shape[TS]
= new (Tree[TS] `shaped` Shape[TS]) {
def toShape(x: Tree[TS]) = x match {
case True => Fst(Fst(Fst(True)))
case False => Fst(Fst(Snd(False)))
case Zero => Fst(Snd(Fst(Zero)))
case x: Succ => Fst(Snd(Snd(x)))
case x: Pred => Snd(Fst(Fst(x)))
case x: IsZero => Snd(Fst(Snd(x)))
case x: If[TS] => Snd(Snd(x))
}
def fromShape(x: Shape[TS]): Tree[TS] = x match {
case Fst(Fst(Fst(_true))) => _true.asInstanceOf[Tree[TS]]
case Fst(Fst(Snd(_false))) => _false.asInstanceOf[Tree[TS]]
case Fst(Snd(Fst(zero))) => zero.asInstanceOf[Tree[TS]]
case Fst(Snd(Snd(succ))) => succ.asInstanceOf[Tree[TS]]
case Snd(Fst(Fst(pred))) => pred.asInstanceOf[Tree[TS]]
case Snd(Fst(Snd(isZero))) => isZero.asInstanceOf[Tree[TS]]
case Snd(Snd(_if)) => _if
}
}
}
|