98

のドキュメンテーションに少し戸惑ったのでfix(現在は何をすべきかは理解できたと思いますが)、ソース コードを調べました。それは私をもっと混乱させました：

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

これはどのくらい正確に固定点を返しますか?

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

Prelude Data.Function> fix id
...

そして、それはそこにぶら下がっています。公平を期すために、これは私の古いMacbookにあり、少し遅いです。ただし、この関数は、id に渡されたものはすべて同じ結果を返すため、計算コストが高すぎることはありません(言うまでもなく、CPU 時間を消費しません)。私は何を間違っていますか？

4

4 に答える 4

100

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

fixが関数の最小不動点を返すと言うとき、ドメイン理論的な意味での意味です。はその関数の不動点ですが、ドメインの順序付けで最小のものではないため、Sofix (\x -> 2*x-1)は返されません。11

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

10,000 フィートからのビューの場合、は再帰fixの概念をエンコードする高次関数です。次の式がある場合:

let x = 1:x in x

これは無限リスト[1,1..]になります。次を使用して同じことを言うことができますfix。

fix (\x -> 1:x)

(または単にfix (1:))、これは関数の固定点を見つけて、そのような(1:)値を IOW すると言っています ... 上で定義したのと同じです。定義からわかるように、はこのアイデアにすぎません。関数にカプセル化された再帰です。xx = 1:xfix

これは、再帰の真に一般的な概念でもあります。多相再帰を使用する関数を含め、この方法で再帰関数を記述できます。たとえば、典型的なフィボナッチ関数:

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が同等であることを示します。

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

于 2011-01-24T21:49:19.897 に答える
27

私はこれをまったく理解しているとは主張していませんが、これが誰かの助けになるなら...それから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). そうすれば、 fix はa -> a、または実際には である関数を受け取り、タイプ、つまり 、つまり別の関数(b -> b) -> (b -> b)の結果を返します!ab -> b

待ってください、関数ではなく固定小数点を返すはずだと思っていました。そうですね（関数はデータなので）。階乗を見つけるための決定的な関数が得られたと想像できます。再帰の方法がわからない関数を与え (したがって、そのパラメータの 1 つは再帰に使用される関数です)、fix再帰の方法を教えました。

後でパターンマッチして終了できるfように、ある種の構造を生成する必要があると言ったことを覚えていますか? fまあ、それは正確ではないと思います。TomMD は、拡張xして関数を適用し、基本ケースに進む方法を示しています。彼の関数では、if/then を使用しました。これが終了の原因です。置換を繰り返した後、最終的にinの定義全体の一部は、によって定義されなくなり、計算可能で完全になります。fixx

于 2011-01-25T02:17:33.160 に答える
18

フィックスポイントを終了する方法が必要です。例を拡張すると、それが終わらないことは明らかです:

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

これは私が fix を実際に使用した例です (私は fix をあまり使用せず、おそらく疲れていたので、これを書いたときに読み取り可能なコードについて心配していなかったことに注意してください):

(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ため、 のx 2代わりに2.

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

そしてここでやめます！

于 2011-01-24T22:00:59.083 に答える
3

私が理解しているのは、関数の値を見つけて、指定したものと同じものを出力するということです。問題は、常に undefined (または、haskell では undefined と無限ループは同じである無限ループ) を選択するか、未定義が最も多いものを選択することです。たとえば、id を使用すると、

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

ご覧のとおり、 undefined は固定点なので、それfixを選択します。代わりに (\x->1:x) を実行するとします。

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

したがってfix、未定義を選択することはできません。無限ループにもう少し接続するため。

λ <*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が、無限ループや未定義はありません。

于 2014-03-15T00:39:45.960 に答える