■

アルゴリズムが、Rewriting ruleの形で与えられています。

a

• • -

c

みたいな感じ。aとかの集合Eがあって、Eの中に書き換えられるものが無くなったら停止、というアルゴリズム。

こういうのどうやって書いたら良いんでしょうか。

ありがちなのは、まだ解けてない集合Eと解いた後の集合E'を渡すようにして、Eで書き換えたものをE'に加えていって、Eが空になったら終了、という感じだと思います。しかし、今回はEの書き換えをEからE'の書き換えに変形するのが自明ではないので、やりたくないのです。

苦し紛れに書いたのはこんな感じのコード。

exception Solved of E.t

let rec solve es =
  let try_solve es e =
    (* eを書き換えられる規則があったら、書き換えた後の集合を返す *)
    (* なかったら、そのまま返す *)
  in
    try
      E.iter (fun e -> let es' = try_solve es e in
                         if not (E.equal es es')
                         then
                           raise (Solved es')) es;
      es
    with
       Solved es -> solve es

E.iterでそれぞれの要素に対して「解けないか試してみて、解けたら例外を投げて解ける式でなかったらそのまま放置」という関数を適用し、例外を拾って再帰的に呼び出す、とうコード。Camlらしく、imperativeに書いてみようかとも思いましたが、やっぱりうまくかけない気がしたのでこっちで。

しかし、こうやって書いてみると、悪くないような気もするようなしないような。(遅そうですが。)(あとでリファクタリングすることにしようと思います。)