algorithm - 関数型言語で実装するのが難しいアルゴリズムはどれですか？

Question

私は関数型言語に手を出していますが、いくつかのアルゴリズム（特に動的計画法を使用するアルゴリズム）は記述が難しく、最悪の場合の実行時間では効率が低下することがあります。変数が不変で副作用がある関数型言語では効率が低いアルゴリズムのクラスはありますか？

そして、誰かが私に指摘できる参照がありますか？それは、より難しいアルゴリズム（おそらく共有状態によって最適化されたもの）を書くのに役立ちますか？

ありがとう

Answer 1

まず、ご存知かもしれませんが、Haskellを含む一部の言語は共有を実装しており、これにより、考えられる問題の一部が軽減されます。

Andrewの答えはチューリング完全性を指摘していますが、関数型言語で実装するのが難しいアルゴリズムの質問には実際には答えていません。関数型言語で実装するのが難しいアルゴリズムを尋ねる代わりに、人々は通常、関数型言語で実装するのが難しいデータ構造を尋ねます。

これに対する簡単な答え：ポインタを含むもの。

マシンレベルにドリルダウンするときのポインターに相当する機能はなく、マップがあり、特定のデータ構造を配列またはポインターとして実装されたものに安全にコンパイルできますが、高レベルでは、物事を表現することはできません必須言語で可能な限り簡単にポインタベースのデータ構造を使用します。

これを回避するために、いくつかのことが行われました。

• ポインタがハッシュテーブルの基礎を形成し、ハッシュテーブルは実際にはマップを実装するだけなので、効率的な関数マップが包括的に研究されてきました。実際、Chris Okasakiは、関数型マップや両端キューなどを実装するための多くの方法を詳しく説明した本（「純粋関数型データ構造」）を持っています...
• ポインタを使用して、より大きなデータ構造のトラバーサル内のノードを表すことができるため、この領域でも作業が行われています。製品はジッパーであり、「より深い構造の内側のポインター」技術と機能的に同等の機能を簡潔に表す効率的な構造です。
• ポインタを使用して副作用のある計算を実装できるため、モナドを使用してこの種の計算をかなりの方法で表現してきました。状態を追跡するのは難しいため、モナドの1つの用途は、プログラムの醜い命令型の動作部分をマスクし、型システムを使用して、プログラムが正しくチェーンされていることを確認することです（モナドバインドを介して）。

どのアルゴリズムも命令型から機能型に非常に簡単に変換できると言いたいのですが、そうではありません。ただし、問題はアルゴリズム自体ではなく、アルゴリズムが操作するデータ構造であり、状態の必須の概念に基づいていると私はかなり確信しています。この投稿では、機能データ構造の長いリストを見つけることができます。

これらすべての裏側は、より純粋に機能的なスタイルを使い始めると、プログラムの複雑さが大幅に低下し、命令型のデータ構造に対する多くのニーズがなくなることです（たとえば、命令型でのポインターの非常に一般的な使用）言語は厄介なデザインパターンを実装することであり、これは通常、機能レベルでのポリモーフィズムとタイプクラスの巧妙な使用に変換されます。

編集：この質問の本質は、機能的な方法で計算を表現する方法を扱っていると思います。ただし、ステートフル計算を機能的に定義する方法があることに注意してください。むしろ、ステートフル計算について推論するために関数型手法を使用することが可能です。たとえば、Ynotプロジェクトは、ヒープに関するファクト（分離ロジックの形式）がモナドバインドによって追跡されるパラメーター化されたモナドを使用してこれを実行します。

ちなみに、MLでも動的計画法がなぜそんなに難しいのかわかりません。通常、最終的な答えを計算するためにいくつかのシーケンスのコレクションを構築する動的計画問題は、関数への引数を介して構築された値を蓄積する可能性があり、状況によっては継続が必要になる可能性があります。末尾再帰を使用すると、これが命令型言語の場合ほどきれいで効率的でない理由はありません。確かに、これらの値がリストである場合（たとえば）、必然的にそれらを配列として実装できるという議論に遭遇する可能性がありますが、そのためには、適切な投稿の内容を参照してください:-)

Answer 2

Please remember that most functional languages allow some notion of side effects; they may be frowned upon, restricted to local use, etc., but you can still use them. In OCaml, Haskell, F#, Scala or Clojure, you can use mutable arrays if you need to.

So if you find an algorithm for which you have a formulation using mutable arrays, and you need to reproduce it in one of these languages, just use mutable arrays!

There is no reason to force oneself to do everything using a single programming paradigm; there are some problem domains where imperative programming is (given our current knowledge) the best-suited tool for the job, just as there are domains where logic programming is excellent. If it saves you time and effort to make a local, encapsulated use of one of these paradigm, you should not hesitate to use them.

For example, the Sieve of Eratosthenes is trivial to implement with mutable arrays, and significantly harder to imitate (reasonably efficiently) in a purely functional way: see Melissa O'Neill article for details.

On the other hand, finding immutable solutions to a given problem can be an interesting and enlightening exercice. The book "Purely Functional Data Structures" of Crhis Okasaki is a good example of very nice reformulations of algorithms in a purely functional way. If you are interested in the algorithm by themselves (rather than their application to your problem), this can be an very interesting activity.

(For examples of uses of sharing to optimize a purely functional algorithm, see Richard Bird and Ralf Hinze's 2003 Functional Pearl: Trouble Shared is Trouble Halved.)

Answer 3

低漸近コストで命令型機能を実装できるため、抽象的な意味で、命令型コードを純粋関数型ユニバースに変換するのに本質的な困難はありません。もちろん、実際にはあります。:-)Pippengerの「PurevsImpureLisp」とそれを引用している論文を見てください。