[解決済み] fixの使い方、効果について教えてください。

質問

のドキュメントを読んでいて、ちょっと混乱しました。 fix のドキュメントを読んで少し混乱したので (今となっては何をするものなのか理解しているつもりですが)、ソースコードを見てみました。 それは私をさらに混乱させたままにしておきました。

fix :: (a -> a) -> a
fix f = let x = f x in x

これは具体的にどのように定点を返すのでしょうか？

コマンドラインで試してみることにしました。

Prelude Data.Function> fix id
...

そして、そこでハングアップします。 公平を期すために、これは私の古いマックブック上で、ちょっと遅いです。 しかし、この関数は も というのは、idに渡されたものはすべて同じものを返してくれるからです（言うまでもなく、CPU時間はまったく消費しません）。 私は何を間違えているのでしょうか？

どのように解決するのですか?

あなたは何も間違っていません。 fix id は無限ループです。

というとき fix が関数の最小固定点を返すとすると、その関数の 領域理論 の意味で使われます。 ですから fix (\x -> 2*x-1) は ではなく を返します。 1 を返さないからです。 1 はその関数の固定点であるが、それは 最小 であり、領域順序の

ドメインオーダーを1、2段落で説明することはできませんので、上記のドメイン理論のリンクを参照してください。 これは素晴らしいチュートリアルで、読みやすく、かなり啓発的です。とてもお勧めです。

10,000フィートからの眺めのために。 fix は高次の関数であり、これは 再帰 . もし、式があれば

let x = 1:x in x

この結果、無限リスト [1,1..] を使っても同じことが言えます。 fix :

fix (\x -> 1:x)

(あるいは、単に fix (1:) の固定点を見つけてくださいということです。 (1:) 関数の固定点、つまり値 x というのは x = 1:x ... ちょうど上で定義したように。 定義からわかるように fix はこのアイデア、つまり関数にカプセル化された再帰にほかなりません。

これは再帰の本当に一般的な概念でもあり、どんな再帰関数もこの方法で書くことができます。 多相再帰を使用する関数も含め . 例えば、典型的なフィボナッチ関数がそうです。

fib n = if n < 2 then n else fib (n-1) + fib (n-2)

を使って書くことができます。 fix のように書くことができます。

fib = fix (\f -> \n -> if n < 2 then n else f (n-1) + f (n-2))

練習問題 fix の2つの定義が同じであることを示すために fib は等価であることを示す。

しかし、完全に理解するためには、領域理論について読んでください。 本当にクールなものです。