CPLib.Memoize
Defined in cp-library@0.16.0
関数のメモ化(memoize)
基本的な使い方:
import CPLib.Memoize;
// フィボナッチ数列 mod 2^64 を計算するMemoizeモナド
//
// `m`はメモ化につかうメモリの型。`HashMap`や`Array`を呼び出し時に選択。
//
// 結果をメモしたいので、値を計算するモナドを `memoize(n) $ |_|` の後に書く
fib : [m : Memory, Key m = I64, Value m = U64] I64 -> Memoize m U64 = |n| memoize(n) $ |_| (
if n <= 1 { pure $ n.u64 };
pure $ *fib(n - 1) + *fib(n - 2)
);
// フィボナッチ数列の和 mod 2^64 を計算するMemoizeモナド
//
// 内部で呼ばれるfibはメモ化されるべきだが、sum_fibの結果自体はメモしないので、`memoize`しない。
sum_fib : [m : Memory, Key m = I64, Value m = U64] I64 -> Memoize m U64 = |n| (
range(0, n).fold_m(0.u64, |n, sum| pure $ sum + *fib(n))
);
main : IO () = (
// 答えを計算するモナドを作成し、ハッシュマップ上で実行する。
// 引数はキャパシティ(計算中に超えるとrehashが発生)
assert_eq(|_|"", sum_fib(10).run_with_hashmap(10), 88_U64);;
// 配列上で実行する。引数はサイズ(計算中に超えるとout of range)
assert_eq(|_|"", sum_fib(10).run_with_array(10), 88_U64)
);
Values
namespace CPLib.Memoize
memoize
Type: [m : CPLib.Memoize::Memory, CPLib.Memoize::Memory::Key m = k, CPLib.Memoize::Memory::Value m = v] k -> Std::Lazy (CPLib.Memoize::Memoize m v) -> CPLib.Memoize::Memoize m v
モナドアクションをメモ化する
memoize(x) $ |_| body は、
- キーxに対する値がメモリに存在する場合はそれを返す。
- 存在しない場合はモナドbodyを作って実行し、結果をメモリに保存してから返す。
Parameters
x: メモ化のキーf: キーxに対する値を計算するモナドを返す関数
run_with_array
Type: Std::I64 -> CPLib.Memoize::Memoize (Std::Array (Std::Option v)) a -> a
配列上でメモ化モナドを実行する
Parameters
size: 配列のサイズ。計算中に超えた場合はout of rangeでプログラム終了。f: メモ化モナド
run_with_hashmap
Type: Std::I64 -> CPLib.Memoize::Memoize (HashMap::HashMap k v) a -> a
ハッシュマップ上でメモ化モナドを実行する
Parameters
capacity: ハッシュマップの初期容量。計算中に超えた場合はrehashが発生。f: メモ化モナド
run_with_memory
Type: m -> CPLib.Memoize::Memoize m a -> a
メモ化モナドをメモリm上で実行する
Parameters
m: メモ化に使うメモリ領域f: メモ化モナド
namespace CPLib.Memoize::Memory
find
Type: [m : CPLib.Memoize::Memory] CPLib.Memoize::Memory::Key m -> m -> Std::Option (CPLib.Memoize::Memory::Value m)
Trait member of CPLib.Memoize::Memory
insert
Type: [m : CPLib.Memoize::Memory] CPLib.Memoize::Memory::Key m -> CPLib.Memoize::Memory::Value m -> m -> m
Trait member of CPLib.Memoize::Memory
Types and aliases
namespace CPLib.Memoize
Memoize
Defined as: type Memoize m a = unbox struct { ...fields... }
メモ化モナド
mはメモ化に使うメモリの型(HashMapやArrayなど)。
Traits and aliases
namespace CPLib.Memoize
trait m : Memory
type Key
Defined as: Key m
type Value
Defined as: Value m
method insert
Type: CPLib.Memoize::Memory::Key m -> CPLib.Memoize::Memory::Value m -> m -> m
method find
Type: CPLib.Memoize::Memory::Key m -> m -> Std::Option (CPLib.Memoize::Memory::Value m)