「フロートアウト」とはどういう意味ですか？ <a href="http://www.haskell.org/haskellwiki/Let_vs._Where#Problems_with_where" rel="noreferrer">Haskell wiki I read that this</a>で

Question

：

fib = 
    let fib' 0 = 0 
     fib' 1 = 1 
     fib' n = fib (n - 1) + fib (n - 2) 
    in (map fib' [0 ..] !!) 

これよりも効率的である。

fib x = 
    let fib' 0 = 0 
     fib' 1 = 1 
     fib' n = fib (n - 1) + fib (n - 2) 
    in map fib' [0 ..] !! x 

「、そのため第二ケースFIB」は、（再）、したがって、それができない、すべての引数xのために定義されています浮かれている。

私はこれが何を意味するのか理解できません。

1. "float out"とは何ですか？どのように最適化ですか？
2. fibの呼び出しごとにfib'が再定義されるのはなぜですか？
3. これはエタ拡張ですか、そうではありませんか？

Answer 1

非常に良い説明ではありません。 ...はXを言及していない場合

\x -> let y = ... in z 

ラムダのをて浮上させることができます：：

let y = ... in \x -> z 

ことを意味している

は、単純であることを意味し、 "アウト浮かんで"一度計算されるのはで、...が高価な場合は時間を大幅に節約できます。しかし、GHCはスペースリークを引き起こす可能性があるため、このような最適化を行うことについては控えめです。 （ただしはとなりますが、ダニエルフィッシャーが答えて指摘しているように、2番目の定義にタイプシグネチャを指定してください）

これは自動最適化に関するものではありません。最初のスニペットはラムダの外側にfib'を定義し、2番目のスニペットは内側に定義します（ラムダは暗黙のうちにfib x = ...になります。これはfib = \x -> ...に相当します）。

でも、実際には関係ありません。最初のスニペットではmap fib' [0 ..]がラムダの外側で発生するため、その結果はラムダのすべてのアプリケーションで共有されます（そのコードでは、 "lambda"は部分アプリケーション(!!)から発生します）。後者では、ラムダの内側にあり、fibのすべてのアプリケーションで再計算される可能性が高いです。

最後の結果は、以前の実装では値がキャッシュされるため、後者よりもはるかに効率的です。最初のスニペットの効率は、fib'が直接再帰的にではなく、代わりにfibになるという事実に依存しているので、メモの恩恵を受ける。

これはeta-expansionに関連しています。後者のスニペットは最初のもののη拡張です。しかし、あなたが引用した声明は、何が起こっているのかを説明するものではありません。

これは実装固有の動作であり、Haskellのセマンティクスの一部ではないことに注意してください。しかし、すべての合理的な実装はこのように動作します。

Answer 2

ehirdの答えは非常によく物事を説明し、しかし一点

があります最終的な結果は、かつての実装が値をキャッシュし、これまでより効率的に後者よりもあるということです。

時々間違っています。あなたは（私は-O2、ない-O1確認、そしてもちろんのみGHC）の最適化と定義のいずれかを含むモジュールをコンパイルする場合

、考慮すべきいくつかのケースがあります：タイプなし

が

1. 最初の定義署名
2. 型シグネチャと第二定義fib :: Int -> Integer
3. 多型タイプを持つ最初の定義fib :: Num a => Int -> a
4. 型署名することなく、第2の定義
5. ケース1内型シグネチャfib :: Num a => Int -> a

と2番目の定義は、単相性制限がタイプfib :: Int -> Integerを生成し、リストmap fib' [0 .. ]はfibのすべての呼び出し間で共有されています。つまり、fib (10^6)を照会すると、メモリに最初の百万（+1）のフィボナッチ数のリストがあり、ガベージコレクターが使用されなくなったと判断できる場合にのみ収集されます。それはしばしばメモリリークです。ケース2では

は、結果は（INGのコア）は、ケース4において

の場合と実質的に同一であり、リストは（もちろんfibの異なるトップレベル呼出し間で共有されず、結果ができ多くのタイプがあるので、共有するリストがたくさんありますが）、トップレベルの呼び出しごとに1回インスタンス化され、fib'からの呼び出しで再利用されるため、fib nを計算すると、O（n）の追加とO（n^2）リスト。それはあまりにも悪くありません。計算が完了するとリストが収集されるため、スペースがリークすることはありません。

ケース3は、4

ケース5と実質的に同じであるが、しかし、素朴な再帰よりも悪いです。明示的に多相でリストはラムダの内側にバインドされているため、リストは再帰呼び出しに再利用できません。それぞれの再帰呼び出しによって新しいリストが作成されます。