data-structures - 短所の利点は何ですか？

Question

多くの関数型プログラミング言語は、データ コンストラクターをサポートし、推奨しています( HaskellやScalaなどの のConsようなリストの場合) 。(1, (2, (3)))

しかし、その利点は何ですか？このようなリストは、ランダムにアクセスすることも、 に追加することもできませんO(1)。

Answer 1

まず、通常呼び出される ML スタイルのリスト データ コンストラクターのニックネームとしての「cons」と、::そのニックネームの由来である元の Lisp スタイルのcons関数を区別してみましょう。

Lisp では、コンス セルは、同種の要素型のリストに限定されない汎用データ構造です。ML スタイルの言語で同等のものは、ネストされたペアまたは 2 タプルであり、空のリストは「ユニット」型で表されることがよくあり()ます。Óscar López が Lisp のユーティリティの概要を説明しconsているので、ここでは省略します。

ほとんどの ML スタイルの言語では、不変コンス リストの利点は、Lisp でのリストの使用とあまり変わらず、動的型付けの柔軟性と、静的型付けの保証および ML スタイルのパターン マッチングの構文とのトレードオフです。

しかし、Haskell では、遅延評価のために状況がかなり異なります。コンストラクターは怠け者であり、コンストラクターのパターン マッチングは評価を強制する数少ない方法の 1 つであるため、厳密に評価される言語とは対照的に、末尾再帰を避ける必要がある場合がよくあります。代わりに、再帰呼び出しをリストの末尾に配置することで、必要な場合にのみ各再帰呼び出しを計算できるようになります。遅延生成されたリストがmapや などの適切な遅延関数で処理される場合foldr、GC がクリーンアップするためにヘッドが放棄されるのと同じレートで末尾が強制され、定数メモリで大きなリストを構築して消費することが可能になります。

Haskell の一般的な見方は、遅延コンス リストはデータ構造ではなく、制御構造 (他のそのようなループと効率的に構成する具体化されたループ) であるということです。

とはいえ、繰り返しランダムアクセスが必要な場合など、コンスリストが適切でない場合が多く、そのような状況ではリストを使用することはお勧めできません。