61

データ構造に関するテキストは多数あり、データ構造コードのライブラリもあります。純粋に機能的なデータ構造の方が推論しやすいことを理解しています。ただし、命令型のコードよりも、実用的なコードで純粋に関数型のデータ構造を使用することの実際の利点を理解するのは困難です（関数型プログラミング言語を使用するかどうかは関係ありません）。純粋に機能的なデータ構造に利点がある実際の事例を誰かが提供できるでしょうか。その理由は何ですか。

私のような例では、programming_languageでdata_structure_nameを使用してアプリケーションを実行します。これは、 certain_thingを実行できるためです。

ありがとう。

PS：純粋に機能的なデータ構造とは、永続的なデータ構造と同じではありません。永続データ構造は変わらないデータ構造ですか？一方、純粋に機能するデータ構造は、純粋に機能するデータ構造です。

4

5 に答える 5

74

純粋関数型（別名、永続的または不変）のデータ構造には、いくつかの利点があります。

  • それらをロックする必要はありません。これにより、同時実行性が大幅に向上します。
  • 構造を共有できるため、メモリ使用量が削減されます。たとえば、Haskellのリスト[1、2、3、4]や、Javaなどの命令型言語について考えてみます。Haskellで新しいリストを作成するには、新しいリストcons（値と次の要素への参照のペア）を作成し、それを前のリストに接続するだけです。Javaでは、前のリストを損傷しないように、完全に新しいリストを作成する必要があります。
  • 永続データ構造を怠惰にすることができます。
  • また、関数型を使用すると、時間や操作の順序を考える必要がなくなるため、プログラムをより宣言的にすることができます。
  • 実際、データ構造は不変であるため、さらにいくつかの仮定を行うことができるため、言語の機能を拡張できます。たとえば、Clojureは不変性の事実を使用して、各オブジェクトにhashCode（）メソッドの実装を正しく提供するため、任意のオブジェクトをマップのキーとして使用できます。
  • 不変のデータと機能的なスタイルで、メモ化も自由に使用できます。

より多くの利点があります。一般に、これは実世界をモデル化する別の方法です。SICPのこの章と他のいくつかの章では、不変の構造を使用したプログラミング、その長所と短所をより正確に把握できます。

于 2010-12-09T16:11:39.613 に答える
25

共有メモリの安全性に加えて、ほとんどの純粋に機能するデータ構造は、永続性を提供し、実質的に無料です。たとえば、私がsetOCamlにを持っていて、それにいくつかの新しい値を追加したいとしましょう。これを行うことができます。

module CharSet = Set.Make(Char)
let a = List.fold_right CharSet.add ['a';'b';'c';'d'] CharSet.empty in
let b = List.fold_right CharSet.add ['e';'f';'g';'h'] a in
...

a新しい文字を追加した後も変更されないままです（広告のみが含まれます）が、 bahが含まれ、同じメモリの一部を共有します（setAVLツリーであり、の形状であるため、共有されるメモリの量を判断するのは難しいです。ツリーの変更）。ツリーに加えたすべての変更を追跡しながら、これを続行して、前の状態に戻すことができます。

これは、純粋関数型に関するWikipediaの記事からのすばらしい図で、文字「e」をバイナリツリーに挿入した結果を示していますxs。

代替テキスト

于 2010-12-09T16:18:23.487 に答える
14

Erlangプログラムは、純粋に機能的なデータ構造をほぼ独占的に使用し、複数のコアにほぼシームレスにスケーリングすることで、大きなメリットを享受します。共有データ（主にバイナリとビット文字列）は変更されないため、そのようなデータをロックする必要はありません。

于 2010-12-09T15:30:17.713 に答える
10

純粋に機能するデータ構造には、次の利点があります。

  • 永続性：古いバージョンは、変更できないことを知っていれば、安全に再利用できます。

  • 共有：データ構造の多くのバージョンは、適度なメモリ要件で同時に保持できます。

  • スレッドセーフ：ミューテーションはレイジーサンク（存在する場合）内に隠されているため、言語実装によって処理されます。

  • シンプルさ：状態の変化を追跡する必要がないため、特に同時実行のコンテキストで、純粋に機能的なデータ構造を簡単に使用できます。

  • インクリメンタリティー：純粋に機能的なデータ構造は多くの小さな部分で構成されているため、インクリメンタルなガベージコレクションに最適であり、レイテンシーが低くなります。

純粋に機能的なデータ構造の利点として並列処理をリストしていないことに注意してください。これが当てはまるとは思わないからです。効率的なマルチコア並列処理には、キャッシュを活用し、メインメモリへの共有アクセスのボトルネックを回避するために予測可能な局所性が必要です。純粋に機能するデータ構造には、この点に関してせいぜい未知の特性があります。その結果、純粋に機能的なデータ構造を使用する多くのプログラムは、マルチコアで並列化すると、すべての時間をキャッシュミスに費やし、共有メモリパスウェイを争うため、拡張性が高くありません。

純粋に機能的なデータ構造とは、永続的なデータ構造と同じではありません。

ここにはいくつかの混乱があります。純粋に機能的なデータ構造のコンテキストでは、永続性とは、データ構造の以前のバージョンを、それらがまだ有効であるという知識で安全に参照できることを指すために使用される用語です。これは純粋関数型の自然な結果であり、したがって、永続性はすべての純粋関数型データ構造に固有の特性です。

于 2010-12-25T22:45:33.290 に答える
9

F＃のこの小さなスニペットを取ります：

let numbers = [1; 2; 3; 4; 5]

これは1から5までの整数の不変リストであると100％確実に言うことができます。そのリストへの参照を渡すことができ、リストが変更されている可能性があることを心配する必要はありません。それは私がそれを使う十分な理由です。

于 2010-12-09T15:37:29.553 に答える