haskell - 関数型言語での動的プログラミング

Question

ハスケルを勉強しています。中間の計算ステップを保存できないという問題が発生しました。効果がない感じです。関数型プログラミングで動的プログラミングを使用するには?

Answer 1

[Haskell で] 途中の計算ステップを保存できないという問題に遭遇しました。

あなたがそれを学ぶためにどのリソースを使用したかはわかりませんが、それらは明らかに最高ではありませんでした.

例えば：

let 
    intermediate = {- calculation step -}
in ...

計算ステップの結果を に保存しintermediateます。(より良い: 変数を値にバインドしintermediateます。)

さらに、関連するウィキペディアのエントリを引用するには：

数学、コンピューター サイエンス、および経済学では、動的計画法は、複雑な問題をより単純な部分問題に分解することによって解決する方法です。これは、部分問題の重複 [1] および最適な部分構造 (後述) の特性を示す問題に適用できます。該当する場合、メソッドは単純なメソッドよりもはるかに短い時間で済みます。

動的計画法の背後にある重要なアイデアは非常に単純です。一般に、特定の問題を解決するには、問題のさまざまな部分 (サブ問題) を解決し、サブ問題のソリューションを組み合わせて全体的なソリューションに到達する必要があります。多くの場合、これらのサブ問題の多くは実際には同じです。動的計画法のアプローチでは、各部分問題を 1 回だけ解こうとするため、計算回数が削減されます。特定の部分問題の解が計算されると、それは保存または「メモ化」されます。次に同じ解が必要になったときに、単に見上げられます。このアプローチは、繰り返されるサブ問題の数が入力のサイズの関数として指数関数的に増加する場合に特に役立ちます。

このスタイルの問題解決が Haskell によって非常にうまくサポートされていることは明らかです。たとえば、最も簡単なケースでは、すでに解決されたサブ問題とその解決策を保持するマップを持ち歩くことができます。より高度なアプローチでは、State Monad を使用できます。等々。