haskell - Haskell での動的プログラミング

Question

Haskell は動的プログラミング用のツールを提供していますか? 手続き型言語では、再帰関係に基づいて計算を格納するために配列を使用します。Haskellで同様のことを行うにはどうすればよいですか?

Answer 1

状況に応じて多くの異なる方法。とは言うものの、Haskellは怠惰であるため、多くの場合、単純な動的計画法アルゴリズムは他の言語よりもHaskellの方がはるかに単純です。

フィボナッチ関数（関数型プログラミングの「HelloWorld」）について考えてみましょう。

fib n | n < 2 = 1
fib n | otherwise = fib (n-1) + fib (n-2)

これは指数時間（grr）で実行されます。fibのすべての値を怠惰な無限に長いリストに簡単に格納できます

fibs = map fib [0..]

今、私たちはそれを観察することができます

fibs !! n
 = (map fib [0..]) !! n =
 = fib ([0..] !! n)
 = fib n

これまでのところ、これは役に立ちませんが、この同等性を有利に使用できます

fib n | n < 2 = 1
fib n | otherwise = (fibs !! (n-1)) + (fibs !! (n-2)) where
  fibs = map fib [0..]

これはフィボナッチ関数の線形時間解を提供し（スペースをリークしますが...実際にはこのようにしないでください）、Haskellが怠惰であるためにのみ機能します。それ自体の漸化式の観点から、無限のデータ構造を定義しました。奇跡は、これが有限時間（厳密ではない）で実行されること、線形時間で実行されることは、必要に応じた呼び出し（Haskellのコストモデル）の時間最適性の積であるということです。この線形時間パフォーマンスの理由は、の各エントリがfibs最大で1回（または場合によってはまったく）計算されないためです。