haskell - このバージョンの「修正」が Haskell でより効率的なのはなぜですか?

Question

Haskell では、これは不動点の単純な (単純な) 定義です。

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

しかし、Haskellが実際にそれを実装する方法は次のとおりです（より効率的です）

fix f = let x = f x in x

私の質問は、なぜ 2 番目のものは最初のものよりも効率的ですか?

Answer 1

遅いものは再帰の各ステップでfix呼び出しますが、速いものは1 回だけ呼び出します。トレースで視覚化できます。ff

import Debug.Trace

fix  f = f (fix f)
fix' f = let x = f x in x

facf :: (Int -> Int) -> Int -> Int
facf f 0 = 1
facf f n = n * f (n - 1)

tracedFacf x = trace "called" facf x

fac  = fix tracedFacf
fac' = fix' tracedFacf

実行してみます:

> fac 3
called
called
called
called
6
> fac' 3
called
6

より詳細にlet x = f x in xは、遅延サンクが に割り当てられx、このサンクへのポインタが に渡されfます。を最初に評価するfix' fと、サンクが評価され、サンクへのすべての参照 (ここでは具体的には に渡すものf) が結果の値にリダイレクトされます。xへの参照も含む値が与えられたことが起こりxます。

これはかなり気が遠くなる可能性があることを認めます。これは、怠惰な作業をするときに慣れるべきものです。

Answer 2

fix1つの引数を取る関数を生成するために 2 つの引数を取る関数を呼び出している場合、これが常に (または必ず) 役立つとは思いません。確認するには、いくつかのベンチマークを実行する必要があります。ただし、引数を 1 つ取る関数で呼び出すこともできます。

fix (1 :)

循環リンクリストです。の単純な定義を使用するとfix、代わりに無限リストになり、構造が強制されるにつれて新しい部分が遅延して構築されます。