129

なぜ遅延評価が便利なのか、私は長い間疑問に思っていました。理にかなった方法で私に説明してくれる人はまだいません。ほとんどの場合、それは「私を信頼してください」に要約されます。

注: メモ化という意味ではありません。

4

22 に答える 22

101

主な理由は、より効率的になる可能性があるためです。使用しない場合、値を計算する必要はありません。たとえば、関数に 3 つの値を渡すことができますが、条件式の順序によっては、実際にはサブセットのみが使用される場合があります。C のような言語では、とにかく 3 つの値すべてが計算されます。しかし Haskell では、必要な値だけが計算されます。

また、無限リストのようなクールなものも可能です。C のような言語では無限リストを使用できませんが、Haskell では問題ありません。無限リストは数学の特定の分野でかなり頻繁に使用されるため、それらを操作できると便利です。

于 2008-11-05T15:07:46.693 に答える
73

遅延評価の便利な例は、次の使用ですquickSort。

quickSort [] = []
quickSort (x:xs) = quickSort (filter (< x) xs) ++ [x] ++ quickSort (filter (>= x) xs)

リストの最小値を見つけたい場合は、定義できます

minimum ls = head (quickSort ls)

最初にリストをソートしてから、リストの最初の要素を取ります。ただし、遅延評価のため、頭だけが計算されます。たとえば、リストの最小値を取得すると、[2, 1, 3,]quickSort は最初に 2 より小さいすべての要素を除外します。次に、その上でクイックソートを実行します（シングルトンリスト[1]を返します）。これで十分です。遅延評価のため、残りはソートされず、計算時間が大幅に節約されます。

もちろん、これは非常に単純な例ですが、遅延は非常に大きなプログラムでも同じように機能します。

ただし、これには欠点があります。プログラムの実行速度とメモリ使用量を予測するのが難しくなります。これは、怠惰なプログラムが遅くなったり、より多くのメモリを消費したりするという意味ではありませんが、知っておくとよいでしょう。

于 2008-11-12T14:51:15.100 に答える
72

遅延評価は多くのことに役立ちます。

まず、怠惰な言語の副作用について推論するのは非常に難しいため、既存の怠惰な言語はすべて純粋です。

純粋な言語では、等式推論を使用して関数定義について推論できます。

foo x = x + 3

残念ながら、レイジーでない設定では、レイジーな設定よりも多くのステートメントが返されません。そのため、これはMLなどの言語ではあまり役に立ちません。しかし、怠惰な言語では、平等について安全に推論することができます。

第二に、MLの「値制限」のような多くのものはHaskellのような怠惰な言語では必要ありません。これにより、構文が大幅に整理されます。MLのような言語では、varやfunなどのキーワードを使用する必要があります。Haskellでは、これらのことは1つの概念に崩壊します。

第三に、怠惰は、バラバラに理解できる非常に機能的なコードを書くことを可能にします。Haskellでは、次のような関数本体を作成するのが一般的です。

foo x y = if condition1
          then some (complicated set of combinators) (involving bigscaryexpression)
          else if condition2
          then bigscaryexpression
          else Nothing
  where some x y = ...
        bigscaryexpression = ...
        condition1 = ...
        condition2 = ...

これにより、関数の本体を理解しながら、「トップダウン」で作業できます。MLのような言語letでは、厳密に評価されたを使用する必要があります。したがって、let句を関数の本体に「持ち上げる」ことはあえてしないでください。これは、コストがかかる（または副作用がある）場合、常に評価されることを望まないためです。Haskellは、where句の内容が必要な場合にのみ評価されることを知っているため、where句に詳細を明示的に「プッシュオフ」できます。

実際には、ガードを使用して、さらに次のように折りたたむ傾向があります。

foo x y 
  | condition1 = some (complicated set of combinators) (involving bigscaryexpression)
  | condition2 = bigscaryexpression
  | otherwise  = Nothing
  where some x y = ...
        bigscaryexpression = ...
        condition1 = ...
        condition2 = ...

第4に、怠惰は特定のアルゴリズムのよりエレガントな表現を提供することがあります。Haskellの怠惰な「クイックソート」はワンライナーであり、最初のいくつかのアイテムだけを見ると、それらのアイテムだけを選択するコストに比例したコストしか支払わないという利点があります。これを厳密に行うことを妨げるものは何もありませんが、同じ漸近的なパフォーマンスを実現するには、毎回アルゴリズムを再コーディングする必要があります。

