Nemerle でメモ化された関数を作成するのは簡単です。

using Nemerle;

Fib(n : int) : int
{
   | 0 => 0;
   | 1 => 1;
   | _ => Fib(n - 1) + Fib(n - 2);
}
   
[Memoize]
MemoizedFib(n : int) : int
{
   | 0 => 0;
   | 1 => 1;
   | _ => MemoizedFib(n - 1) + MemoizedFib(n - 2);
}

いずれもフィボナッチ数を求めるコードですが， MemoizedFib は [Memoized] が付いているので， 2 回目以降の呼び出しが高速になります。

確かめるために呼び出しごとに n を出力してみましょう。

Non-memoized Fibonacci
First call
n = 5
n = 4
n = 3
n = 2
n = 1
n = 0
n = 1
n = 2
n = 1
n = 0
n = 3
n = 2
n = 1
n = 0
n = 1
5
Second call
n = 5
n = 4
n = 3
n = 2
n = 1
n = 0
n = 1
n = 2
n = 1
n = 0
n = 3
n = 2
n = 1
n = 0
n = 1
5
----------
Memoized Fibonacci
First call
n = 5
n = 4
n = 3
n = 2
n = 1
n = 0
n = 1
n = 2
n = 3
5
Second call
n = 5
5

メモ化された関数は明らかに関数の呼び出し回数が少なくなっています。 2 回目以降の呼び出しについては再帰を行っていないことがわかります。

とても簡単にメモ化できますね。

おまけ

実は n のダンプはマクロを使って次のように実現しました。

Fib([Dump] n : int) : int

このようにする利点は，関数のパターンマッチングの形を崩さなくても良いというところでしょうか。

Dump マクロは次のように定義されます。

using System;
using Nemerle;
using Nemerle.Compiler;

[MacroUsage(MacroPhase.WithTypedMembers, MacroTargets.Parameter, Inherited = true, AllowMultiple = false)]
public macro Dump(_typer : TypeBuilder, method : MethodBuilder, parameter : ParameterBuilder)
{
   def name = <[ $(parameter.AsParsed().PName : name) ]>;
   def format = $"$(parameter.Name) = {0}";
   method.Body = <[
      Console.WriteLine($format, $name);
      $(method.Body);
   ]>;
}

いやあ，マクロって本当に良いものですね。

ソースコードは GitHub にアップロードしています。