日々の流転

λ. g の逆関数が存在するときに Anamorphic Fusion が成功するか

gに逆関数が存在するなら、ψ' = F(g^-1) ∘ ψ ∘ g とおけば、Fusionできるのは自明。なーんて簡単な話では無いのだとは思うけれど……

λ. レコード型＋不動点演算子で late binding を表現

http://www15.ocn.ne.jp/~rodinia/Blog/MyJournal.html

不動点演算子を作用させた時点でthis.methodが決まってしまうのはその通りですが、不動点演算子を使うのはどうせ具体的な値を定義する段階でなので、一般的なOO言語の late binding を表現するにはそれで十分です。

具体的には、AのコンストラクタをA->Aの形で表現しておく約束にしておいて、それにfixを適用することでAのインスタンスを定義することにすればOK。簡単な例をHaskellで書くと以下のような感じ。Aを継承して一部のメソッドをオーバーライドしたBを定義するのを模倣している。

fix :: (a -> a) -> a
fix f = let x = f x in x
 
data A
    = A
    { op    :: Int -> Int
    , twice :: Int -> Int
    }
 
-- Aのコンストラクタ
ctorA :: A -> A
ctorA this
    = A
    { op    = \x -> x+1
    , twice = \x -> this `op` (this `op` x)
    }
 
-- Aのインスタンス
objA :: A
objA = fix ctorA
 
-- Haskellには残念ながらサブタイピングが無いので (T_T)
type B = A
 
-- Bのコンストラクタ。opをオーバーライド。
ctorB :: B -> B
ctorB this = super{ op = \x -> (super `op` x) * 2 }
    where super = ctorA this
 
-- Bのインスタンス
objB :: B
objB = fix ctorB

試してみると、objB `twice` 10 = 46 = (((10+1)*2)+1)*2 となって、AのopではなくBのopが呼ばれていることが分かる。

なお、この方法だと <m_i : B_i>_i∈I は μX.[m_i:X -> B_i]_i∈I ではなく、[m_i: B_i]_i∈I で表現されるので、サブタイピングに関しても何の問題も無い。