原です。

[haskell-jp:227]から始まる豊福さんの質問には共感するところ
が多かったのですが、ちょっと回答が錯綜しているので、現状ま
での所を適当にまとめてみました。批判修正加筆歓迎。

=================================================
Haskell における不動点作用素 Q&A (ドラフト)

-------------------------------------------------

Q1. 解説文「自己言及の論理と計算」

  http://www.kurims.kyoto-u.ac.jp/~hassei/selfref.pdf

に挙げられている、関数上の不動点を求める ML のプログラム:

datatype X = psi_inv of X -> (int -> int);
fun psi (psi_inv (f)) = f;
fun fixpoint(g) =
  let fun h(y) = g(fn x => psi(y)(y)(x))
   in h(psi_inv(h))
  end;

fun F(f)(n) = if n=0 then 1 else n * f(n-1);
val factorial = fixpoint(F);
factorial(10);
(* 10! = 3628800 *)

を Haskell で書くとどうなりますか?

([haskell-jp:216]より)


A1. 以下のようになります。

data X = PsiInv (X -> (Int -> Int))

psi :: X -> (X -> (Int -> Int))
psi (PsiInv f) = f

fixpoint :: ((Int -> Int) -> (Int -> Int)) -> (Int -> Int)
fixpoint g = let h y = g (\x -> psi y y x) in
                 h (PsiInv h)

f :: (Int -> Int) -> (Int -> Int)
f g n = if n==0 then 1
        else n * g(n-1)

factorial :: Int -> Int
factorial = fixpoint f
-- factorial 10 == 3628800

([haskell-jp:227]より)


* この fixpoint のことを Y コンビネータと呼びます。

-------------------------------------------------

Q2. Y コンビネータは、逆極限法とどういう関係にありますか?

A2. 直接の関係があるわけではありません。

-------------------------------------------------

Q3. ML を離れて、Haskell らしく Y コンビネータを書くとどうなり
ますか?

A3. Haskell はもともと遅延評価をすることと、パターンマッチを
用いることにより、次のように書けます。

data X a = T (X a -> a)
fixpoint g = (\x -> g (x (T x))) (\(T x) -> g (x (T x)))

fact = \f n -> if n == 0 then 1 else n * f (n-1)
factorial = fixpoint fact

([haskell-jp:220] のを改変)

なお、次のように fixpoint をそれ自体再帰的に定義することもで
きます。([haskell-jp:217]より)

fixpoint g = g (fixpoint g)

-------------------------------------------------

Q4. Haskell は、ただ y に関する方程式:

  y g = g (y g)

を与えるだけで、

  \g -> (\x -> g (x (T x))) (\(T x) -> g (x (T x)))

という解を得てしまうのですか?

A4. 違います。上の方程式がその解と同値であることを Haskell 
は知りません。例えば

  factorial n = if n==0 then 1 else n * (factorial (n-1))

と書くだけで factorial 10 を計算しますが、だからといって
Haskell は factorial が「階乗に等しい」ことを知っているわ
けではありません。今回の y のような、高階の関数を含む方程
式でも同様で、計算過程は次のようになります。

y g = g (y g)
f h n = if n==0 then 1 else n * h(n-1)

y f 0  =>  f (y f) 0
       =>  if 0==0 then 1 else 0 * (y f (0-1))
       =>  1

y f 1  =>  f (y f) 1
       =>  if 1==0 then 1 else 1 * (y f (1-1))
       =>  1 * (y f (1-1))
       ...
       =>  1 * 1
       =>  1

...

-------------------------------------------------

Q4. Y コンビネータはモナドと関係ありますか?

A4. (?)

=================================================


--
ML: haskell-jp / quickml.com
使い方: http://QuickML.com/