SML版 factの最小不動点を調べる

圏論勉強会#9 Haskellによるfactの最小不動点の説明 のSML版です。

講義中では「Haskellの遅延評価が〜」と何度も繰り返されてましたが、fixを使う前の undefined を使う定義ではSMLでも(この場合は)同様の結果が得られます。
ただし引数を合わせる必要があります。(単に例外を投げるだけのコードは関数型には推論されない)

structure Fact =
struct
  infixr 1 $
  fun f $ a = f a

  exception Fact of int

  fun factF f = fn n => if n=0 then 1 else n * f(n-1);
  val bottom = fn _=> raise Fact (* ⊥ *)
  val fact0 = bottom
  val fact1 = factF $ bottom
  val fact2 = factF o factF $ bottom
  val fact3 = factF o factF o factF $ bottom
  val fact4 = factF o factF o factF o factF $ bottom
  val fact5 = factF o factF o factF o factF o factF $ bottom
end

- fact0 0;
uncaught exception Fact
- fact1 0;
val it = 1 : int
- fact1 1;
uncaught exception Fact
- fact2 1;
val it = 1 : int
- fact2 2;
uncaught exception Fact

factFの適用回数が増えていくと⊥を返さないドメイン(領域?)が広くなっていきます。

SMLで fix の実装は素直には出来ないので今回はパスで…。
コード全体は Gist にあります。