【JavaScript】深さ優先探索をジェネレータで書く

深さ優先探索をジェネレータファンクション function * () で書いてみよう。

深さ優先探索の素朴な例

まず、深さ優先探索が必要になる課題を考える。

【課題】

ネストされたオブジェクトを deep freeze せよ。

Object.freeze はオブジェクトをフリーズしてくれる。 strict モードにおいては、フリーズされたオブジェクトのプロパティを変更しようとするとエラーを投げる。ただし、 Object.freeze の仕様ではオブジェクトの表面の部分だけをフリーズするので、深いプロパティは変更できる。

// 例
'use strict'

const frozen = Object.freeze({
  value: 1,
  nested: {
    value: 2
  }
})

try {
  // 変更しようとするとエラーを投げる
  frozen.value = 100
} catch (e) {
  console.error(e)
}

// ところが、こっちは変更できる
frozen.nested.value = 100

そこで、あるオブジェクトが変更不可能であることを保証するためには、ネストされたオブジェクトについてもフリーズしてくれる関数が必要である。上記のようなオブジェクトの各プロパティも変更できないようにフリーズせよ、というのが課題。そのためには、オブジェクトのキーをたどっていって、各階層のオブジェクトをすべてフリーズしなければならない。そこで、深さ優先探索を使う。

// 深さ優先探索で Object.freeze する
function deepFreeze (obj) {
  for (let key of Object.keys(obj)) {
    if (typeof obj[key] === 'object') {
      deepFreeze(obj)
    }
  }
  return Object.freeze(obj)
}

const frozen = deepFreeze({ /* 略 */ })

try {
  // エラーを投げてくれる
  frozen.nested.value = 100
} catch (e) {
  console.error(e)
}

課題に対する解答としてはこんな感じ。（実際には、この解答には不備がある。たとえば JavaScript において typeof null === 'object' なので、deepFreeze({ value: null }) を実行するとエラーになる。でもまあ、ここではよしとしておく。）

ジェネレータで切り分ける

上記の deepFreeze 関数において、オブジェクト内を深さ優先探索する関数と、各オブジェクトを freeze する関数を切り分けることができる。関数を切り分けると再利用性が増すのでハッピーになれる。そのためにジェネレータを使う。

ジェネレータは、ざっくり言うと for of で列挙できるようにする仕組みである。簡単な例。

function * countTo3Generator () {
  yield 1
  yield 2
  yield 3
}

let countTo3 = countTo3Generator()
for (let i of countTo3) {
  console.log(i)
}

// 実行結果
// 1
// 2
// 3

yield の書かれている箇所でジェネレータ関数がいったん止まり、そこで評価された値を for 文内で使える。 for 内の次のループでジェネレータ関数の続きが実行されて、yield でまた止まる。っと、言葉で説明するとややこしい。気持ちとしては yield は小さな return 文という感じがある。

別の例。

// 配列の偶数番目だけを取り出す
function * evenElementsGenerator (array) {
  for (let i = 0; i < array.length; i += 2) {
    yield array[i]
  }
}

let array = ['even0', 'odd0', 'even1', 'odd1']
let evenElements = evenElementsGenerator(array)
for (let item of evenElements) {
  console.log(item)
}
// 実行結果
// even0
// even1

さて、本題。ジェネレータ関数で上記の deepFreeze を切り分けるとこんな感じになる。

function * deepFirstSearch (obj) {
  for (let key of Object.keys(obj)) {
    let value = obj[key]
    if (typeof value === 'object') {
      yield * deepFirstSearch(obj[key])
    }
  }
  yield obj
}

function deepFreeze (obj) {
  let innerObjs = deepFirstSearch(obj)
  for (let innerObj of innerObjs) {
    Object.freeze(innerObj)
  }
  return obj
}

途中で yield * という構文が出てくるが、これはジェネレータを展開している。

これで深さ優先探索する関数と Object.freeze する関数を切り分けることができた。

満足。