Home About
Kotlin , Tree Data Structure

木構造(Tree)の各要素に対してマップしたい Kotlin

リストの各要素に対してマップするというのは簡単。 これと同じことを 木構造 に対して行うにはどうすればいいのか?

たとえば、 a,b,c という文字列のリストがあったとして、それに prefix として _ を追加したい、という場合。

次のように記述するだけです。

_listOf("a","b","c").map {
    // prefix _ を追加する処理をここに記述
}

具体的に書けば次のようになります。

// main.kts
val list0 = listOf("a","b","c")
val list1 = list0.map { "_${it}" }
println( list1 )

実行すると意図通り _ が追加されたリストを得ることができます。

$ kotlin main.kts
[_a, _b, _c]

同じように 木構造のデータ aTree があったとして、それの各要素に対して prefix _ を追加したい場合を考えます。

aTree.map {
    // 各要素に prefix _ を追加する処理をここに記述
}    

このように 木構造のデータも リストと同じように map できればいいのに。(本当はできるのかもしれない、自分がやり方を知らないだけで。)

ファイルシステム風の木構造データを題材に

具体的に次のような木構造のデータがあったとして、各要素の(ディレクトリ名またはファイル名)の前に _ を追加することを考えます。

- Home
    - Documents 
        - 1.txt
        - 2.txt
    - Images 
        - 3.jpg
        - 4.jpg

まずこのデータを kotlin の木構造データとして表現する必要があります。

まず Tree を定義します。

// main.kts
sealed class Tree {
    data class Leaf(val value: String): Tree()
    data class Node(val value: String, val children: List<Tree>): Tree()
}

これを使って先ほどの ファイルシステムを表現。

val homeDir = Tree.Node("Home", listOf(
    Tree.Node("Documents", listOf(
        Tree.Leaf("1.txt"),
        Tree.Leaf("2.txt"))),
    Tree.Node("Images", listOf(
        Tree.Leaf("3.jpg"),
        Tree.Leaf("4.jpg")))))

println(homeDir)

実行すると次のようになります。(わかりやすいように改行を入れています。)

Node(
  value=Home,
  children=[
    Node(
      value=Documents,
      children=[
        Leaf(value=1.txt),
        Leaf(value=2.txt)]),
    Node(
      value=Images,
      children=[
        Leaf(value=3.jpg),
        Leaf(value=4.jpg)])])

この Tree の各要素に prefix を足す関数 addPrefix を定義。アウトラインはこんな感じです。

val addPrefix: (Tree, String)->Tree = { rootTree, prefix->
    fun f(tree: Tree): Tree {
        // ここで再帰的に 木構造を処理して、その各要素に prefix を追加する.
    }

    f(rootTree)
}

それでは肝心の f 関数を実装します。

val addPrefix: (Tree, String)->Tree = { rootTree, prefix->
    fun f(tree: Tree): Tree {
        return when(tree){
            is Tree.Leaf -> {
                Tree.Leaf("${prefix}${tree.value}")
            }
            is Tree.Node -> {
                Tree.Node("${prefix}${tree.value}", tree.children.map { f(it) })
            }
        }
    }

    f(rootTree)
}

homeDiraddPreffix に適用して結果を確認。

println( addPrefix(homeDir,"_") )

実行すると、各要素にプレフィックス _ を追加できました。(わかりやすいように改行を入れています。)

Node(
  value=_Home,
  children=[
    Node(
      value=_Documents,
      children=[
        Leaf(value=_1.txt),
        Leaf(value=_2.txt)]),
    Node(
      value=_Images,
      children=[
        Leaf(value=_3.jpg),
        Leaf(value=_4.jpg)])])

これで木構造に対して実質的に map することはできたのですが、

addPrefix(homeDir,"_")

のように書く必要があります。 また、ここでは単に prefix 文字列を渡しているだけなので、汎用性がない。 たとえば、suffix を追加したい、と思ったらもう行き詰まってしまいます。

そこで、 FixElementValueF というタイプを定義して、これを渡すように変更します。

typealias FixElementValueF = (String)->String

addPrefix 関数を FixElementValueF を受け取りそれを使って各要素を処理するように変更します。 さらに 関数名も addPrefix ではおかしいので fixEachElement と改名します。

