8

Haskell の他のすべてのメモ化のトリックとテクニックを見てきましたが、私が探しているのは、メモ化を処理するコンパイラ/インタプリタのレベルでの簡単な実装です。

たとえば、フィボナッチ関数の次のコードを考えてみます。

fib 0 = 1
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

デフォルトでメモ化を使用して上記のコードを実行する、ghc (またはその他の Haskell コンパイラ) 用のある種のコンパイラ オプションが必要です。たとえば、「fib 10」を計算するには、「fib 8」と「fib 9」を最初に計算する必要があります。また、「fib 9」の計算は、最初の「fib 8」の計算に依存します。したがって、「fib 10」を計算するときは、コンパイラ/インタープリターにそれを理解し、「fib 8」を一度だけ計算してもらいたいのです。

メモ化を処理する新しいフィボナッチ関数を書きたくないことに注意してください (Haskell の他のすべてのメモ化に関する質問の場合と同様)。私が欲しいのは、上記の機能を維持し、メモ化を行うことです。Haskell コンパイラにその機能があるかどうかはわかりませんが、それは私の質問の一部です。これを提供できる Haskell コンパイラを知っていますか?

ありがとう

4

1 に答える 1

13

コンパイラは通常、「メモ化」オプションを提供しません。これは、プログラマがどこでどのようにメモ化を実行したいかを知るのが難しいためです。メモ化は本質的に、時間とスペースの要件を交換することです。

ここで、少し異なる方法で関数を記述したい場合は、関数の定義と使用されるメモ化手法を切り離す方法があります。

import Data.RunMemo (Memoizable, runMemo, noMemo)
import Data.MemoCombinators as Memo (integral)

fibMemoizable :: Memoizable (Integer -> Integer)
fibMemoizable recurse = go where
  go 0 = 1
  go 1 = 1
  go n = recurse (n - 1) + recurse (n - 2)

fastFib :: Integer -> Integer
fastFib = runMemo Memo.integral fibMemoizable

slowFib :: Integer -> Integer
slowFib = runMemo noMemo fibMemoizable

これは、Luke Palmer のdata-memocombinatorsパッケージと、私自身のおもちゃパッケージrunmemoを使用しています。再帰呼び出しを呼び出すことを除いて、その内容はあなたが書いたものと同じであることに注意してください。recurseこれはコンパイラに焼き付けられる可能性がありますが、Haskell はこれを処理するのに十分な表現力を備えているため、コンパイラが何をしているのかを認識しなくてもよいため、その理由はわかりません。

于 2012-10-25T01:00:00.320 に答える