階層構造のデータから特定のプロパティを抽出して、フラットにする

json のような階層構造を持つデータから特定のプロパティを再帰的に探索して、平坦なリストにしたものを取得したい場面に出会ったのでメモする。

データ構造

case class Tree(
    value: Int,
    children: List[Tree]
)

木構造？というか、自身のリストを持つようなデータ構造。

実装

再帰でなんとかする

case class Tree(value: Int, children: List[Tree]) {
  val values: List[Int] = {
    @tailrec
    def loop(children: List[Tree], vs: List[Int]): List[Int] = {
      children match {
        case Nil => vs
        case ::(head, next) => loop(next ++ head.children, vs appended  head.value)
      }
    }
    loop(children, List(value))
  }
}

実行結果

val tree = {
  Tree(
    1,
    List(
      Tree(2, List.empty),
      Tree(3, List.empty),
      Tree(4, List(
        Tree(5, List.empty),
        Tree(6, List.empty),
        Tree(7, List(
          Tree(8, List(
            Tree(9, List(
              Tree(12, List(
                Tree(13, List.empty)
              ))
            ))
          )),
          Tree(10, List(
            Tree(11, List.empty)
          ))
        ))
      ))
    )
  )
}

println(tree.values) // List(1, 2, 3, 4, 5, 6, 7, 8, 10, 9, 11, 12, 13)</pre>

うん。できてそう。

ちゃんとテストしたわけではない。

問題点

自身のプロパティにアクセスするような実装のため、ほぼ同じ処理なのに共通化しづらいのが難点。再帰的にとってくるような処理をあっちこっちでやると同じ処理が散らばる。