第5に、怠惰により、言語で新しい制御構造を定義できます。厳密な言語で構文のように新しい'if.. then ..else..'を書くことはできません。次のような関数を定義しようとすると、次のようになります。

if' True x y = x
if' False x y = y

厳密な言語では、条件値に関係なく、両方のブランチが評価されます。ループを考えるとさらに悪化します。すべての厳密なソリューションでは、ある種の引用符または明示的なラムダ構造を提供する言語が必要です。

最後に、同じように、モナドなどの型システムの副作用に対処するための最良のメカニズムのいくつかは、実際には怠惰な設定でのみ効果的に表現できます。これは、F＃のワークフローの複雑さをHaskellモナドと比較することで確認できます。（厳密な言語でモナドを定義することはできますが、残念ながら、怠惰がなく、ワークフローが厳密な手荷物を大量に受け取るため、モナドの法則に失敗することがよくあります。）

于 2008-11-05T15:47:38.127 に答える
29

通常の順序評価と遅延評価（Haskellのように）には違いがあります。

square x = x * x

次の式を評価しています...

square (square (square 2))

...熱心な評価：

> square (square (2 * 2))
> square (square 4)
> square (4 * 4)
> square 16
> 16 * 16
> 256

...通常の注文評価あり：

> (square (square 2)) * (square (square 2))
> ((square 2) * (square 2)) * (square (square 2))
> ((2 * 2) * (square 2)) * (square (square 2))
> (4 * (square 2)) * (square (square 2))
> (4 * (2 * 2)) * (square (square 2))
> (4 * 4) * (square (square 2))
> 16 * (square (square 2))
> ...
> 256

...遅延評価あり：

> (square (square 2)) * (square (square 2))
> ((square 2) * (square 2)) * ((square 2) * (square 2))
> ((2 * 2) * (2 * 2)) * ((2 * 2) * (2 * 2))
> (4 * 4) * (4 * 4)
> 16 * 16
> 256

これは、遅延評価が構文ツリーを調べてツリー変換を行うためです...

square (square (square 2))

           ||
           \/

           *
          / \
          \ /
    square (square 2)

           ||
           \/

           *
          / \
          \ /
           *
          / \
          \ /
        square 2

           ||
           \/

           *
          / \
          \ /
           *
          / \
          \ /
           *
          / \
          \ /
           2

...一方、通常の順序評価はテキストの拡張のみを行います。

そのため、遅延評価を使用すると、パフォーマンスは（少なくともO表記では）熱心な評価と同等でありながら、より強力になります（評価は他の戦略よりも頻繁に終了します）。

于 2008-11-21T16:21:47.530 に答える
26

サイモンペイトンジョーンズを信じるなら、遅延評価自体は重要ではなく、デザイナーに言語を純粋に保つことを余儀なくさせた「ヘアシャツ」としてのみ重要です。私はこの観点に共感しています。

リチャード・バード、ジョン・ヒューズ、そしてそれほどではないがラルフ・ヒンツェは、遅延評価で驚くべきことをすることができます。彼らの作品を読むことはあなたがそれを理解するのを助けるでしょう。良い出発点は、Birdの壮大な数独ソルバーと関数型プログラミングが重要である理由に関するHughesの論文です。

于 2008-12-10T09:45:33.827 に答える
26

RAM に関連するガベージ コレクションと同様に、CPU に関連する遅延評価。GC を使用すると、無制限の量のメモリを持っているふりをして、必要なだけメモリ内のオブジェクトを要求できます。ランタイムは、使用できないオブジェクトを自動的に再利用します。LE では、無制限の計算リソースを持っているふりをすることができます。必要なだけ計算を行うことができます。ランタイムは、不必要な (特定のケースに対して) 計算を実行しません。

これらの「ふりをする」モデルの実際的な利点は何ですか? これにより、開発者はリソースの管理から (ある程度) 解放され、ソースからいくつかのボイラープレート コードが削除されます。しかし、より重要なのは、ソリューションをより幅広いコンテキストで効率的に再利用できることです。

