异构树的类型级展平

Question

我正在学习 Shapeless 并实现了一个简单的异构树

我希望能够提取保留类型信息的标签。我很努力，但还没有草图来展示解决方案。任何帮助表示赞赏！

object TreeTest {

  import shapeless._

  case class HTree[A, F <: HList](label: A, forest: F) {
    def withBranch[T, FF <: HList](tree: HTree[T, FF]): HTree[A, HTree[T, FF] :: F] = new HTree(label, tree :: forest)
  }

  object HTree {
    def apply[A](label: A) = new HTree[A, HNil](label, HNil)
  }

  val t1 = HTree(1)
  val t2 = HTree("1")
  val t3 = t2.withBranch(HTree(2.0))
  val t4: HTree[Int, HTree[String, HTree[Double, HNil] :: HNil] :: HNil] = t1.withBranch(t3)

  def labels[A, F <: HList](t: HTree[A, F]) = ???

  val flattened: Int :: String :: Double :: HNil = labels(t4)
}

Answer 1

我能够创建一个递归多态函数来提取你的 HTree 的标签：

import shapeless._, ops.hlist._

object getLabels extends Poly1 {
  implicit def caseHTree[A, F <: HList, M <: HList](implicit 
    fm: FlatMapper.Aux[getLabels.type, F, M],
    prepend: Prepend[A :: HNil, M]
  ) : Case.Aux[HTree[A, F], prepend.Out] = 
    at[HTree[A, F]](tree => prepend(tree.label :: HNil, fm(tree.forest)))
}

它将当前 HTree 的标签添加到它递归获取的分支的标签（在 forest 上平面映射）。

t4 的结果是：

getLabels(t4)
// Int :: String :: Double :: HNil = 1 :: 1 :: 2.0 :: HNil

异构树的类型级展平

Type-level flattening of a heterogenous Tree

scala

shapeless