Haskell::OGR-nの探索(その5)

その4のコードを諸々クリーンアップ。

  • 無駄にhead/tailしていた所をパターンマッチで行うように整理
  • 計算済みのOGR-nを持ち回るようにした
  • PGR(n,m)のスキャンオーダを長さ順に整列されるように変更
  • lm、pgr関数をトップレベルに変更

ogr5.hs

今回は残念ながら若干時間計算量/領域計算量共に増加している。

PGR(n,m)の計算過程で明らかに重複して同じGRを計算している部分があるので、memo化により計算量の削減を図られると予想している。スキャンオーダの変更はこれを見越してのこと。

ただ、memo化のための方策は今の所まだいい案を思いついていない。mutableなオブジェクトを導入すれば今のコードスタイルを崩さずに達成できると思うが、安易にはやりたくない(IO monadicな計算のpure functionへの持ち込み方が理解できていないとも言う)。
かと言って、memoオブジェクトを持ち回るのは明らかに面倒くさい(やりかけて面倒なのでやっぱりあきらめた)。さらにmemoオブジェクトの増大化に連れて更新のコストも増大化することは容易に予想がつく。
再帰関数、メモ化でちょっとググってみると、不動点関数、Yコンビネータなんかがすぐヒットするが、まだまだこのあたりは理解できていない(知識としてはわかっても、コードには結びつかんものですね)。

memo化はこの冬の宿題ってところですかね。