数値 S と数値 N のリストがあるとします。リスト S から数値 N に最も近い数値 M を見つける必要があります。2 つのコンテキストを持つことができます: 単一の N と N のリスト L (L の各 N に対する ei) S で最も近い M を調べます)。遅延評価を使用する場合は、S を並べ替え、二分探索を適用して、N に最も近い M を見つけることができます。適切な遅延並べ替えを行うには、単一の N と O(ln(size(S))) に対して O(size(S)) ステップが必要になります。 (size(S) + size(L))) 均等に分散された L のステップ。最適な効率を達成するための遅延評価がない場合は、コンテキストごとにアルゴリズムを実装する必要があります。

于 2010-01-29T21:43:33.630 に答える
13

三目並べのプログラムを考えてみましょう。これには次の 4 つの機能があります。

  • 現在のボードを取得し、それぞれに 1 つの移動が適用された新しいボードのリストを生成する移動生成関数。
  • 次に、移動生成機能を適用して、この位置から続く可能性のあるすべてのボード位置を導出する「移動ツリー」機能があります。
  • ツリー (または場合によってはその一部のみ) をたどって最適な次の動きを見つけるミニマックス関数があります。
  • プレイヤーの 1 人が勝ったかどうかを決定するボード評価機能があります。

これにより、懸念事項が明確に分離されます。特に、ゲームのルールを理解する必要があるのは、手番生成関数とボード評価関数だけです。手番ツリーとミニマックス関数は完全に再利用可能です。

それでは、三目並べの代わりにチェスを実装してみましょう。「熱心な」(つまり従来の) 言語では、ムーブ ツリーがメモリに収まらないため、これは機能しません。そのため、生成する移動を決定するためにミニマックス ロジックを使用する必要があるため、ボード評価および移動生成関数を移動ツリーおよびミニマックス ロジックと混合する必要があります。私たちのきれいなモジュラー構造は消えてしまいます。

しかし、怠惰な言語では、ムーブ ツリーの要素は、ミニマックス関数からの要求に応じてのみ生成されます。最上位の要素でミニマックスを解放する前に、ムーブ ツリー全体を生成する必要はありません。したがって、私たちのクリーンなモジュール構造は実際のゲームでも機能します。

于 2008-12-26T16:50:21.010 に答える
12

まだ議論の中で取り上げられていないと私が信じているもう2つのポイントがあります。

  1. 怠惰は、並行環境での同期メカニズムです。これは、いくつかの計算への参照を作成し、その結果を多くのスレッド間で共有するための軽量で簡単な方法です。複数のスレッドが未評価の値にアクセスしようとすると、そのうちの1つだけがそれを実行し、他のスレッドはそれに応じてブロックし、値が使用可能になるとその値を受け取ります。

  2. 怠惰は、純粋な設定でデータ構造を償却するための基本です。これは、岡崎によって純粋関数型データ構造で詳細に説明されていますが、基本的な考え方は、遅延評価は、特定のタイプのデータ構造を効率的に実装できるようにするために重要な、制御された形式の突然変異であるということです。純粋なヘアシャツを着用せざるを得ない怠惰についてよく話しますが、逆の方法も当てはまります。これらは相乗的な言語機能のペアです。

于 2011-10-02T04:19:25.620 に答える
11

コンピュータの電源を入れると、特定のディレクトリまたは特定のプログラムが必要であることをユーザーが示すまで、Windows が Windows エクスプローラでハード ドライブ上のすべてのディレクトリを開くことを控え、コンピュータにインストールされているすべてのプログラムを起動することを控えます。 「怠惰な」評価です。

「遅延」評価は、必要なときに操作を実行することです。遅延評価がプログラミング言語またはライブラリの機能である場合に便利です。これは、すべてを前もって計算するよりも、遅延評価を独自に実装する方が一般に難しいためです。

