木構造における属性の伝播の表現 -- CatsのMonoidと再帰処理によって

プログラミングをして暮らしていると、だいたい木構造と向き合うことになる。その頻度はリスト程ではないものの十分に高い。

木構造操作の一類型として、木の根から順に辿っていき、一定の操作を加えていくというものがある。個々の要素だけ見れば良いこともあるが、少なくない頻度で、 親要素から何らかの情報を引き継ぐ、といった振舞いが必要になる ことがある。

今回はこれをコードでうまく表現する方法について考えてみたい。

ライブラリ依存性の定義は以下の通り:

"org.scala-lang.modules" %% "scala-xml" % "1.2.0",
"org.typelevel" %% "cats-core" % "2.8.0"

例1: ディレクトリ構造と絶対パス名
例2: XMLと属性の伝播
感想

例1: ディレクトリ構造と絶対パス名

まずは簡単な例から考えていこう。以下のような再帰的なディレクトリ構造があるとする:

sealed trait Structure
final case class Directory(name: String, children: Seq[Structure]) extends Structure
final case class File(name: String) extends Structure

val fs1 = Directory("", Seq(
  Directory("bin", Seq(File("make"))),
  Directory("etc", Seq(
    File("passwd"),
    Directory("ssh", Seq(
      File("sshd_config"),
      File("ssh_config"),
    ))
  ))
))

これを走査して、以下のようなパス名を得たいとする:

/bin/make
/etc/passwd
/etc/ssh/sshd_config
/etc/ssh/ssh_config

このような処理は、親から情報を引き継ぐ必要はない。StructureからStringへと構造をつぶす過程が発生するので、親側で情報を計算すればよいからだ:

def runStructure(x: Structure): Seq[String] = x match {
  case Directory(name, xs) => xs.map(runStructure).flatMap(names => names.map(n => s"$name/$n"))
  case File(name) => Seq(name)
}

runStructure(fs1)
// res0: Seq[String] = List("/bin/make", "/etc/passwd", "/etc/ssh/sshd_config", "/etc/ssh/ssh_config")

例2: XMLと属性の伝播

二つめの例として、以下のような例を挙げる(というよりこちらが本題で、一つ目の例は導入に過ぎない):

XML構造でなんらかのコンテンツを表現している
各要素は独自のコンテキストを保有している
要素のコンテキストは直接上書きされない限り、子孫要素に伝播する
- 例えば、上位要素でbg=blueと指定されていれば、特に上書きされなければその子孫要素ではbg=blueを指定したものとみなす

例えば、以下のようなXMLを想定する:

import scala.xml._

val xm =
  <dialogue bg="blue">
    <scene bg="red">
      <say>aaa</say>
    </scene>
    <say>bbb</say>
    <say bg="green">ccc</say>
  </dialogue>

ここから全てのsay要素を取り出したい。ただしsay要素は、コンテキストを指定する上位の要素に囲まれているので、コンテキストを保持しつつ再帰的に処理して取り出さなければならない。

そういえばコンテキストの定義を与えていなかった。コンテキストは以下の形で定義されている:

case class BackgroundColor(col: String)
case class Ctx(bg: Option[BackgroundColor] = None) extends Product

あらゆるsay要素は、暗黙のCtxを持っていると考えてほしい。しかし直接Ctxを得ることはできないので、祖先要素の全てのCtxをうまく結合して、最終的なその要素のCtxが確定する。

さて、関数型プログラミングの時間だ。以下の事をCatsを使って表現していく:

BackgroundColor同士はうまく結合できる
- ここでは、後勝ち(子孫側が勝つ)で実装する
Ctx同士はうまく結合できる
- なぜなら、Ctxの構成要素であるOption[BackgroundColor]同士が結合できるから
- なぜなら、Aが結合できるときOption[A]も結合できるから
「うまく結合できる」ことを「MonoidまたはSemigroupのインスタンスを示す」ことで表現する

`BackgroundColor` is a Semigroup

まずは、BackgroundColor同士がうまく結合できることを示そう。BackgroundColorには単位元が無いので、MonoidではなくSemigroupのインスタンスになる。

import cats.implicits._

implicit val monoidForBG = new cats.Semigroup[BackgroundColor] {
  def combine(x: BackgroundColor, y: BackgroundColor): BackgroundColor = BackgroundColor(y.col) // 後勝ち
}

実装しなければならないのは、結合操作を定義するcombineのみだ。素直に実装できた。次はCtxについて同様の実装を行う。

`Ctx` is a Monoid

