21

これに関する他の投稿を見たことがありますが、Haskell でこれを行うクリーンな方法はありますか?

第2部として、関数をモナドにせずに行うこともできますか?

4

5 に答える 5

15

hackage の data-memocombinators パッケージは、再利用可能なメモ化ルーチンを多数提供します。基本的な考え方は次のとおりです。

type Memo a = forall r. (a -> r) -> (a -> r)

つまり、a の任意の関数を memoize できます。次に、モジュールはいくつかのプリミティブ (unit :: Memo ()や などintegral :: Memo Int) と、より複雑なメモ テーブルを作成するためのコンビネータ(pair :: Memo a -> Memo b -> Memo (a,b)やなど) を提供しますlist :: Memo a -> Memo [a]。

于 2008-11-21T12:20:03.430 に答える
12

Jonathan のソリューションを unsafePerformIO で変更して、関数の「純粋な」メモ化バージョンを作成できます。

import qualified Data.Map as Map
import Data.IORef
import System.IO.Unsafe

memoize :: Ord a => (a -> b) -> (a -> b)
memoize f = unsafePerformIO $ do 
    r <- newIORef Map.empty
    return $ \ x -> unsafePerformIO $ do 
        m <- readIORef r
        case Map.lookup x m of
            Just y  -> return y
            Nothing -> do 
                    let y = f x
                    writeIORef r (Map.insert x y m)
                    return y

これは再帰関数で動作します:

fib :: Int -> Integer
fib 0 = 1
fib 1 = 1
fib n = fib_memo (n-1) + fib_memo (n-2)

fib_memo :: Int -> Integer
fib_memo = memoize fib

この例は 1 つの整数パラメーターを持つ関数ですが、 memoize の型は、同等の型を取る関数で使用できることを示しています。複数のパラメーターを持つ関数がある場合は、memoize を適用する前にそれらをタプルにグループ化します。Fi:

f :: String -> [Int] -> Float
f ...

f_memo = curry (memoize (uncurry f))
于 2010-11-21T03:27:01.357 に答える
9

これは主にhttp://www.haskell.org/haskellwiki/Memoizationに従います。

タイプ（a-> b）の関数が必要です。自分自身を呼び出さない場合は、戻り値をキャッシュする単純なラッパーを作成するだけです。このマッピングを保存する最良の方法は、利用できるプロパティによって異なります。注文はほとんど最小限です。整数を使用すると、値を保持する無限のレイジーリストまたはツリーを構築できます。

type Cacher a b = (a -> b) -> a -> b

positive_list_cacher :: Cacher Int b
positive_list_cacher f n = (map f [0..]) !! n

また

integer_list_cacher :: Cacher Int b
integer_list_cacher f n = (map f (interleave [0..] [-1, -2, ..]) !!
    index n where
        index n | n < 0  = 2*abs(n) - 1
        index n | n >= 0 = 2 * n

したがって、再帰的であると仮定します。次に、それ自体ではなく、メモ化されたバージョンを呼び出す必要があるため、代わりにそれを渡します。

f_with_memo :: (a -> b) -> a -> b
f_with_memo memoed base = base_answer
f_with_memo memoed arg  = calc (memoed (simpler arg))

もちろん、メモ化されたバージョンは、私たちが定義しようとしているものです。

ただし、入力をキャッシュする関数を作成することから始めることができます。

値をキャッシュする構造を作成する関数を渡すことで、1つのレベルを構築できます。キャッシュされた関数がすでに渡されているバージョンのfを作成する必要がある場合を除きます。

怠惰のおかげで、これは問題ありません：

memoize cacher f = cached where
         cached = cacher (f cached)

次に必要なのはそれを使用することだけです：

exposed_f = memoize cacher_for_f f

この記事では、明示的なキャッシュ関数を選択するのではなく、関数への入力で型クラスを選択して上記を実行する方法についてのヒントを示しています。これは非常に便利です。入力タイプの組み合わせごとにキャッシュを明示的に構築するのではなく、タイプaとbのキャッシュを暗黙的に組み合わせて、aとbを受け取る関数のキャッシュにすることができます。

最後の注意点：この怠惰な手法を使用すると、キャッシュは縮小せず、拡大するだけです。代わりにIOモナドを使用する場合、これを管理できますが、賢明に実行するかどうかは使用パターンによって異なります。

于 2008-10-03T21:48:27.673 に答える
3

より命令的な言語から直接翻訳を行って、これを思いつきました。

memoize :: Ord a => (a -> IO b) -> IO (a -> IO b)
memoize f =
  do r <- newIORef Map.empty
     return $ \x -> do m <- readIORef r
                       case Map.lookup x m of
                            Just y  -> return y
                            Nothing -> do y <- f x
                                          writeIORef r (Map.insert x y m)
                                          return y

しかし、これはどこか物足りない。また、Data.Mapは、パラメーターがOrdのインスタンスになるように制約します。

于 2008-09-26T22:06:16.237 に答える
1

引数が自然数になる場合は、次のように簡単に実行できます。

memo f = let values = map f [0..]
     in \n -> values !! n

ただし、これはスタックのオーバーフローにはあまり役に立ちません。また、再帰呼び出しでは機能しません。http://www.haskell.org/haskellwiki/Memoizationで、より洗練されたソリューションを見ることができます。

于 2008-09-26T22:03:49.143 に答える