> nobsunさん
> > fact = y (\ f n -> if n == 0 then 1 else n * f (n-1))
> 
> >> fun F(f)(n) = if n=0 then 1 else n * f(n-1);
> >> val factorial = fixpoint(F);
> は同じですから違いは
> > y f = f (y f)
> 
> >> fun fixpoint(g) =
> >>   let fun h(y) = g(fn x => psi(y)(y)(x))
> >>    in h(psi_inv(h))
> >>   end;
> のとこですね。
>   前者は両辺に y が出てきますが後者は左辺にしか fixpoint が
> 出てこないので定義としては違うんじゃないでしょうか。

ちょっとまぎらわしいですが、ML の

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

を Haskell で書くと

data Psi a = PSI (Psi a -> a)
psi :: Psi a -> Psi a -> a
psi (PSI f) = f

fixpoint g = let h y = g (\ x -> psi y y x)
	     in h (PSI h)

となります。これは

fixpoint g = (\y -> g (\ x -> psi y y x))
             (PSI (\ y -> g (\ x -> psi y y x)))

と等価です。右辺は関数適用になっているので、少しリダクションを進めると

          β==> g (\ x -> psi (PSI (\ y -> g (\ x -> psi y y x)))
                              (PSI (\ y -> g (\ x -> psi y y x)))
	                      x)
          β==> g (\ x -> (\y -> g (\ x -> psi y y x))
		          (PSI (\ y -> g (\ x -> psi y y x)))
			  x)
	  η==> g (\y -> g (\ x -> psi y y x)
                  (PSI (\y -> g (\ x -> psi y y x)))
          すなわち、 
                g (fixpoint g)

つまり、

y f = f (y f) 

と等価な定義であることが分ります。
実際上の fixpoint をつかって、

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

とすると

Main> fact 10
3628800

となります。

--nobsun 

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