8

純粋な関数型プログラミング言語では変更可能なデータは許可されませんが、一部の計算は命令的な方法でより自然に/直感的に表現されます。または、アルゴリズムの命令的なバージョンがより効率的である場合があります。ほとんどの関数型言語は純粋ではないことを認識しており、変数の割り当て/再割り当てや命令的なことを実行できますが、一般的には推奨されません。

私の質問は、ローカル状態をローカル変数で操作できるようにしないで、関数が独自のローカル定数とグローバル定数 (または外部スコープで定義された定数のみ) にのみアクセスできるようにする必要があるのはなぜですか? このように、すべての関数は参照の透過性を維持します (同じ引数を指定すると、常に同じ戻り値を返します) が、関数内では、計算を命令語 (while ループなど) で表現できます。

IO などは、モナドを介して、または「世界」または「宇宙」トークンを渡すことにより、通常の機能的な方法で実現できます。

4

2 に答える 2

3

簡単に言えば、あなたが望むものを許可するシステムがあります。たとえばST、Haskell のモナドを使用してそれを行うことができます (コメントで参照されているように)。

モナドのSTアプローチは Haskell のものControl.Monad.STです。STモナドで書かれたコードはSTRef、便利な場所で参照 ( ) を使用できます。ST良い点は、本質的に自己完結型である ため、モナドの結果を純粋なコードで使用することもできることです(これは基本的に、質問で求めていたものです)。

この自己完結型のプロパティの証明は、型システムを通じて行われます。モナドはST、通常 type-variable で示される state-thread パラメータを運びますs。このような計算を行うと、次のような型のモナド結果が得られます。

foo :: ST s Int

これを実際に純粋な結果にするには、使用する必要があります

runST :: (forall s . ST s a) -> a

この型は次のように読むことができます:s型パラメーターが重要でない計算をしてくださいST。バゲージなしで、計算の結果を返すことができます。これは基本的に、可変変数が型システムによってキャッチされる をST運ぶため、可変変数がエスケープするのを防ぎます。s

これは、基礎となる変更可能な構造 ( vector パッケージなど) で実装されている純粋な構造に対して効果的に使用できます。基になる配列をその場で変更する何かを行うために、限られた時間だけ不変性を捨てることができます。たとえば、イミュータブルVectorを不純なアルゴリズム パッケージと組み合わせて、インプレース ソート アルゴリズムのパフォーマンス特性を最大限に維持しながら、純度を維持することができます。

この場合、次のようになります。

pureSort :: Ord a => Vector a -> Vector a
pureSort vector = runST $ do
  mutableVector <- thaw vector
  sort mutableVector
  freeze mutableVector

および関数は線形時間のコピーですが、これにより全体的な O(n lg n) の実行時間が中断されることはありませんthaw。可変ベクトルが再び使用されないため、別の線形トラバーサルを回避するためにfreeze使用することもできます。unsafeFreeze

于 2012-07-05T11:43:19.370 に答える
3

私の質問は、ローカル状態をローカル変数で操作できるようにしないで、関数が独自のローカル定数とグローバル定数 (または外部スコープで定義された定数のみ) にのみアクセスできるようにする必要があるのはなぜですか?

良い質問。その答えは、変更可能なローカルは実用的な価値が限られているが、ヒープに割り当てられた変更可能なデータ構造 (主に配列) は非常に価値があり、効率的なスタック、キュー、セット、辞書など、多くの重要なコレクションのバックボーンを形成しているということだと思います。したがって、突然変異をローカル言語のみに制限しても、それ以外の場合は純粋に機能的な言語に突然変異の重要な利点は何も与えられません。

関連する注意事項として、純粋に関数型のデータ構造を交換するシーケンシャル プロセスの通信は、両方の世界の多くの利点を提供します。これは、シーケンシャル プロセスが内部でミューテーションを使用できるためです。たとえば、これは F# では慣用的であり、a のコードMailboxProcessorは可変データ構造を使用しますが、それらの間でやり取りされるメッセージは不変です。

並べ替えは、このコンテキストでの良いケース スタディです。C での Sedgewick のクイックソートは短くてシンプルで、どの言語の最速の純粋な関数型ソートよりも何百倍も高速です。その理由は、クイックソートが配列をその場で変更するためです。ミュータブルなローカルは役に立ちません。ほとんどのグラフ アルゴリズムで同じ話です。

于 2012-07-05T08:43:51.267 に答える