このブログの更新は Twitterアカウント @m_hiyama で通知されます。
Follow @m_hiyama

メールでのご連絡は hiyama{at}chimaira{dot}org まで。

はじめてのメールはスパムと判定されることがあります。最初は、信頼されているドメインから差し障りのない文面を送っていただけると、スパムと判定されにくいと思います。

参照用 記事

植木算の難しさとツリー

「5階まで行くエレベータが各階で止まると何回止まる?」とか、「長さ100メートルの歩道に5メートルおきに植木を植えると木は何本?」(植木算)とか、間違いやすいですね。


for (int i = 1; i <= array.length; i++) {
System.out.println(array[i]);
}
これが例外起こすのも事情は同じです。

勘定するとき0からはじめるか1からはじめるか、不等号にイコールが含まれるか含まれないか、限界値とは許される値か禁止される値か、などはいつだってトラブルのもとです。

さて、自分でファイルコピーコマンドを作るとします。aもbもディレクトリだとして、mycopy a bがどう動作すべきか(仕様)を考えましょう。

次のような案がありえます。

  1. b/a/ を作るだけ。
  2. a/をルートとするツリー構造をb/a/の下に再現。
  3. a/の下のファイル群を b/の下の対応する位置にコピーする。例えば、a/foo.txtをb/foo.txtに。

どれもそれなりに正当化できます。その背後には、ツリーのノードを指したとき暗示される対象の曖昧さ(ゆれ)があります。つまり:

  1. そのノードそのもの
  2. そのノードを(相対)ルートとするサブツリー
  3. そのノードの子孫達が作るツリーリスト(ヘッジ)

仮に「a < b」を「aはbの祖先 = bはaの子孫」のことだとすると、上の解釈に対応する集合(ノードセット)は次のようです。

  1. { x | a = x }
  2. { x | a <= x }
  3. { x | a < x }

やっぱり、等号/不等号が“ゆれ”の原因でした。

これは、ツリーに対するパターンやオペレーションの設計をするとき、考慮すべきことです。