于 2008-11-05T15:11:56.497 に答える
9

  1. それは効率を高めることができます。これは見た目は明らかですが、実際には最も重要ではありません。（怠惰は効率を損なう可能性があることにも注意してください。この事実はすぐにはわかりません。ただし、一時的な結果をすぐに計算するのではなく、大量に保存することで、大量のRAMを消費する可能性があります。）

  2. 言語にハードコーディングするのではなく、通常のユーザーレベルのコードでフロー制御構造を定義できます。（たとえば、Javaにはforループがあり、Haskellにはfor関数があります。Javaには例外処理があります。Haskellにはさまざまなタイプの例外モナドがあります。C＃にはありgotoます。Haskellには継続モナドがあります...）

  3. これにより、データを生成するためのアルゴリズムを、生成するデータの量を決定するためのアルゴリズムから切り離すことができます。概念的に無限の結果リストを生成する1つの関数と、このリストを必要なだけ処理する別の関数を作成できます。さらに重要なことに、5つのジェネレーター関数と5つのコンシューマー関数を使用でき、両方のアクションを同時に組み合わせる5 x 5 = 25の関数を手動でコーディングする代わりに、任意の組み合わせを効率的に生成できます。（！）デカップリングが良いことであることは誰もが知っています。

  4. 多かれ少なかれ、純粋な関数型言語を設計する必要があります。常にショートカットを取りたくなりますが、怠惰な言語では、わずかな不純物がコードを非常に予測不可能にし、ショートカットをとることに強く反発します。

于 2012-10-02T09:20:24.097 に答える
8

このことを考慮：

if (conditionOne && conditionTwo) {
  doSomething();
}

メソッド doSomething() は、conditionOne が trueでconditionTwo がtrue の場合にのみ実行されます。conditionOne が false の場合、なぜ conditionTwo の結果を計算する必要があるのでしょうか? この場合、特に条件が何らかのメソッド プロセスの結果である場合、 conditionTwo の評価は時間の無駄になります。

これは、遅延評価の関心の一例です...

于 2008-11-05T15:07:33.260 に答える
6

