15

GHC ソース コードを見ると、fixの定義は次のようになっていることがわかります。

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

例では、修正は次のように使用されます。

fix (\f x -> let x' = x+1 in x:f x')

これは基本的に、1 ずつ増加して無限大になる一連の数値を生成します。これを行うには、受信した関数を最初のパラメーターとしてその関数にカリー化する必要があります。上記の修正の定義がどのようにそれを行うことができるかは、私には明らかではありません。

この定義は、修正がどのように機能するかを理解するようになった方法です。

fix :: (a -> a) -> a
fix f = f (fix f)

だから今、私は2つの質問があります:

  1. 最初の定義で、xはどのようにして修正 xを意味するようになったのでしょうか?
  2. 2番目の定義よりも最初の定義を使用する利点はありますか?
4

4 に答える 4

16

等式の推論を適用すると、この定義がどのように機能するかを簡単に確認できます。

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

を評価しようとすると、何にx評価されfix fますか? として定義されてf xいるので、fix f = f x. しかし、xここには何がありますか？それf xは、以前と同じです。だからあなたは得るfix f = f x = f (f x)。fこのように推論すると、 : fix f=のアプリケーションの無限チェーンが得られますf (f (f (f ...)))。

今、あなたの代わり(\f x -> let x' = x+1 in x:f x')にf得る

fix (\f x -> let x' = x+1 in x:f x')
    = (\f x -> let x' = x+1 in x:f x') (f ...)
    = (\x -> let x' = x+1 in x:((f ...) x'))
    = (\x -> x:((f ...) x + 1))
    = (\x -> x:((\x -> let x' = x+1 in x:(f ...) x') x + 1))
    = (\x -> x:((\x -> x:(f ...) x + 1) x + 1))
    = (\x -> x:(x + 1):((f ...) x + 1))
    = ...

編集: 2 番目の質問に関して、@is7s はコメントで、最初の定義の方が効率的であるため好ましいと指摘しました。

その理由を知るために、 のコアを見てみましょうfix1 (:1) !! 10^8:

a_r1Ko :: Type.Integer    
a_r1Ko = __integer 1

main_x :: [Type.Integer]   
main_x =
  : @ Type.Integer a_r1Ko main_x

main3 :: Type.Integer
main3 =
  !!_sub @ Type.Integer main_x 100000000

ご覧のとおり、変換後はfix1 (1:)本質的にmain_x = 1 : main_x. この定義自体がどのように参照されているかに注意してください。これが「結び目を結ぶ」という意味です。この自己参照は、実行時に単純なポインターの間接参照として表されます。

修正1

fix2 (1:) !! 100000000では、次を見てみましょう。

main6 :: Type.Integer
main6 = __integer 1

main5
  :: [Type.Integer] -> [Type.Integer]
main5 = : @ Type.Integer main6

main4 :: [Type.Integer]
main4 = fix2 @ [Type.Integer] main5

main3 :: Type.Integer
main3 =
  !!_sub @ Type.Integer main4 100000000

ここでは、fix2アプリケーションが実際に保存されています。

修正2

その結果、2 番目のプログラムはリストの各要素の割り当てを行う必要があります (ただし、リストはすぐに消費されるため、プログラムは依然として定数空間で効果的に実行されます)。

$ ./Test2 +RTS -s
   2,400,047,200 bytes allocated in the heap
         133,012 bytes copied during GC
          27,040 bytes maximum residency (1 sample(s))
          17,688 bytes maximum slop
               1 MB total memory in use (0 MB lost due to fragmentation)
 [...]

それを最初のプログラムの動作と比較してください。

$ ./Test1 +RTS -s          
          47,168 bytes allocated in the heap
           1,756 bytes copied during GC
          42,632 bytes maximum residency (1 sample(s))
          18,808 bytes maximum slop
               1 MB total memory in use (0 MB lost due to fragmentation)
[...]
于 2012-10-21T16:01:59.990 に答える
9

最初の定義で、x はどのようにして修正 x を意味するようになったのでしょうか?

fix f = let x = f x in x

Haskell のバインディングを再帰的にする

まず第一に、Haskell では再帰的な let バインディングが可能であることを理解してください。Haskell が「let」と呼ぶものは、他のいくつかの言語では「letrec」と呼ばれます。これは、関数定義ではごく普通のことです。例えば：

ghci> let fac n = if n == 0 then 1 else n * fac (n - 1) in fac 5
120

しかし、値の定義についてはかなり奇妙に思えるかもしれません。それにもかかわらず、Haskell の非厳密性により、値は再帰的に定義できます。

ghci> take 5 (let ones = 1 : ones in ones)
[1,1,1,1,1]

Haskell の遅延について詳しくは、Haskell のセクション 3.3 と 3.4 の簡単な紹介を参照してください。

GHCのサンク

GHC では、まだ評価されていない式は「サンク」でラップされます。つまり、計算を実行するという約束です。サンクは、絶対に評価しなければならない場合にのみ評価されます。したいとしfix someFunctionます。の定義によればfix、それは

let x = someFunction x in x

今、GHC が見ているのはこのようなものです。

let x = MAKE A THUNK in x

したがって、それは喜んであなたのためにサンクを作り、あなたがx実際に何であるかを知りたいと要求するまですぐに進みます.

サンプル評価

あのサンクの表情はたまたま自分自身を指している。ones例を取り上げて、を使用するように書き直してみましょうfix。

ghci> take 5 (let ones recur = 1 : recur in fix ones)
[1,1,1,1,1]

では、そのサンクはどのように見えるでしょうか？より明確なデモンストレーションのために、無名関数として
インライン化できます。ones\recur -> 1 : recur

take 5 (fix (\recur -> 1 : recur))

-- expand definition of fix
take 5 (let x = (\recur -> 1 : recur) x in x)

では、 とは x？何が何であるかはよくわかりませんxが、関数の適用を行うことができます。

take 5 (let x = 1 : x in x)

ほら、以前の定義に戻りました。

take 5 (let ones = 1 : ones in ones)

したがって、それがどのように機能するかを理解していると信じている場合は、どのように機能するかについて良い感触を持っていますfix.

2番目の定義よりも最初の定義を使用する利点はありますか?

はい。問題は、最適化を行っても、2 番目のバージョンでスペース リークが発生する可能性があることです。の定義に関する同様の問題については、GHC トラック チケット #5205を参照してくださいforever。これが、私がサンクについて言及した理由ですlet x = f x in x: サンクを 1 つだけ割り当てるためxです。

于 2012-10-22T04:36:33.687 に答える
5

インライン最適化に由来する説明を少し単純化したかもしれません。私たちが持っている場合

fix :: (a -> a) -> a
fix f = f (fix f)

thenfixは再帰関数であり、使用されている場所でインライン化できないことを意味します (INLINEプラグマが指定された場合、無視されます)。

でも

fix' f = let x = f x in x

再帰関数ではありません- それ自体を呼び出すことはありません。内部だけxが再帰的です。だから電話するときは

fix' (\r x -> let x' = x+1 in x:r x')

コンパイラはそれをインライン化できます

(\f -> (let y = f y in y)) (\r x -> let x' = x+1 in x:r x')

次に、それを単純化し続けます。たとえば、

let y = (\r x -> let x' = x+1 in x:r x') y in y 
let y = (\  x -> let x' = x+1 in x:y x')   in y

これは、関数が標準の再帰表記を使用して定義されているかのようですfix。

    y       x =  let x' = x+1 in x:y x'
于 2012-10-28T06:32:39.990 に答える