31

古典的なアルゴリズムの本 (TAOCP、CLR) (およびfxtbookなどのそれほど古典的ではない本) は、命令型アルゴリズムでいっぱいです。これは、組み合わせ生成 (アルゴリズムで配列インデックスと配列値の両方が使用される) や共用体検索アルゴリズムなど、実装が配列に大きく基づいているアルゴリズムで最も明白です。

これらのアルゴリズムの最悪の場合の複雑さの分析は、O(1) である配列アクセスに依存します。Clojure のように、配列を配列っぽい永続構造に置き換えると、配列アクセスは O(1) ではなくなり、それらのアルゴリズムの複雑さの分析は有効ではなくなります。

これは私に次の質問をもたらします: 純粋な関数型プログラミングは古典的なアルゴリズムの文献と互換性がありませんか?

4

4 に答える 4

8

データ構造に関しては、破壊的な更新を使用すると標準的なデータ構造の多くが機能しなくなるため、Chris Okasaki は古典的なデータ構造を純粋に機能的な設定に採用することについてかなりの研究を行いました。彼の著書「Purely Functional Data Structures」では、二項ヒープや赤/黒ツリーなどの一部の構造が機能的な設定でどのようにうまく実装できるかを示していますが、配列やキューなどの他の基本的な構造は、より精巧な概念で実装する必要があります。

コア アルゴリズムのこの分野を追求することに興味がある場合は、彼の本が出発点として最適です。

于 2011-08-02T05:29:57.503 に答える
8

簡単に言えば、アルゴリズムが終了後に観察できる効果 (それが返すもの以外) を持たない限り、それは純粋であるということです。これは、破壊的な配列の更新や突然変異などを行う場合でも当てはまります。

次のようなアルゴリズムがあるとします。

function zero(array):
    ix <- 0
    while(ix < length(array)):
       array[ix] <- 0
       ix <- ix+1
    return array

上記の疑似コードがレキシカル スコープであると仮定すると、配列パラメーターが最初にコピーされ、返される配列がまったく新しいものである限り、このアルゴリズムは純粋な関数を表します (この場合、Haskell 関数fmap (const 0)はおそらく機能します)。本に示されているほとんどの「命令型」アルゴリズムは実際には純粋な関数であり、ST のようなものを使用して純粋に関数的な設定でそれらをそのように記述することはまったく問題ありません。

Mercury または Disciple Disciplined Compiler を調べて、いまだに破壊の中で繁栄している純粋な言語を確認することをお勧めします。

于 2011-08-02T07:28:53.137 に答える
2

この関連する質問に興味があるかもしれません: Efficiency of purely Functional Programming .

最もよく知られている非破壊アルゴリズムが最もよく知られている破壊アルゴリズムよりも漸近的に悪い問題はありますか?

于 2011-08-02T09:11:58.933 に答える
0

そうではない。しかし、命令型言語でしか使えないように見えるアルゴリズムを多くの書籍で見ることができるのは事実です。主な理由は、純粋な関数型プログラミングが長い間学術的な使用に限定されていたことです。次に、これらのアルゴリズムの作成者は、必須の機能が主流になることに強く依存していました。ここで、広く普及している 2 つのアルゴリズム、クイック ソートとマージ ソートについて考えてみましょう。クイックソートは、マージソートよりも「必須」です。その利点の 1 つは、適所にあることです。マージソートは、データをコピーして永続的に保持する必要があるため、(何らかの方法で) クイックソートよりも「純粋」です。実際、多くのアルゴリズムは、あまり効率を失うことなく、純粋な関数型プログラミングで実装できます。これは、たとえば有名なDragon Bookの多くのアルゴリズムに当てはまります。

于 2011-08-02T00:31:33.173 に答える