要するに Tree 構造のものをフラットにしたい。
たとえば、特定のディレクトリ以下から PDF ファイルのみを抜き出してなにか処理するとか、そんなタスクに使うコード。 もちろん、シェルスクリプトで書けば以下のように簡単に記述することができる。
$ find . -name "*.pdf"
こうして得たファイルリストを元に何か処理すれば済む場合はそれでよいのですが、つまり:
$ find . -name "*.pdf" | xargs <do something>
しかし、シェルスクリプトを使いたくないとか、収集するコードと処理するコードをまとめて kotlin や javascript で記述したいなどという場合がある。
次のようなツリー構造（のファイルシステム）を想定します。
- Home/
- Documents/
- hello.txt
- world.txt
- Desktop/
- hello.png
- Trash/
- world.png
説明の都合上、ここではディレクトリはその名前の末尾に / を入れて表現します。
kotlin で実装します。
このツリー構造を実装するために File データクラスを用意します。
data class File(val name: String, val isDir: Boolean, val children: List<File>)
続いて、 ディレクトリとファイルを作り出すヘルパー関数を定義。
val emptyList = listOf<File>()
val toFile: (String)-> File = { name->
File(name, false, emptyList)
}
val toDir : (String, List<File>)-> File = { name, children->
File(name, true, children)
}
これらを使って先ほどのツリーを実装すると次のようになります。
val homeDir = toDir(
"Home",
listOf<File>(
toDir(
"Documents",
listOf<File>(
toFile("hello.txt"),
toFile("world.txt"))
),
toDir(
"Desktop",
listOf<File>(
toFile("hello.png"),
toDir(
"Trash",
listOf<File>(
toFile("world.png")
))))))
それでは、このツリー構造をフラットに畳みます。
これから書いていくコードのためのヘルパー関数 listFiles を用意。 これは、ディレクトリとしての File がきたら、そのディレクトリ内の File のリストを返す関数です。
val listFiles: (File)-> List<File> = { file->
if( !file.isDir ){ emptyList } else { file.children }
}
フラットに畳むための関数 fileRecurse を定義します。 そのシグニチャーはこれ。
val fileRecurse: (File)->List<File>
File を List<File> にするということ、そのままですね。
この関数は再帰関数なので関数リテラルではなく、普通の関数として実装します。
fun fileRecurse(file: File): List<File> {
return if( !file.isDir ){
listOf(file)
} else {
listOf(file) + listFiles(file).map { childFile->
fileRecurse(childFile)
}.flatten()
}
}
たとえば Desktop ディレクトリをこの fileRecurse に適用した場合、次のような再帰処理イメージになります。
一回目
[<desktop/>] +
[fileRecurse(<hello.png>),
fileRecurse(<Trash/>)]
二回目
[<desktop/>] +
[[<hello.png>] +
[<Trash/>] + [fileRecurse(<world.png>)]]
三回目
[<desktop/>] +
[[<hello.png>] +
[<Trash/>] + [[<world.png>]]
このイメージによる説明では、flatten() を省略しているので、リストのリストみたいになっていますが、実際のコードは flatten() が入っているので、リストはネストしません。
それでは実際に homeDir をフラットにしてみます。
val result = fileRecurse( homeDir )
println( result )
ここまでのコードは main.kts に記述してあるとして、 それを実行して、その結果を見てみます。
$ kotlinc -script main.kts
[File(name=Home, isDir=true, children=[File(name=Documents, isDir=true, children=[File(name=hello.txt, isDir=false, children=[]), File(name=world.txt, isDir=false, children=[])]), File(name=Desktop, isDir=true, children=[File(name=hello.png, isDir=false, children=[]), File(name=Trash, isDir=true, children=[File(name=world.png, isDir=false, children=[])])])]), File(name=Documents, isDir=true, children=[File(name=hello.txt, isDir=false, children=[]), File(name=world.txt, isDir=false, children=[])]), File(name=hello.txt, isDir=false, children=[]), File(name=world.txt, isDir=false, children=[]), File(name=Desktop, isDir=true, children=[File(name=hello.png, isDir=false, children=[]), File(name=Trash, isDir=true, children=[File(name=world.png, isDir=false, children=[])])]), File(name=hello.png, isDir=false, children=[]), File(name=Trash, isDir=true, children=[File(name=world.png, isDir=false, children=[])]), File(name=world.png, isDir=false, children=[])]
（わからん）
簡単な出力に直します。
val result = fileRecurse( homeDir ).map {
if( it.isDir ){ "${it.name}/" } else { "${it.name}" }
}
println( result )
実行結果。
$ kotlinc -script main.kts
[Home/, Documents/, hello.txt, world.txt, Desktop/, hello.png, Trash/, world.png]
うまくいきました。
fileRecurse 関数で 対象 file が ディレクトリだった場合の処理を 次のように記述しています。
listOf(file) + listFiles(file).map { childFile->
fileRecurse(childFile)
}.flatten()
map と flatten を使って記述していますが、 これは 結局 現在対象となっている file （をリスト List<File> にしたもの）と その file の children の各 file それぞれをリスト List<File> にしたものを 足し合わせているだけです。
なので、 以前のエントリーで実装していたように、fold を使って、次のように 実装することもできます。
val children: List<File> = listFiles(file)
children.fold( listOf(file), {acc, child-> acc + fileRecurse(child)} )
とてもわかり辛いので、型を書き足して冗長に実装すれば次のようになります。
val f: (List<File>, File)->List<File> = { acc, child->
acc + fileRecurse(child)
}
val children: List<File> = listFiles(file)
children.fold( listOf(file), f)
fileRecurse 全体では次のようになります。
fun fileRecurse(file: File): List<File> {
return if( !file.isDir ){
listOf(file)
} else {
val children: List<File> = listFiles(file)
children.fold( listOf(file), {acc, child-> acc + fileRecurse(child)} )
}
}
どちらでも目的は果たせるが map して flatten したほうが少しわかりやすかもしれない。