遅延の大きなメリットの 1 つは、不変のデータ構造を適切な償却境界で書き込むことができることです。簡単な例は、不変のスタックです (F# を使用):

type 'a stack =
    | EmptyStack
    | StackNode of 'a * 'a stack

let rec append x y =
    match x with
    | EmptyStack -> y
    | StackNode(hd, tl) -> StackNode(hd, append tl y)

コードは合理的ですが、2 つのスタック x と y を追加するには、最良、最悪、平均の場合で O(x の長さ) の時間がかかります。2 つのスタックの追加はモノリシック操作であり、スタック x 内のすべてのノードに影響します。

データ構造を遅延スタックとして書き直すことができます。

type 'a lazyStack =
    | StackNode of Lazy<'a * 'a lazyStack>
    | EmptyStack

let rec append x y =
    match x with
    | StackNode(item) -> Node(lazy(let hd, tl = item.Force(); hd, append tl y))
    | Empty -> y

lazyコンストラクターでコードの評価を中断することによって機能します。を使用して評価される.Force()と、戻り値はキャッシュされ、後続のすべての で再利用されます.Force()。

遅延バージョンでは、追加は O(1) 操作です。1 つのノードを返し、リストの実際の再構築を一時停止します。このリストの先頭を取得すると、ノードの内容が評価され、強制的に先頭が返され、残りの要素で 1 つのサスペンションが作成されるため、リストの先頭を取得するのは O(1) 操作です。

したがって、私たちの怠惰なリストは常に再構築の状態にあり、すべての要素をトラバースするまで、このリストを再構築するためのコストを支払う必要はありません。遅延を使用して、このリストは O(1) のコンシングと追加をサポートします。興味深いことに、アクセスされるまでノードを評価しないため、潜在的に無限の要素を持つリストを構築することは完全に可能です。

上記のデータ構造では、トラバーサルごとにノードを再計算する必要がないため、.NET の通常の IEnumerables とは明らかに異なります。

于 2009-06-19T19:04:34.507 に答える
5

遅延評価は、データ構造で最も役立ちます。構造内の特定の点のみを帰納的に指定し、配列全体で他のすべての点を表現する配列またはベクトルを定義できます。これにより、非常に簡潔に、高い実行時パフォーマンスでデータ構造を生成できます。

これが実際に動作していることを確認するには、本能と呼ばれる私のニューラルネットワークライブラリを見てください。優雅さと高性能のために遅延評価を多用します。たとえば、私は従来の必須のアクティベーション計算を完全に取り除きます。単純な怠惰な表現は私のためにすべてを行います。

これは、たとえば、活性化関数やバックプロパゲーション学習アルゴリズムで使用されます（2つのリンクしか投稿できないためlearnPat、モジュールで関数をAI.Instinct.Train.Delta自分で検索する必要があります）。従来、どちらもはるかに複雑な反復アルゴリズムを必要とします。

于 2011-10-03T03:49:39.303 に答える
5

This snippet shows the difference between lazy and not lazy evaluation. Of course this fibonacci function could itself be optimized and use lazy evaluation instead of recursion, but that would spoil the example.

Let's suppose we MAY have to use the 20 first numbers for something, with not lazy evaluation all the 20 numbers have to be generated upfront, but, with lazy evaluation they'll be generated as needed only. Thus you will pay only the calculation price when needed.

Sample output

Not lazy generation: 0.023373
Lazy generation: 0.000009
Not lazy output: 0.000921
Lazy output: 0.024205

import time

def now(): return time.time()

def fibonacci(n): #Recursion for fibonacci (not-lazy)
 if n < 2:
  return n
 else:
  return fibonacci(n-1)+fibonacci(n-2)

before1 = now()
notlazy = [fibonacci(x) for x in range(20)]
after1 = now()
before2 = now()
lazy = (fibonacci(x) for x in range(20))
after2 = now()


before3 = now()
for i in notlazy:
  print i
after3 = now()

before4 = now()
for i in lazy:
  print i
after4 = now()

print "Not lazy generation: %f" % (after1-before1)
print "Lazy generation: %f" % (after2-before2)
print "Not lazy output: %f" % (after3-before3)
print "Lazy output: %f" % (after4-before4)
于 2008-11-05T15:38:27.130 に答える
4

他の人はすでに大きな理由をすべて挙げていますが、怠惰がなぜ重要なのかを理解するのに役立つ練習問題は、固定小数点関数を厳密な言語で書いてみることだと思います。

Haskell では、固定小数点関数は非常に簡単です。

fix f = f (fix f)

これは次のように展開されます

f (f (f ....

しかし、Haskell は怠惰なので、その無限の計算チェーンは問題になりません。評価は「外側から内側へ」行われ、すべてがうまく機能します。

fact = fix $ \f n -> if n == 0 then 1 else n * f (n-1)

重要なのは、fix怠惰であることではなく、怠惰であるfことです。すでに strictfを与えられたら、手を空中に放り投げてあきらめるか、それを拡張して物を散らかすことができます。(これは、言語ではなく、厳密/怠惰なライブラリであるというノアの発言によく似ています)。

厳密な Scala で同じ関数を書くことを想像してみてください。

def fix[A](f: A => A): A = f(fix(f))

val fact = fix[Int=>Int] { f => n =>
    if (n == 0) 1
    else n*f(n-1)
}

もちろん、スタック オーバーフローが発生します。機能させたい場合は、必要に応じてf引数を呼び出す必要があります。

def fix[A](f: (=>A) => A): A = f(fix(f))

def fact1(f: =>Int=>Int) = (n: Int) =>
    if (n == 0) 1
    else n*f(n-1)

val fact = fix(fact1)
于 2011-10-03T04:50:41.127 に答える
3

あなたが現在どのように考えているかはわかりませんが、遅延評価を言語機能ではなくライブラリの問題と考えると便利だと思います。

つまり、厳密な言語では、いくつかのデータ構造を構築することで遅延評価を実装でき、遅延言語 (少なくとも Haskell) では、必要なときに厳密性を求めることができます。したがって、言語の選択は、実際にプログラムを遅延または非遅延にするわけではなく、デフォルトで得られるものに影響を与えるだけです。

そのように考えたら、後でデータを生成するために使用できるデータ構造を記述するすべての場所を考えてみてください (その前にあまり見ないでください)。評価。

于 2010-01-29T21:54:03.563 に答える
3

遅延評価は貧弱な人間の等式推論です (理想的には、関連する型と操作のプロパティからコードのプロパティを推測することが期待できます)。

非常にうまく機能する例: sum . take 10 $ [1..10000000000]. 1 つの直接的で単純な数値計算ではなく、合計 10 の数値に減らされてもかまいません。もちろん、遅延評価がなければ、最初の 10 個の要素を使用するためだけに、メモリ内に巨大なリストが作成されます。確かに非常に遅くなり、メモリ不足エラーが発生する可能性があります。

私たちが望むほど素晴らしいものではない例: sum . take 1000000 . drop 500 $ cycle [1..20]. リストではなくループであっても、実際には1 000 000の数字を合計します。それでも、いくつかの条件と数式を使用して、1 つの直接的な数値計算に減らす必要があります。これは、1 000 000 の数字を合計するよりもはるかに優れています。リスト内ではなく、ループ内であっても (つまり、森林伐採の最適化後)。

もう 1 つのことは、末尾再帰 modulo consスタイルでコーディングできるようになり、それが機能することです。

参照。関連する回答。

于 2013-11-10T17:28:09.783 に答える
2

私が使用した遅延評価の最も有用な活用は、特定の順序で一連のサブ関数を呼び出す関数でした。これらのサブ関数のいずれかが失敗した場合（falseが返された場合）、呼び出し元の関数はすぐに戻る必要がありました。だから私はそれをこのようにすることができたでしょう：

bool Function(void) {
  if (!SubFunction1())
    return false;
  if (!SubFunction2())
    return false;
  if (!SubFunction3())
    return false;

(etc)

  return true;
}

または、よりエレガントなソリューション：

bool Function(void) {
  if (!SubFunction1() || !SubFunction2() || !SubFunction3() || (etc) )
    return false;
  return true;
}

使い始めると、ますます頻繁に使う機会があります。

于 2008-11-06T14:22:34.270 に答える
2

遅延評価がなければ、次のようなものを書くことはできません。

  if( obj != null  &&  obj.Value == correctValue )
  {
    // do smth
  }
于 2008-11-29T11:17:32.573 に答える
2

とりわけ、遅延言語は多次元の無限のデータ構造を可能にします。

スキーム、Python などでは、ストリームを使用して 1 次元の無限データ構造を使用できますが、1 次元に沿ってのみトラバースできます。

怠惰は同じフリンジの問題に役立ちますが、そのリンクで言及されているコルーチン接続に注目する価値があります。

于 2008-12-04T22:34:53.500 に答える
1

高階関数より抜粋

3829 で割り切れる 100,000 未満の最大数を見つけてみましょう。これを行うには、解があることがわかっている一連の可能性をフィルタリングします。

largestDivisible :: (Integral a) => a  
largestDivisible = head (filter p [100000,99999..])  
    where p x = x `mod` 3829 == 0

まず、100,000 未満のすべての数値のリストを降順で作成します。次に、述語でフィルタリングします。数値は降順でソートされるため、述語を満たす最大の数値がフィルタリングされたリストの最初の要素になります。開始セットに有限リストを使用する必要さえありませんでした。それはまたしても怠惰です。フィルタリングされたリストの先頭のみを使用することになるため、フィルタリングされたリストが有限であるか無限であるかは問題ではありません。最初の適切な解が見つかると、評価は停止します。

于 2015-07-14T17:48:58.247 に答える
1

「遅延評価」とは、結合ブール値のように意味する場合、

   if (ConditionA && ConditionB) ...

答えは単純に、プログラムが消費する CPU サイクルが少ないほど、実行が速くなるということです...そして、処理命令のチャンクがプログラムの結果に影響を与えない場合、それは不要です (したがって、無駄になります)。とにかくそれらを実行するには...

otoh の場合、次のように、「遅延初期化子」として知られているものを意味します。

class Employee
{
    private int supervisorId;
    private Employee supervisor;

    public Employee(int employeeId)
    {
        // code to call database and fetch employee record, and 
        //  populate all private data fields, EXCEPT supervisor
    }
    public Employee Supervisor
    { 
       get 
          { 
              return supervisor?? (supervisor = new Employee(supervisorId)); 
          } 
    }
}

さて、この手法により、クラスを使用するクライアント コードは、従業員オブジェクトを使用するクライアントがスーパーバイザーのデータへのアクセスを必要とする場合を除いて、スーパーバイザー データ レコードのデータベースを呼び出す必要を回避できます...これにより、従業員をインスタンス化するプロセスが高速になります。それでも、スーパーバイザーが必要な場合は、スーパーバイザー プロパティへの最初の呼び出しでデータベース呼び出しがトリガーされ、データがフェッチされて利用できるようになります...

于 2008-11-05T15:14:07.273 に答える