38

Data.MemoCombinatorsのソースを調べてきましたが、その中心がどこにあるのか実際にはわかりません。

これらすべてのコンビネータの背後にあるロジックと、実際のプログラミングでプログラムを高速化するために実際にどのように機能するかについて説明してください。

この実装の詳細と、オプションでメモ化に対する他のHaskellアプローチとの比較/対比を探しています。私はメモ化とは何かを理解しており、一般的にどのように機能するかについての説明を探していません。

4

4 に答える 4

59

このライブラリは、よく知られているメモ化手法を簡単に組み合わせたものです。正規の例から始めましょう：

fib = (map fib' [0..] !!)
    where
    fib' 0 = 0
    fib' 1 = 1
    fib' n = fib (n-1) + fib (n-2)

私はあなたが言ったことをあなたがこれがどのようにそしてなぜ働くかを知っていることを意味すると解釈します。それで、私は組み合わせに焦点を合わせます。

私たちは本質的に、のアイデアを捉えて一般化しようとしてい(map f [0..] !!)ます。この関数のタイプはです(Int -> r) -> (Int -> r)。これは理にかなっていInt -> rます。同じ関数のメモ化されたバージョンから関数を受け取り、それを返します。意味的にアイデンティティであり、このタイプの関数はすべて「メモ化」と呼ばれますInt（メモid化しない場合でも）。この抽象化に一般化します。

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

したがって、Memo aのメモ化機能であるaは、から任意aの関数を受け取り、aメモ化された（またはされていない）意味的に同一の関数を返します。

さまざまなメモ化機能のアイデアは、データ構造を使用してドメインを列挙し、それらに関数をマップしてから、データ構造にインデックスを付ける方法を見つけることです。 bool良い例です：

bool :: Memo Bool
bool f = table (f True, f False)
    where
    table (t,f) True = t
    table (t,f) False = f

fromの関数Boolはペアと同等ですが、ペアが各コンポーネントを1回だけ評価する点が異なります（ラムダの外部で発生するすべての値の場合と同様）。したがって、ペアにマップして戻るだけです。table重要な点は、定義域を列挙することにより、引数（ここではの最後の引数）のラムダより上の関数の評価を持ち上げることです。

メモ化も同様の話ですが、ケースのMaybe aメモ化方法を知る必要がある点が異なります。したがって、のメモ化機能は、のメモ化機能を引数として取ります。aJustMaybea

maybe :: Memo a -> Memo (Maybe a)
maybe ma f = table (f Nothing, ma (f . Just))
    where
    table (n,j) Nothing = n
    table (n,j) (Just x) = j x

ライブラリの残りの部分は、このテーマのバリエーションにすぎません。

整数型を記憶する方法は、よりも適切な構造を使用します[0..]。少し複雑ですが、基本的には無限のツリーを作成するだけです（構造を解明するために数値を2進数で表します）。

1
  10
    100
      1000
      1001
    101
      1010
      1011
  11
    110
      1100
      1101
    111
      1110
      1111

そのため、ツリーで数値を検索すると、その表現のビット数に比例した実行時間が発生します。

sclvが指摘しているように、ConalのMemoTrieライブラリは同じ基本的な手法を使用していますが、コンビネータプレゼンテーションの代わりに型クラスプレゼンテーションを使用しています。同時にライブラリを個別にリリースしました（実際、数時間以内に！）。Conalは単純なケースで使用する方が簡単です（関数は1つだけmemoで、タイプに基づいて使用するメモ構造を決定します）が、私のものは次のようなことができるので、より柔軟です。

boundedMemo :: Integer -> Memo Integer
boundedMemo bound f = \z -> if z < bound then memof z else f z
   where
   memof = integral f

これは、プロジェクトオイラーの問題の1つを実装するために必要な、特定の範囲未満の値のみを記憶します。

他のアプローチもあります。たとえば、モナド上でオープンフィックスポイント関数を公開します。

memo :: MonadState ... m => ((Integer -> m r) -> (Integer -> m r)) -> m (Integer -> m r)

これにより、さらに柔軟性が高まります。キャッシュやLRUなどを削除します。ただし、使用するのは面倒であり、メモ化する関数に厳密な制約が課せられます（たとえば、無限の左再帰はありません）。この手法を実装しているライブラリはないと思います。

それはあなたが興味を持っていたことに答えましたか？そうでない場合は、おそらくあなたが混乱している点を明確にしますか？

于 2011-02-12T21:48:58.320 に答える
18

心臓はbits機能です：

-- | Memoize an ordered type with a bits instance.
bits :: (Ord a, Bits a) => Memo a
bits f = IntTrie.apply (fmap f IntTrie.identity)

それはあなたに価値unit :: Memo ()を与えることができる唯一の関数です（些細なことを除いて）。Haskellのメモ化についてはこのページMemo aと同じ考え方を使用しています。セクション2は、リストを使用した最も単純なメモ化戦略を示し、セクション3は、メモ化子で使用されるのと同様の自然の二分木を使用して同じことを行います。IntTree

基本的な考え方は、(map fib [0 ..] !!)またはmemocombinatorsの場合のような構造を使用することです- IntTrie.apply (fmap f IntTrie.identity)。ここで注意すべきことは、との間、およびとの間のIntTie.apply対応!!です。IntTrie.identity[0..]

次のステップは、他のタイプの引数を使用して関数をメモ化することです。これはwrap、型間の同型を使用し、からを構築する関数を使用しaて行わbれます。例えば：Memo bMemo a

Memo.integral f
=>
wrap fromInteger toInteger bits f
=>
bits (f . fromInteger) . toInteger
=>
IntTrie.apply (fmap (f . fromInteger) IntTrie.identity) . toInteger
~> (semantically equivalent)
(map (f . fromInteger) [0..] !!) . toInteger

ソースコードの残りの部分は、List、Maybe、Eitherなどのタイプと、複数の引数のメモ化を扱います。

于 2011-02-12T21:20:14.713 に答える
7

一部の作業はIntTrieによって行われます：http：//hackage.haskell.org/package/data-inttrie-0.0.4

Lukeのライブラリは、ConalのMemoTrieライブラリのバリエーションであり、ここで説明しています：http: //conal.net/blog/posts/elegant-memoization-with-functional-memo-tries/

いくつかのさらなる拡張-機能的メモ化の背後にある一般的な概念は、関数を取得し、のすべての可能な値a -> bによってインデックス付けされ、の値を含むデータ構造全体にマップすることです。このようなデータ構造は、2つの方法で怠惰である必要があります。最初に、保持する値が怠惰である必要があります。第二に、それ自体を怠惰に生成する必要があります。前者はデフォルトで非厳密な言語です。後者は、一般化された試行を使用して実行されます。ab

メモコンビネーター、メモトリーなどのさまざまなアプローチはすべて、ますます複雑になる構造の試行を簡単に構築できるように、個々のタイプのデータ構造に対して試行の断片の構成を作成する方法にすぎません。

于 2011-02-12T19:50:31.100 に答える
0

@luqui私には明らかではないことが1つあります。これは、次と同じ動作動作をしますか。

fib :: [Int]
fib = map fib' [0..]
    where fib' 0 = 0
             fib' 1 = 1
             fib' n = fib!!(n-1) + fib!!(n-2)

上記はトップレベルでfibをメモ化する必要があるため、2つの関数を定義する場合：

f n = fib!!n + fib!!(n+1)

次にf5を計算すると、 fib6を計算するときにfib5が再計算されないことがわかります。メモ化コンビネータが同じ動作をするかどうか（つまり、fib計算の「内部」での再計算を禁止するだけでなくトップレベルのメモ化）があるかどうかはわかりません。

于 2011-02-14T13:05:47.020 に答える