Scala type level programming - representing a hierarchy

Question

I'm learning about type level programming in Scala and I'm curious if it's possible to represent a tree or hierarchy using type level programming.

The simple case would be a multi-level tree

A_
  |
  B_
    |C
    |D
  |     
  E

How would one represent such a structure?

Answer 1

There are lots of ways you can represent a heterogeneous tree in Scala, with one of the simplest being something like this:

type MyTreeShape[A, B, C, D, E] = (A, (B, (C, D), E))

This has some limitations, though (like the fact that you can't have a tuple as the value of a leaf, since we're using tuple-ness in our representation). For the rest of this answer I'll be using a slightly more complex representation involving Shapeless's HList:

import shapeless._

type MyTreeShape[A, B, C, D, E] =
  A ::
    (B ::
      (C :: HNil) ::
      (D :: HNil) ::
      HNil) ::
    (E :: HNil) ::
    HNil

Here a tree is an HList whose head is the value and whose tail is an HList of child trees.

If we want to do anything usefully generic with these kinds of trees, we'll need some type classes. I'll write up a quick depth-first FlattenTree on the model of the type classes in Shapeless's ops.hlist package as an example. Other type classes for size, depth, etc. can be implemented similarly.

Here's the type class and a convenience method that'll make it easy to use:

trait FlattenTree[T <: HList] extends DepFn1[T] { type Out <: HList }

def flattenTree[T <: HList](t: T)(implicit f: FlattenTree[T]): f.Out = f(t)

Now for instances, which we'll put in the companion object:

object FlattenTree {
  type Aux[T <: HList, Out0 <: HList] = FlattenTree[T] { type Out = Out0 }

  implicit def flattenTree[H, T <: HList](implicit
    tf: FlattenForest[T]
  ): Aux[H :: T, H :: tf.Out] = new FlattenTree[H :: T] {
    type Out = H :: tf.Out

    def apply(t: H :: T): H :: tf.Out = t.head :: tf(t.tail)
  }
}

Note that this needs a helper type class, FlattenForest:

trait FlattenForest[F <: HList] extends DepFn1[F] { type Out <: HList }

object FlattenForest {
  type Aux[F <: HList, Out0 <: HList] = FlattenForest[F] { type Out = Out0 }

  implicit val hnilFlattenForest: Aux[HNil, HNil] = new FlattenForest[HNil] {
    type Out = HNil

    def apply(f: HNil): HNil = HNil
  }

  implicit def hconsFlattenForest[
    H <: HList,
    OutH <: HList,
    T <: HList,
    OutT <: HList
  ](implicit
    hf: FlattenTree.Aux[H, OutH],
    tf: Aux[T, OutT],
    pp: ops.hlist.Prepend[OutH, OutT]
  ): Aux[H :: T, pp.Out] = new FlattenForest[H :: T] {
    type Out = pp.Out

    def apply(f: H :: T): pp.Out = pp(hf(f.head), tf(f.tail))
  }
}

Now we can use it like this:

val myTree: MyTreeShape[String, Int, Char, Symbol, Double] =
  "foo" :: (10 :: HList('a') :: HList('z) :: HNil) :: HList(0.0) :: HNil

val flattened = flattenTree(myTree)

And let's show the static type is appropriate:

flattened: String :: Int :: Char :: Symbol :: Double :: HNil

And that's exactly what we want.

You could do all this without Shapeless, but it would involve an incredible amount of boilerplate.