string - Haskell の文字列キーを使用した動的プログラミング

Question

純粋な関数型プログラミングのイディオムにはかなり慣れていないため、動的プログラミングのこのケースを実装する方法がわかりません。再帰的に計算される関数f :: String -> [String]があり、メモ化したい。入力Strings は任意である可能性があるため、遅延のようなものが必要だと思いMapますが、何も見つかりませんでした。Haskellでそのようなケースを実装する方法は?

Answer 1

memoizer ライブラリを使用します。

import qualified Data.MemoCombinators as Memo

f :: String -> [String]
f = Memo.list Memo.char memof  -- because String = [Char]
    where
    memof x = ... f ...          -- call *f* recusively (not memof)

詳細については、ドキュメントを参照してください。メモトライも参照