Apr 19 2014

夢日記。

なんかの体育祭に参加していた。自分が25組で、固まって座っていたけどみんなどこかにあそびに行ってしまった。 残ったのは自分を含めて四人で、内一人が自分に馴れ馴れしく近寄ってきたので慌てて行き先もなく逃げた。

外で偶然知り合いと出会う確率は知り合いの人数に比例すると言えなくもないけれど、 場所だとか時間だとかいう条件が与えられたら、確率は零か壱かであるような気もする。

へんなゼリーが、試供品が、町のあちらこちらで配られていた。 たくさん人間がいる中で自分だけが無視されていたようだった。 だからたくさん自分から人に話しかけることにした。そうすれば一応はみんな、自分の相手をしてくれた。

余再帰、の意味はわからないけれど、それを用いた キューっぽい何かデータ構造の再現を利用した、 幅優先探索。

ノード a の行き先、c a = @ [c1 .. cn] が自然に考えられるデータ構造について、 (木とか) 根ノード a0 から初めて、幅優先探索で辿った順をリストとして返すことにすれば目的は果たされた。

bfs a0 = a0 : something

walk (a : rest) = c a ++ walk rest

that is

walk q = c (head q) ++ walk (tail q)

初めから、完全なa : rest が与えられてれば、 walk とは所詮 map に近い何かだけど、

queue = a : walk queue

このようにリストの再帰的定義を用いると、違うことになる。

walk q = c (head q) ++ walk (tail q)

の下で(ちょっと書きなおした)、

q = a : walk q
  = a : c (head q) ++ walk (tail q)

  where
  walk (tail q) = c $ head (tail q)
                = c $ c $ head q
                = c (c a)

q = a ++ c a ++ c (c a) ++ c (c (c a)) ++ ..

になるはず。 (++)が(:)なら、ただのscanだ。

qの先頭から、適当な処理をしてやって、適当なとこで打ち切れば、 幅優先探索は完遂される。