26

一部の言語（Haskell、Clojure、Schemeなど）の評価は遅延です。遅延評価の「セールスポイント」の1つは、無限のデータ構造です。何がそんなに素晴らしいのですか？無限のデータ構造を処理できることが明らかに有利である場合のいくつかの例は何ですか？

4

6 に答える 6

22

これが2つの例です。1つは大きいもの、もう1つは小さいものです。

JohnHughesによる関数型プログラミングが重要である理由はチェスゲームの良い例です。チェスゲームの移動ツリーは実際には無限ではありませんが、無限になる可能性があるほど十分に大きいです（「ほぼ無限」と呼びます）。厳密な言語では、ツリー全体を格納するための十分なスペースがないため、実際にツリーとして扱うことはできません。しかし、怠惰な言語では、ツリーを定義してから、「nextMove」関数を定義して、必要な限りツリーをトラバースします。遅延評価メカニズムが詳細を処理します。

小さな例は、インデックス番号をリスト内のすべてのアイテムに関連付けるだけです。これにより、["foo"、 "bar"、 "baz"]は[（1、 "foo"）、（2、 "bar"）、（ 3、 "baz"）]。厳密な言語では、最後のインデックスを追跡し、最後にいるかどうかを確認するループが必要です。Haskellではあなたはただこう言います：

zip [1..] items

zipの最初の引数は、無限のリストです。あなたはそれがどれくらい前もって必要であるかを理解する必要はありません。

于 2011-03-12T18:36:21.430 に答える
15

私が考えることができるいくつかの利点：

  • よりクリーンなコード-有界データを操作するコードよりも単純でクリーンな場合が多い場合、無限シーケンスを生成するコードに注意するのは興味深いことです。これは、そのようなコードが基礎となる数学的定義に近いことが多いためです。
  • 柔軟性-データの大きさを事前に決定するのではなく、怠惰な無限構造を使用してデータを作成する場合は、心配する必要はありません。それは「うまくいく」でしょう
  • パフォーマンス-怠惰を正しく使用すると、必要なときにデータ値を計算するだけでパフォーマンスを向上させることができますが、まったく使用しない可能性があります。したがって、大量の不要な計算を回避できる可能性があります。
  • 無限プロセスの抽象化-イベントのストリームの抽象化として、無限のレイジーシーケンスの興味深い使用法があります。たとえば、時間の経過に伴うネットワーク接続からの入力の読み取りなどです。これにより、イベントのストリームを処理するコードを作成するための非常にエレガントで興味深い方法を作成できます。たとえば、Clojureのstream-utilsライブラリを参照してください。
  • より優れたアルゴリズム-無限のデータ構造でより簡単に表現できるアルゴリズムがいくつかあります-アイデアは、ソリューションの必要な部分を怠惰に「引き込み」、残りの無限のアルゴリズムを未評価のままにすることです。このアプローチを使用すると、アルゴリズムの時間計算量を減らすと（たとえば、O(n^2)からO(n log n)）、これは大きなメリットになります。
于 2011-03-12T18:42:19.683 に答える
7

正規の純粋なメモ化戦略があります。

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

fib'関数を無限リストにマップして、のすべての値のテーブルを作成しますfib。出来上がり！安くて簡単なメモ化。

もちろん、これには引数で線形のルックアップ時間があります。これを無限の試行に置き換えて、対数ルックアップ時間を取得できます。cf. data-inttrie。

于 2011-03-12T18:20:21.670 に答える
6

@knivilのスキームについてコメントするつもりでした。代わりに、これを別の答えとして投げます。

レイジーデータ構造は、ほとんどのタスクを実行する唯一の方法ではありません。これはPythonistasを苛立たせるかもしれません。しかし、プログラマーが使用する手法を選択できるようになると、それが最善だと思います。怠惰なテクニックはパワフルでエレガントです。

KnivilはSchemeのを使用して言及しiotaました。怠惰に依存して、完全なメソッド（3つの引数すべてを含む）を作成するのがいかに簡単かを見てください。

iota count begin step = let xs = begin:map (+step) xs
                        in take count xs

-- or, alternately
iota count begin step = take count $ map ((+begin).(*step)) [0..]

length怠惰を悪用して、空でないリストを作成することもできます。

len = fst . last . zip [1..]

-- or even handling empty lists
len = fst . last . zip [0..] . (undefined:)

iterateプレリュードで定義された強力でエレガントな機能を考えてみましょう。

iterate f x = x : iterate f (f x)

無限のリストを作成します[x, f x, f (f x), f (f (f x)), ...]。私は次のように書くことができたでしょiotaうiterate：

iota count begin step = take count $ iterate (+step) begin

怠惰なアプローチは、プログラムするためのエレガントな方法です。それが唯一の方法ではありません。CやJavaに慣れている人は、確かに「怠惰は必要ありません。ただ_できます」と叫びますが、それは正しいことです。あなたの言語がチューリング完全であるならば、それはすることができます。しかし、怠惰はとてもエレガントです。

于 2011-03-12T21:37:53.823 に答える
3

さて、先月は良いユースケースがありました。オブジェクトをコピーするときに一意の名前のジェネレーターが必要でした。つまり、ジェネレータは元の名前を取り、Xコピーの新しい名前を生成します。それは次のようなテキストを追加することによってそれを行います

X - copy
X - copy (2)
X - copy (3)
...

名前が同じグループ内のオブジェクトのセット内で使用されていない限り。単純なループの代わりに「無限データ構造」（文字列の無限配列）を使用することには、1つの利点があります。名前がすでに使用されている場合は、名前生成部分をテストから完全に分離できます。そのため、使用中のテストがオブジェクトタイプごとにわずかに異なる、さまざまなタイプのオブジェクトに対してジェネレーター関数を再利用できます。

于 2011-03-12T18:35:18.430 に答える
2

無限のデータ構造は、（計算可能な）実数のエレガントな表現を提供します。たとえば、次のような無限のリスト

[(0, 4), (1, 3.5), (3.1, 3.2), ...]

を表すことができpiます。怠惰が組み込まれているため、この表現の操作が簡単になります。

于 2012-09-26T04:13:21.843 に答える