割り当てがあった場合：
バイナリ データのブロックを指定して、その中のバイトの頻度をカウントします。
そして、これをCで行うことになっていましたが、答えは簡単で、より大きなバイナリブロックであってもかなり高速です。これを純粋に関数型の言語で副作用なしに実装するにはどうすればよいでしょうか?
たとえば、各バイトと残りのバイト リストの頻度カウントを受け入れ、変更された頻度カウントを返す関数を作成した場合、100M バイトのデータ セットに対して非常に多くの作業を行う必要があります。
また、データを並べ替えてから、後続の同じ値のバイト数を何らかの方法でカウントすると、並べ替え自体に多くの時間がかかります。
これを実装する合理的な方法はありますか？
これを行う簡単な方法は、バイトをカウントにマッピングするデータ構造を渡して返すことです。これはおそらくある種のツリーとして実装されるでしょう (私が知る限り、これは標準ライブラリ コンテナーから得られるものだからです)。純粋な関数型プログラミングでは、ツリーに渡され、ノードが 1 つだけ異なる新しいツリーを返す必要がある場合、返されたツリーはその構造とデータのほとんどすべてを元のツリーと共有することになります。
ツリーをトラバースしてカウントを取得する際にオーバーヘッドが発生しますが、バイトをカウントしているため、ツリーは 256 要素よりも小さいため、オーバーヘッドは定数である log(255) になります。大規模なデータセットの場合、大きくなることはありません。アルゴリズムの複雑さが大きく変わることはありません。これは、256 エントリのカウント配列全体を共有せずにコピーするという最大のオーバーヘッドを使用したとしても、実際には当てはまります。
これを最適化したい場合は、次のカウント セットの計算の一部として以外は、「中間の」頻度カウントがまったく必要ないという事実を利用できます。つまり、機能コードをセマンティックに記述している間でも、さまざまな手法を使用して実装に破壊的な更新を使用させることができます。STrefHaskellのは、基本的にこれを手動で実行できるようにします。
理論的には、コンパイラは、二度と必要のない値を新しい値に置き換えていることに気付く可能性があるため、その場で更新を行うことができます。現在、実際の製品対応コンパイラがこの最適化を行うことができるかどうかはわかりません。