21

HaskellのデフォルトのString実装は、速度とメモリの両方の点で効率的ではないという事実はよく知られています。私の知る限り[] lists、一般的には単一リンクリストとしてHaskellに実装されており、ほとんどの小さい/単純なデータ型（たとえばInt）の場合、それはあまり良い考えではないようですが、String完全にやり過ぎのようです。この問題に関する意見のいくつかは次のとおりです。

実世界のハスケル

このような単純なベンチマークでは、Pythonなどのインタプリタ言語で記述されたプログラムでさえ、Stringを使用するHaskellコードを桁違いに上回る可能性があります。

Haskellでの効率的な文字列の実装

文字列は[Char]、つまりCharのリンクリストであるため、文字列の参照の局所性が低いことを意味します。また、文字列はメモリ内でかなり大きいことを意味します。少なくともN *（21bits + Mbits）ここでNは文字列の長さ、Mはポインタのサイズ（...）です。文字列は、コンパイラによってループなどに最適化される可能性がはるかに低くなります。

Haskellにはいくつかの素晴らしいフレーバーのByteStrings（およびArrays）があり、それらがうまく機能することを知っていますが、デフォルトの実装が最も効率的なものになると思います。

TL; DR：HaskellのデフォルトのString実装は、非常に非効率的で、実際のアプリケーション（本当に単純なアプリケーションを除く）ではめったに使用されないのに、なぜ単一リンクリストなのですか？歴史的な理由はありますか？実装は簡単ですか？

4

3 に答える 3

22

Haskellのデフォルトの文字列実装が単一リンクリストであるのはなぜですか

単一リンクリストは以下をサポートしているため：

  • パターンマッチングによる誘導
  • モナド、ファンクターなどの便利なプロパティがあります
  • 適切にパラメトリックに多形性
  • 自然に怠惰です

そしてString、[Char]（ユニコードポイント）は言語の目標（1990年現在）に適合する文字列型を意味し、基本的にリストライブラリに「無料」で付属しています。

String要約すると、歴史的に言語設計者は、テキスト処理の最新の問題よりも、適切に設計されたコアデータ型に関心を持っていたため、Unicodeテキストチャンクではない、エレガントで、理解しやすく、教えやすい型があります。 、および密集した、パックされた、厳密なデータ型ではありません。

于 2012-12-13T18:20:41.873 に答える
12

効率は、抽象化を測定するための1つの軸にすぎません。リストはtext-y操作にはかなり非効率的ですが、に特化したときに有用な解釈を持つ多態的に実装されたリスト操作がたくさんあるという点で非常に便利です[Char]。そのため、ライブラリの実装とユーザーの頭脳の両方で多くの再利用が可能です。 。

現在のレベルの経験で今日ゼロから言語が設計されていたとしても、同じ決定が下されるかどうかは明らかではありません。ただし、経験が得られる前に完全に決定を下すことが常に可能であるとは限りません。

于 2012-12-13T17:56:17.617 に答える
4

この時点で、それはおそらく歴史的です。ByteString非常に効率的なものを作った最適化は最近のものですが、[Char]それらすべてに何年も前からあります。

于 2012-12-13T17:56:48.337 に答える