どのように修正を使用しますか、そしてそれはどのように機能しますか？

Question

私はドキュメントに少し混乱していました fix （私はそれが今何をすべきかを理解していると思いますが）、私はソースコードを見ました。それは私をもっと混乱させました：

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

これは固定点をどのように正確に返しますか？

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

Prelude Data.Function> fix id
...

そして、それはそこにぶら下がっています。公平を期すために、これは私の古いMacBookにあります。ただし、この機能はできません それも IDに渡されたものがすべて同じものを元に戻すため、計算上高価です（CPU時間がないことは言うまでもありません）。私は何が間違っているのですか？

Answer 1

あなたは何も悪いことをしていません。 fix id 無限ループです。

私たちがそれを言うとき fix 関数の最小固定点を返すと、 ドメイン理論 検出。そう fix (\x -> 2*x-1) は いいえ 戻るつもりです 1, 、なぜなら 1 その関数の固定点であり、それは 少しでも ドメインの注文に1つ。

単なる段落でドメインの注文を説明することはできませんので、上記のドメイン理論リンクを参照してください。これは優れたチュートリアルで、読みやすく、非常に啓発的です。強くお勧めします。

10,000フィートからの眺めのために、 fix のアイデアをコードする高次関数です 再帰. 。表現がある場合：

let x = 1:x in x

その結果、無限のリストが作成されます [1,1..], 、同じことを使用していると言うことができます fix:

fix (\x -> 1:x)

（または単に fix (1:)）、それは私に固定点を見つけると言っています (1:) 関数、IOW値 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 同等です。

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

Answer 2

私はこれをまったく理解しているとは主張していませんが、これが誰かに役立つなら... Yippee。

の定義を考慮してください fix. fix f = let x = f x in x. 。心を揺さぶる部分はそれです x と定義されている f x. 。しかし、それについて少し考えてください。

x = f x

x = fxなので、の値を代用できます x その右側で、そうですか？だから...

x = f . f $ x -- or x = f (f x)
x = f . f . f $ x -- or x = f (f (f x))
x = f . f . f . f . f . f . f . f . f . f . f $ x -- etc.

したがって、トリックは、終了するために、 f 何らかの種類の構造を生成する必要があります。 f パラメーター（？）の完全な「値」を実際に気にかけずに、パターンがその構造と一致し、再帰を終了できます。

もちろん、Luquiが説明したように、無限のリストを作成するようなことをしたい場合を除きます。

Tommdの要因の説明は良いです。 Fixのタイプの署名はです (a -> a) -> a. 。のタイプの署名 (\recurse d -> if d > 0 then d * (recurse (d-1)) else 1) は (b -> b) -> b -> b, 、 言い換えると、 (b -> b) -> (b -> b). 。だから私たちはそれを言うことができます a = (b -> b). 。そうすれば、修正は私たちの関数を取ります。 a -> a, 、または本当に、 (b -> b) -> (b -> b), 、およびタイプの結果を返します a, 、 言い換えると、 b -> b, 、言い換えれば、別の機能！

待って、私はそれが固定点を返すことになっていると思った...関数ではありません。まあ、それは一種です（関数はデータであるため）。要因を見つけるための決定的な機能を私たちに与えたと想像できます。再発する方法がわからない関数を与えました（したがって、パラメーターの1つは再発するために使用される関数です）、そして fix 反論する方法を教えました。

私がそれを言った方法を覚えておいてください f 後であるように何らかの構造を生成する必要があります f パターンは一致して終了できますか？まあ、それは正確ではないと思います。 Tommdは、拡大する方法を示しました x 関数を適用し、基本ケースに向けてステップを適用します。彼の機能のために、彼はif/thenを使用しました、そしてそれが終了を引き起こすものです。繰り返し交換した後、 in の定義全体の一部 fix 最終的には、その観点から定義されるのを停止します x そして、それはそれが計算可能かつ完全であるときです。

Answer 3

Fixpointが終了する方法が必要です。あなたの例を拡大すると、それが終わらないことは明らかです：

fix id
--> let x = id x in x
--> id x
--> id (id x)
--> id (id (id x))
--> ...

これが修正を使用している私の本当の例です（私は頻繁に修正を使用せず、おそらくこれを書いたときに読みやすいコードについて疲れていなかった /心配していませんでした）：

(fix (\f h -> if (pred h) then f (mutate h) else h)) q

wtf、あなたは言います！まあ、はい、しかしここにはいくつかの本当に有用なポイントがあります。まず第一に、あなたの最初 fix 引数は通常、「繰り返し」ケースである関数である必要があり、2番目の引数は行動するデータです。これは、指定された関数と同じコードです：

getQ h
      | pred h = getQ (mutate h)
      | otherwise = h

あなたがまだ混乱しているなら、おそらく要因がより簡単な例になるでしょう：

fix (\recurse d -> if d > 0 then d * (recurse (d-1)) else 1) 5 -->* 120

評価に注意してください：

fix (\recurse d -> if d > 0 then d * (recurse (d-1)) else 1) 3 -->
let x = (\recurse d -> if d > 0 then d * (recurse (d-1)) else 1) x in x 3 -->
let x = ... in (\recurse d -> if d > 0 then d * (recurse (d-1)) else 1) x 3 -->
let x = ... in (\d -> if d > 0 then d * (x (d-1)) else 1) 3

ああ、あなたはそれを見ましたか？それか x 私たちの内部の関数になりました then ブランチ。

let x = ... in if 3 > 0 then 3 * (x (3 - 1)) else 1) -->
let x = ... in 3 * x 2 -->
let x = ... in 3 * (\recurse d -> if d > 0 then d * (recurse (d-1)) else 1) x 2 -->

上記では、覚えておく必要があります x = f x, 、したがって、の2つの議論 x 2 ただの代わりに最後に 2.

let x = ... in 3 * (\d -> if d > 0 then d * (x (d-1)) else 1) 2 -->

そして、私はここでやめます！

Answer 4

私がそれを理解する方法は、それがあなたがそれを与えるのと同じものを出力するように、それが関数の値を見つけます。キャッチは、常に定義されていない（または、Haskellで、未定義で無限のループが同じである）またはその中で最も未定義のものを持っているものを選択することです。たとえば、IDで

λ <*Main Data.Function>: id undefined
*** Exception: Prelude.undefined

ご覧のとおり、未定義は固定点なので、 fix それを選びます。代わりに（ x-> 1：x）を行う場合。

λ <*Main Data.Function>: undefined
*** Exception: Prelude.undefined
λ <*Main Data.Function>: (\x->1:x) undefined
[1*** Exception: Prelude.undefined

そう fix 未定義を選択できません。 Infinite Loopsにもう少し接続するために。

λ <*Main Data.Function>: let y=y in y
^CInterrupted.
λ <*Main Data.Function>: (\x->1:x) (let y=y in y)
[1^CInterrupted.

繰り返しますが、わずかな違い。では、固定点は何ですか？試してみましょう repeat 1.

λ <*Main Data.Function>: repeat 1
[1,1,1,1,1,1, and so on
λ <*Main Data.Function>: (\x->1:x) $ repeat 1
[1,1,1,1,1,1, and so on

同じです！これが唯一の固定点であるため、 fix それに落ち着かなければなりません。ごめん fix, 、無限のループや未定義はありません。