fix関数に適用したら無限ループになる理由
前提
不動点コンビネータであるfix関数は、引数に取った関数
f の最小不動点を返す関数
f の不動点とは、 f x == x を満たす x のことであるこの等式を満たす
x は複数存在することもある fix はその内の最小なものを返す以下の疑問に答える
関数
f = (*3) を fix に適用した時に、なぜ 0 じゃなくて無限ループになるのか？ghci(hs)> f = (*3) -- f :: Int -> Int
> fix f -- 無限ループ！「最小」と言うのだから、
0 * 3 == 0 なんだし 0 が返ってくるべきでは？と思ったりする「最小」とは言うが、何の順序の話をしているのかを捉え違えるとこう誤解する
その順序が
Int の数値の大小関係\leの話ならば確かに 0 かもしれないしかし、ここでの順序はそれではない
結論
ここでの順序関係は、意味近似順序のことである
最小不動点は、この順序における最小なものを返す
それが
f = (*3) の場合は、 undefined なので無限ループになる以下のことを抑えておく必要がある
未定義
無限ループ
\mathrm{Int}_\botにおける意味近似順序
例えば、以下の関数を考える
hsf = const "x"これは、引数に何を取っても
"x" を返す関数hsf 1 -- "x"
f True -- "x"
f "x" -- "x"
..この
f の不動点は唯一つであり、それは "x" 従って、最小不動点は
"x" である実際、
fix f の返り値は "x" になるこれは不動点の例として直観に沿う簡単な例
例えば、以下の関数を考える
hsf = (*3)これには複数の不動点が存在する
例えば、
0 ∵
0 * 3 == 0 例えば、
undefined ∵
undefined * 3 == undefined この時、どちらがより小さいか？が問題になる
以下2点を抑える必要がある
どういう集合を考えているのか？
ここで考えている集合は、Haskellの型
Int であるHaskellの型は常に通常の0引数の型にbottom(⊥)を加えた集合になることに注意する
つまり、
Int = {...,-1,0,1,...} ∪ {undefiend} であるどういう順序を考えているのか？
ここで考えている順序は、意味近似順序である
この2点を踏まえると
Int の意味近似順序を表したハッセ図式は以下のようになる
任意の整数nに対して、\mathrm{undefined} \sqsubset nだし、
0 や 1 の間には順序は定義されていないここで、元の
f の不動点は 0 と undefined があったこの時、順序関係は\mathrm{undefined} \sqsubset 0である
故に、最小不動点は
undefined 実際、
fix f の返り値は、無限ループになる結論
不動点が複数あり、その中に\botを含む場合は
fix によって\botが得られるこの\botには、未定義や無限ループが含まれる