Scalaz の Tree で違いがあるかを判定する

※Treeのflattenの結果が同じ値ならば常に同じであることを前提としていて、実際そうなのかをちゃんと確認してないので少し怪しいところあり。

ここ1年くらい木構造に悩まされていますが、scalaz の Tree を使っていて、2つの木に違いが存在するかを判定したい場合にどうするかのメモです。

どう考えたか？

scalaz の Tree の flatten を同じ木構造のデータに実施した際に同じ並び順のListになるならば、一旦Listにして同じindexの要素を比較してあげれば、違いがあるかどうかわかるんじゃない？って単純な発想。

Tree の拡張として作りたいので implicit class で定義する。

implicit class MyTreeOps[A](value: Tree[A]) {
    def isSame(other: Tree[A]): Boolean = {
      val list1 = value.flatten.toList
      val list2 = other.flatten.toList
      list1.zipWithIndex.map { case (v, index) =>
        list2.lift(index) match {
          case Some(value) => value == v
          case None => false
        }
      }.forall(b => b)
    }
  }

自分自身をflattenしたものと、比較対象をflattenしたものに対して、同じ位置にある要素を比較して、全てtrueならば一致しているとみなしています。

これをさらに簡潔に書くと

implicit class MyTreeOps[A](value: Tree[A]) {
    def isSame(other: Tree[A]): Boolean = {
      val list1 = value.flatten.toList
      val list2 = other.flatten.toList
      list1.zipWithIndex.map { case (v, index) =>
        list2.lift(index).contains(v) // 上記パターンマッチと同義の処理
      }.forall(b => b)
    }
  }

のようにも書ける。最初の方が意図が伝わりやすい気もするのでどう書くかは好みで。

実際に試してみる。

import scalaz.Scalaz.ToTreeOps
import scalaz.Tree

object Main {
  def main(args: Array[String]): Unit = {
    println(freeTree isSame freeTree) // true
    println(freeTree isSame freeTree2) // false
  }

  implicit class MyTreeOps[A](value: Tree[A]) {
    def isSame(other: Tree[A]): Boolean = {
      val list1 = value.flatten.toList
      val list2 = other.flatten.toList
      list1.zipWithIndex.map { case (v, index) =>
        list2.lift(index).contains(v)
      }.forall(b => b)
    }
  }

  def freeTree: Tree[Char] =
    'P'.node(
      'O'.node(
        'L'.node('N'.leaf, 'T'.leaf),
        'Y'.node('S'.leaf, 'A'.leaf)),
      'L'.node(
        'W'.node('C'.leaf, 'R'.leaf),
        'A'.node('A'.leaf, 'C'.leaf)))

  def freeTree2: Tree[Char] =
    'P'.node(
      'O'.node(
        'L'.node('N'.leaf, 'T'.leaf),
        'Y'.node('S'.leaf, 'A'.leaf)),
      'L'.node(
        'W'.node('C'.leaf, 'R'.leaf),
        'A'.leaf
      )
    )
}