memoise-0.2

この前作ったメモ化ライブラリ をいろいろ改良しました。

これまではTokenStreamのparseがめんどかったのでサードライブラリのマッピングライブラリを使っていたんですが、 制約が大きくていい感じの構文が作れなかったので自前でparseするようにしました。 自分では直感的で直交した文法になったんではないかなあと思います。

下限を指定できるように＆構文の全体的な改善

キーの取りうる値の上限と下限を直感的に書けるようにする、かつほしい機能を過不足なく満たすように いろいろ試行錯誤した結果こんな感じになりました。

// 上限だけ指定
#[memoise(n <= 100)]
fn fib(n: i64) -> i64 {
    if n == 0 || n == 1 {
        return n;
    }
    fib(n - 1) + fib(n - 2)
}

// 上限と下限を指定
#[memoise(-100 <= n <= 100)]
fn foo(n: i64) -> i64 {
    if n == -100 {
        n
    } else {
        foo(n - 1)
    }
}

// 開区間も指定できる
#[memoise(-100 < n < 100)]
fn bar(n: i64) -> i64 {
    if n == -99{
        n
    } else {
        foo(n - 1)
    }
}

// 組み合わせてもいい
#[memoise(-100 <= n < 100)]
fn baz(n: i64) -> i64 {
    if n == -100 {
        n
    } else {
        foo(n - 1)
    }
}

上限の指定はいまのところ必須です。下限の指定がない場合は 0 <= _ を暗黙的に仮定します。

複数キーも指定できます。

#[memoise(n <= 100, k <= 50)]
fn comb(n: usize, k: usize) -> usize {
    if k == 0 {
        return 1;
    }
    if n == 0 {
        return 0;
    }
    comb(n - 1, k - 1) + comb(n - 1, k)
}

キーの型を任意の整数型に

0.1ではキーがusizeじゃないとこけていましたが、0.2では任意の整数型をキーに指定できるようになりました。

キーを式で指定できるように

こんな感じで好きな式をキーとして使えるようになりました。

#[memoise(-10000 <= n * 100 + m <= 10000)]
fn foo(n: i32, m: i32) -> usize {
    todo!()
}

Future work

密配列のテーブルでメモ化する際に欲しい機能はおおよそそろったと思うんですが、 BTreeMapとかで疎なメモ化をするような機能がやっぱりあったほうが用途は広がると思うんで、 そこを追加したいと思います。 あとテーブルサイズを動的に指定する機能もやっぱりあったほうがいい気がしています。