Converting a case class hierarchy to scalaz.Tree with Shapeless

Question

Consider the following hierarchy:

sealed trait Ex
case class Lit(value: Int) extends Ex
case class Var(name: Char) extends Ex
case class Add(a: Ex, b: Ex) extends Ex

I'd like to convert expressions such as val ex = Add(Lit(0),Add(Lit(1),Var('a'))) into a scalaz.Tree[Either[Class[Any],Any]]], which in this case would give:

-\/(class Add)
|
+- -\/(class Lit)
|  |
|  `- \/-(0)
|
`- -\/(class Add)
   |
   +- -\/(class Lit)
   |  |
   |  `- \/-(1)
   |
   `- -\/(class Var)
      |
      `- \/-(a)

Which is the most appropriate Shapeless functionality/example to start from for doing this?

Answer 1

First for a disclaimer: if you're planning to use this in real code, I think it's almost certainly a bad idea. It'd be better to try to use Shapeless to do what you're trying to do directly rather than going through this type-unsafe representation. But it's a fun problem, so here goes.

(Oh, and another disclaimer: this implementation is off the top of head and there may be nicer ways to accomplish this.)

First for a helper type class (note that all of the code in the three sections below will need to be defined together—you can use :paste if you're in a REPL):

import scalaz.{ Show, Tree, \/ }, scalaz.syntax.either._
import shapeless._, ops.hlist.ToTraversable

trait TreeifyCc[A, C] {
  def apply(tf: Treeify[A], c: C): Tree[Class[_] \/ Any]
}

trait LowPriorityTreeifyCc {
  implicit def singleMemberTreeifyCc[A, C, R <: HList, X](implicit
    gen: Generic.Aux[C, R],
    ev: R <:< (X :: HNil)
   ): TreeifyCc[A, C] = new TreeifyCc[A, C] {
    def apply(tf: Treeify[A], c: C): Tree[Class[_] \/ Any] = Tree.Node(
      c.getClass.left,
      Stream(Tree.Leaf(ev(gen.to(c)).head.right))
    )
  }
}

object TreeifyCc extends LowPriorityTreeifyCc {
  implicit def recursiveTreeifyCc[A, C, R <: HList](implicit
    gen: Generic.Aux[C, R],
    ts: ToTraversable.Aux[R, Stream, A]
  ): TreeifyCc[A, C] = new TreeifyCc[A, C] {
    def apply(tf: Treeify[A], c: C): Tree[Class[_] \/ Any] =
      Tree.Node(c.getClass.left, ts(gen.to(c)).map(tf(_)))
  }
}

And another helper type class:

trait TreeifyAdt[A, C] {
  def apply(tf: Treeify[A], c: C): Tree[Class[_] \/ Any]
}

object TreeifyAdt {
  implicit def cnilTreeifyAdt[A]: TreeifyAdt[A, CNil] =
    new TreeifyAdt[A, CNil] {
      def apply(tf: Treeify[A], c: CNil): Tree[Class[_] \/ Any] =
        sys.error("impossible")
    }

  implicit def cconsAdt[A, H, T <: Coproduct](implicit
    cc: TreeifyCc[A, H],
    ta: TreeifyAdt[A, T]
  ): TreeifyAdt[A, H :+: T] = new TreeifyAdt[A, H :+: T] {
    def apply(tf: Treeify[A], c: H :+: T): Tree[Class[_] \/ Any] = c match {
      case Inl(h) => cc(tf, h)
      case Inr(t) => ta(tf, t)
    }
  }
}

And the type class we actually care about:

trait Treeify[A] {
  def apply(a: A): Tree[Class[_] \/ Any]
}

object Treeify {
  implicit def treeifyAdt[A, R <: Coproduct](implicit
    gen: Generic.Aux[A, R],
    adt: TreeifyAdt[A, R]
  ): Treeify[A] = new Treeify[A] {
    def apply(a: A): Tree[Class[_] \/ Any] = adt(this, gen.to(a))
  }

  def toTree[A](a: A)(implicit tf: Treeify[A]): Tree[Class[_] \/ Any] = tf(a)
}

And we can use it like this:

scala> val ex: Ex = Add(Lit(0), Add(Lit(1), Var('a')))
ex: Ex = Add(Lit(0),Add(Lit(1),Var(a)))

scala> Treeify.toTree(ex).drawTree(scalaz.Show.showFromToString)
res0: String =
"-\/(class Add)
|
+- -\/(class Lit)
|  |
|  `- \/-(0)
|
`- -\/(class Add)
   |
   +- -\/(class Lit)
   |  |
   |  `- \/-(1)
   |
   `- -\/(class Var)
      |
      `- \/-(a)
"

This will work for any ADT where all of the leaves either have a single member or one or more recursive members.