val fixEachElement: (Tree, FixElementValueF)->Tree = { rootTree, fixElementValueF->
    fun f(tree: Tree): Tree {
        return when(tree){
            is Tree.Leaf -> {
                Tree.Leaf("${fixElementValueF(tree.value)}")
            }
            is Tree.Node -> {
                Tree.Node("${fixElementValueF(tree.value)}", tree.children.map { f(it) })
            }
        }
    }

    f(rootTree)
}

この関数を使えば、先ほど同様に prefix に _ を追加するには:

fixEachElement(homeDir, { "_${it}" })

と書けます。また suffix に _ を追加したければ:

fixEachElement(homeDir, { "${it}_" })

とすればOKです。

拡張関数を使う

最後に拡張関数を使って fixEachElement(homeDir, { "_${it}" }) の代わりに homeDir.map { "_${it}" } のように記述できるようにしましょう。

Kotlinの拡張関数についてはこちらのページをご覧ください。

要するに定義した Tree クラスに FixElementValueF を適用できる map 関数を拡張関数として定義すればよい。

fun Tree.map(g: FixElementValueF): Tree {
    return fixEachElement(this, g)
}

これだけです。あとは homeDir.map してみて意図通りの結果が得られるか確認しましょう。

println( homeDir.map( { "_${it}" } ) )

まとめ

それではコード全体を掲載します。

バージョンの確認:

$ kotlin -version
Kotlin version 1.8.10-release-430 (JRE 17.0.11+9-Ubuntu-122.04.1)

main.kts:

val list0 = listOf("a","b","c")
val list1 = list0.map { "${it}.txt" }
println( list1 )

val addPrefix: (Tree, String)->Tree = { rootTree, prefix->
    fun f(tree: Tree): Tree {
        return when(tree){
            is Tree.Leaf -> {
                Tree.Leaf("${prefix}${tree.value}")
            }
            is Tree.Node -> {
                Tree.Node("${prefix}${tree.value}", tree.children.map { f(it) })
            }
        }
    }

    f(rootTree)
}

typealias FixElementValueF = (String)->String

val fixEachElement: (Tree, FixElementValueF)->Tree = { rootTree, fixElementValueF->
    fun f(tree: Tree): Tree {
        return when(tree){
            is Tree.Leaf -> {
                Tree.Leaf("${fixElementValueF(tree.value)}")
            }
            is Tree.Node -> {
                Tree.Node("${fixElementValueF(tree.value)}", tree.children.map { f(it) })
            }
        }
    }

    f(rootTree)
}

sealed class Tree {
    data class Leaf(val value: String): Tree()
    data class Node(val value: String, val children: List<Tree>): Tree()
}



/*
- Home
    - Documents 
        - 1.txt
        - 2.txt
    - Images 
        - 3.jpg
        - 4.jpg
*/

val homeDir = Tree.Node("Home", listOf(
    Tree.Node("Documents", listOf(
        Tree.Leaf("1.txt"),
        Tree.Leaf("2.txt"))),
    Tree.Node("Images", listOf(
        Tree.Leaf("3.jpg"),
        Tree.Leaf("4.jpg")))))

fun Tree.map(g: FixElementValueF): Tree {
    return fixEachElement(this, g)
}

println( homeDir.map( { "_${it}" } ) )
println( homeDir.map( { "${it}_" } ) )

追伸

今のところ Tree.map として FixElementValueF を適用するので Tree.Leaf, Tree.Node の value の書きかえができるだけです。 たとえば、ディレクトリ( Tree.Node ) はそのままで、ファイル( Tree.Leaf ) だけ value を変更したい、という場合に 現状の FixElementValueF では対応できません。

そこで FixElementValueF の定義を次のように変更。

typealias FixElementValueF: (String, Tree)->String

本当は Tree さえ渡せば value はそこから得られるのでこの定義は冗長なのですが、最初のバージョンの FixElementValueF からの 変更という意味では自然なので、今はこのように定義します。

これで map に適用する関数は、このように書けます(先ほどの例の Tree.Leafの名前だけを変更する、という場合):

val g: FixElementValueF = { value, tree->
    when(tree){
        is Tree.Leaf -> { "_${value}" }
        is Tree.Node -> { value }
    }
}

もちろん、この変更にあわせて 拡張関数 map の定義も変更する必要があります。(割愛)

以上です。

Liked some of this entry? Buy me a coffee, please.