Scala类型级编程--表示层次结构

Question

我正在学习Scala中的类型级编程，我很好奇是否可以使用类型级编程来表示树或层次结构。

简单的例子是一棵多层次的树。

A_
  |
  B_
    |C
    |D
  |     
  E

怎样才能代表这样的结构？

Answer 1

在Scala中有许多表示异构树的方法，其中最简单的方法如下：

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

尽管如此，这还是有一些限制的(比如不能将元组作为叶的值，因为我们在表示中使用元组)。对于这个答案的其余部分，我将使用一个涉及无形的HList的稍微复杂一些的表示。

import shapeless._

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

在这里，树是一个HList，它的头是值，它的尾巴是子树的HList。

如果我们想对这些类型的树执行任何有用的泛型操作，那么我们将需要一些类型类。作为一个例子，我将在无形的ops.hlist包中编写一个关于类型类模型的快速深度优先的ops.hlist。大小、深度等的其他类型类也可以类似地实现。

下面是类型类和一种方便的方法，使其易于使用：

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

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

现在，对于实例，我们将把它放在伴生对象中：

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)
  }
}

注意，这需要一个助手类型类，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))
  }
}

现在我们可以这样使用它：

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

val flattened = flattenTree(myTree)

让我们展示一下静态类型是合适的：

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

这正是我们想要的。

你可以在没有无形状的情况下完成这一切，但这将涉及到大量的样板。