Ctxにはデフォルト値が存在する。bgがNoneの場合がそれだ。デフォルト値を単位元だとするとCtxはMonoidのインスタンスだということができる。

implicit val monoidForCtx = new cats.Monoid[Ctx] {
  def combine(x: Ctx, y: Ctx): Ctx = Ctx(x.bg |+| y.bg)
  def empty: Ctx = Ctx()
}

combineとemptyを実装できた。combineの実装は単純で、各フィールド同士をcombineした結果を引数にとって構成したCtxだと定義している。ちなみに、AのSemigroupインスタンスがあるとき、CatsはOption[A]のMonoidインスタンスを自動導出してくれる。Noneを単位元にできるからだ。

typelevel.org

`Elem` can produce `Ctx`

簡単のために、XML要素からCtxを取り出すための関数を用意しておこう:

def extractCtx(e: Elem): Ctx = Ctx(bg = e.attribute("bg").headOption.flatMap(_.headOption.map(bgStr => BackgroundColor(bgStr.text))))

実際に要素を与えてみよう:

extractCtx(xm)
// res2: Ctx = Ctx(bg = Some(value = BackgroundColor(col = "blue")))

Ctxが1つしか取り出されなかったけれど、本来は1つのsay要素に対して使うものなのでいったんはこれで良い。

`combine` のテスト

ここで、ちゃんとCtx同士が結合できるか確認しておこう。

以下のような要素を用意する:

val e1 = <say bg="red">aa</say>
val e2 = <say bg="green">bb</say>
val e3 = <say>cc</say>

これを|+|してみる(|+|はcombineのエイリアス):

extractCtx(e1) |+| extractCtx(e2)
// res3: Ctx = Ctx(bg = Some(value = BackgroundColor(col = "green")))
extractCtx(e1) |+| extractCtx(e3)
// res4: Ctx = Ctx(bg = Some(value = BackgroundColor(col = "red")))
extractCtx(e3) |+| extractCtx(e2)
// res5: Ctx = Ctx(bg = Some(value = BackgroundColor(col = "green")))
extractCtx(e3) |+| extractCtx(e3)
// res6: Ctx = Ctx(bg = None)

右側のCtxに入っているBackgroundColorが優越しているし、どちらかがNoneの場合はSomeである方が優越していることがわかる。うまく動作していそうだ。

xml構造を走査する

ここまでで以下の道具が我々の手中にある:

Ctx同士を正しく結合する方法。
ElemからCtxを生成する方法。

この道具を使ってXMLを走査し、全てのsay要素をCtxとともに取り出そう。

やらなければならないことは:

与えられたXMLノードの種類に応じて以下の処理を行う:
- コメントの場合は空リストを返す
- 要素の場合は、全ての子要素について、それぞれ再帰的に現在のCtx |+| 子要素のCtxを計算し、子要素とペアにしたものをリストで返す
- テキストノードの場合は、現在のコンテキストを返す
  - より正確には、現在のCtx |+| emptyを返すのだが、定義上自明にCtxにしかならないので直接Ctxを返す
  - テキストに空白しか含まれない場合は、空リストを返す

これを実装してみよう。

def runXml(x: Node, ctx: Ctx = cats.Monoid[Ctx].empty): Seq[(Node, Ctx)] = x match {
  case Comment(_) => Seq()
  case e: Elem => e.child.flatMap(c => runXml(c, ctx |+| extractCtx(e)))
  case t: Text if t.text.isBlank() => Seq()
  case t: Text => Seq(t -> ctx)
}

大したことはしておらず、非常に素朴。flatMapとemptyとcombineしか使っていない。

実際にパースしてみよう。

val res = runXml(xm)
println(res)
// List((aaa,Ctx(Some(BackgroundColor(red)))), (bbb,Ctx(Some(BackgroundColor(blue)))), (ccc,Ctx(Some(BackgroundColor(green)))))

各要素にCtxがついたペアが返ってきた。

xmもここで再掲しておこう:

val xm =
  <dialogue bg="blue">
    <scene bg="red">
      <say>aaa</say>
    </scene>
    <say>bbb</say>
    <say bg="green">ccc</say>
  </dialogue>

各say要素は3つ存在し、それぞれ異なるコンテキストに置かれている。コンテキストは一部重畳ちょうじょうされており、例えばaaaには2つのコンテキストbg=blueとbg=redが関わっている。しかしrunXmlによって正しくコンテキストが解釈され、最終的にaaaは最も近傍にあるbg=redをコンテキストとして確定させた。

これで、コンテキストを要素から子孫要素に伝播させるという振舞いを実装することができた。