Есть много способов представить разнородное дерево в Scala, один из самых простых из них выглядит примерно так:
type MyTreeShape[A, B, C, D, E] = (A, (B, (C, D), E))
Однако у этого есть некоторые ограничения (например, тот факт, что вы не можете иметь кортеж в качестве значения листа, поскольку мы используем кортежность в нашем представлении). Для остальной части этого ответа я буду использовать немного более сложное представление, включающее Shapeless HList
:
import shapeless._
type MyTreeShape[A, B, C, D, E] =
A ::
(B ::
(C :: HNil) ::
(D :: HNil) ::
HNil) ::
(E :: HNil) ::
HNil
Здесь дерево — это HList
, голова которого — значение, а хвост — HList
дочерних деревьев.
Если мы хотим сделать с такими деревьями что-то полезное, нам понадобятся классы типов. В качестве примера я напишу краткое описание FlattenTree
модели классов типов в пакете Shapeless 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
И это именно то, что мы хотим.
Вы могли бы сделать все это без Shapeless, но это потребовало бы невероятного количества шаблонов.
person
Travis Brown
schedule
03.03.2015
type Tree[A, B, C, D, E] = (A, (B, C :: D :: HNil) :: E :: HNil)
сHList
Shapeless (или что-то подобное с кортежами), а затем следовать шаблонамops
Shapeless для реализации класса типаSize
и т. д. Если вас интересует решение Shapeless, я был бы рад опубликовать что-то позже. - person Travis Brown   schedule 02.03.2015