Haskellで一般的なメモ機能をどのように作成しますか？

Question

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

2番目の部分として、関数をモナドにせずに行うこともできますか？

Answer 1

これは、主に http://www.haskell.org/haskellwiki/Memoization に続きます。

タイプ（a-＆gt; 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モナドを使用する場合、これを管理できますが、 賢明にそれを行うには、使用パターンに依存します。

Answer 2

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

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

つまりaからの任意の機能をメモできます。モジュールは、いくつかのプリミティブ（ unit :: Memo（）や integral :: Memo Int など）と、より複雑なメモテーブルを構築するためのコンビネータ（ pairなど） ::メモa-＆gt;メモb-＆gt;メモ（a、b）および list ::メモa-＆gt;メモ[a] ）。

Answer 3

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

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を適用する前にそれらをタプルにグループ化します。 F.i。：

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

f_memo = curry (memoize (uncurry f))

Answer 4

より命令的な言語から直接翻訳することで、私はこれを思いつきました。

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 。

Answer 5

引数が自然数になる場合、簡単にできます：

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

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