さかいです。

From: "TOYOFUKU Chikanobu" <nobu_toyofuku / nifty.com>
Subject: [haskell-jp:225] Re: 不動点としての再帰プログラム
Date: Sun, 26 Oct 2003 01:49:41 +0900

>   豊福です。

> nobsanさん
> > ML では、y f = f (y f) のような定義はできないので、
> > 巧妙に同等の定義が可能なような工夫がされています。
> > それが逆にわかりにくい原因だと思います。
> 
>   ML は遅延評価でないので y f = f (y f) ではまずいわけですね。
> 
>   定義として同じとみなすかどうかは置いといて
> 
> 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;
> 
> と同じやり方を haskell でできるならやりたいのですができるで
> しょうか。

もちろん出来ます。

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

--
酒井 政裕 / Masahiro Sakai

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