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

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)

うん。できてそう。

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

問題点

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

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト /  変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト /  変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト /  変更 )

%s と連携中

%d人のブロガーが「いいね」をつけました。