run length圧縮のマッチを試したあと、一文字進めて、もうひとつマッチを試して長くマッチしたほうを採用するというロジックは非決定性モナドではきれいに実装できなさそうだ。
継続モナドを使うのが良さそうな気もするのだけど、ちょっとめんどくさいので、もうすこしラフな感じで、状態を分岐させて、比較して、かたほうを消すみたいなやりかたでやってみようかな。
Discussion
1個または2個の要素を含むデータ構造を作って、run length用の状態をそこに格納するみたいな形でできるんじゃないかな。
状態としては、
1. マッチした位置と長さ、残りの文字列
2. 出力を待つ値、マッチした位置と長さ、残りの文字列
みたいになるかな。で、マッチした段前で1を保存したうえで、2を計算する。マッチした長さを比較して、その結果によって、1か2を利用して計算を進める。
そんな感じかな。
そんなにおおげさにしなくてもいいのかもしれない。
保存する必要があるのは、「マッチした位置と長さ」と「次の一文字」だけでいいのかもしれない。で、
1. 次の一文字を読み込み、それを保存する。次のマッチを試す。次のマッチが前のマッチより短いか、またはマッチしなければ2へ。そうでなければ3へ
2. 一文字読み込みずみなので、前に「マッチした位置と長さ」を出力し、マッチの長さから1減算した文字数だけ読み捨てる。
3. 保存した前に「マッチした位置と長さ」は捨てる。保存した「次の一文字」を出力し新たに「マッチした位置と長さ」を出力し、マッチの長さの文字数だけ読み捨てる。
こんな感じかな。