再帰モナドでMatrixを探索する
動機
Paizaのプログラムテストでいつも0点を叩き出してて悔しいから、
「探索問題に使えるベース構造」を作ってやろうと思い立ちました。
（ちなみに、Paizaに確かTSはなかったので、JSに落とし込まないと使えませんｗ）
中身の話
TypeScript で モナド的な再帰処理 を組んでみた感じです。
構造としては、
- RecursiveMonad：時間を進める装置。
受け取った Node を現在値として記憶し、進めなくなったら親に戻る動きを持つ。 - RecursiveMonadStrategy：動き方を定義する層。
Node をどう探索するか、どの方向に動くかをここで制御できる。
今回は MAP 探索を目的としているので、
MatrixExplorerStrategy として実装しました。
ここで “見渡し方” と “動き方” を定義することで、
探索ロジックを自由に差し替えられるようになっています。
最後に、実行部では本体を生成して .next() を呼ぶたびにちょっとずつ進行。
Strategy の作り方次第で、
一気に見渡す探索にも、深さ優先探索（DFS）的な動きにもできるようにしてあります。
余談
これ、作ってる途中で気づいたんですが、
RecursiveMonad が実質「時間を進めるモナド」っぽくなってて
Node は現在の状態、Strategy は振る舞い、
そして Context（拡張版）で記憶を持たせると、
再帰構造そのものが “思考の流れ” を表現するような（大げさか・・）
コード本体
解説
心臓部
ここが再帰モナドの肝になる部分。
初期化時点でセットしたデータを元に、storategyのlookを行ったあと、次のNodeの情報を受け取る
同じ位置かもしれないし、次の位置かもしれない。それはstrategyが決める。
ノード返されたのであれば、そのノードを元に次のRecursiveMonadoのインスタンスを作り返してあげる。
そうすると、呼び元ではnextしか読んでないけど、インスタンスが変わっていき進むという命令だけで、探索が進んでいく仕組み。
Node
このノードは、RowとColumを持つ部分で、探索中のそのマスに関する情報を持つ部分。
なのでマスごとに生成されている感じ。1マスで4方向みるから、どこまでみたかを保持するのもこいつ
Strategy
探索する振る舞いを決める部分。
lookの部分で4方向見たいので、4方向見るまではその場に留まり、行ける場所を見つけると
見つけた場所のNodeを新しく作って返してあげている。
4方向見るためのgeneratorを作るのはこいつなんだけど、状態の保持はNodeの仕事なので
使っているGeneratorは、Nodeの方に格納するようになってる。
何処にもいけない場合は戻らないと行けないので、nullを返してあげると
RecursiveMonadoさんが、自分の生成を行ったNode（親）のほうに戻してくれるようになっている。
SearchContext
探してるときの情報を保持したいなぁと追加したSearchContext
ゆくゆくは、キャッシュとかに対応したりすれば、DFSとかにも利用できるのかな。
実行部分
作ったものを組み合わせれば、探索の出来上がり。
動かしている心臓部は非常に単純で、whileループで終わるまでnextを読んでるだけ
終了条件のみ、ちょっとnodeの位置で決めてしまったので、現在地点の位置がゴールにいるかをチェックしてる
Discussion