10.1.2.1 C# 和 F# 中可重用的记忆化
如果看一下清单 10.3 中建立 add 值的代码，可以发现，它并不真正知道加法，只是使用了 addSimple 函数，因此，也可以处理其他任何函数。为了使代码更通用，我们可以把这个函数改成参数。
我们要写一个函数（C# 中叫方法），参数为函数，返回这个函数的记忆化版本。参数值是做实际工作的函数，返回的函数增加了缓存功能。清单 10.4 是C# 版本的代码。
清单 10.4 泛型记忆化方法 (C#)
Func<T, R> Memoize<T,R>(Func<T, R> func) { [1]
var cache = new Dictionary<T,R>(); <-- 由闭包捕获缓存
return arg => {
R val;
if(cache.TryGetValue(arg, out val)) return val; <-- 返回缓存值
else {
val =func(arg); | 计算值，
cache.Add(arg, val); | 加到缓存中
returnval; |
} };
}
代码类似于清单 10.3 中的专用加法函数；另外，我们首先创建一个缓存，然后，返回在闭包中捕捉缓存的lambda 函数。这样，对于每个返回的函数，将只有一个缓存，这正是我们想要的。
方法签名[1]表明，参数为函数 Func<T, R>，返回相同类型的函数。这样，不改变函数的结构，只是把它包装成另一个实现缓存的函数。签名是泛型的，所以，它可以使用任何接受一个参数的函数；用元组就能突破这个限制。下面的代码实现了两个数字相加的记忆化函数的 C# 版本：
var addMem = Memoize((Tuple<int, int>arg) => {
Console.Write("adding {0} +{1}; ", arg.Item1, arg.Item2);
return arg.Item1 + arg.Item2; });
Console.Write("{0}; ",addMem(Tuple.Create(19, 23))); |[1]
Console.Write("{0}; ",addMem(Tuple.Create(19, 23))); |
Console.Write("{0}; ", addMem(Tuple.Create(18,24))); [2]
运行这段代码，会发现第二段代码只输出“adding 19+23”一次，第三块输出“adding 18 + 24”。这就是说，前面的加法只执行一次，因为，缓存比较两个元组值，当它们的元素都相等时，就找到了一个匹配。这不会处理元组的第一个实现，因为，它没有任何相等的值实现；在 .NET 4.0 中的元组类型，以及本章源代码都是重写（override）了Equals 方法，进行组件值的比较，这称为结构比较（structural comparison），我们会在第十一章详细介绍。要使 Memoize 方法能够处理有多个参数的函数，还有一种选择，重载 Func<T1, T2, R>、Func<T1, T2, T3, R>，等等。在缓存中，仍然把元组作为键，但对于方法的用户来说，它是隐藏的。
[
overload和override的区别：
override（重写）
1、方法名、参数、返回值相同。
2、子类方法不能缩小父类方法的访问权限。
3、子类方法不能抛出比父类方法更多的异常(但子类方法可以不抛出异常)。
4、存在于父类和子类之间。
5、方法被定义为final不能被重写。
overload（重载）
1、参数类型、个数、顺序至少有一个不相同。
2、不能重载只有返回值不同的方法名。
3、存在于父类和子类、同类中。
]
在 F# 中，实现的泛型同样代码更加容易。我们将取清单 10.3 中写的加法代码，把计算的函数作为记忆化函数的参数。可以在清单 10.5 中看到 F# 版本。
清单10.5 泛型记忆化方法(F# Interactive)
> let memoize(f) =
let cache = newDictionary<_, _>() <-- 初始化由闭包捕获的缓存
(fun x –>
matchcache.TryGetValue(x) with
|true, v –> v
| _-> let v = f(x)
cache.Add(x, v)
v);;
val memoize : (‘a -> ‘b) -> (‘a ->‘b) [1]
在 F# 版本中，可以推断出类型签名[1]，所以，我们不必要手工使函数成为泛型。F# 编译器使用泛型化（generalization）就能做到，推断出的签名相当于 C# 代码中显式签名。
这一次，我们将使用更有意义的例子来演示记忆化的有效。我们会回到全世界最喜欢的递归示例：阶乘函数。清单 10.6 试图对这个函数进行记忆化（memoize），但并不完全按照计划......
清单10.6 用实现记忆化的递归函数的困难 (F# Interactive)
> let rec factorial(x) = [1]
printf"factorial(%d); " x
if (x <= 0)then 1 else x * factorial(x - 1);; [2]
val factorial : int –> int
> let factorialMem = memoizefactorial [3]
val factorial : (int -> int)
> factorialMem(2);;
factorial(2); factorial(1);factorial(0); <-- 第一次计算 2!
val it : int = 1
> factorialMem(2);;
val it : int = 1 <-- 使用缓存的值
> factorialMem(3);;
factorial(3); factorial(2); factorial(1);factorial(0) [4] 为什么这个 2! 会重新计算
val it : int = 2
乍一看，代码似乎是正确的。首先把阶乘计算实现为简单的递归函数[1]，然后，使用memoize（记忆化）函数，创建函数的优化版本[3]。我们在后面进行测试，运行相同的调用两次，看上去正常。第一次调用后，结果被缓存，因此，可以重复使用。
最后一个调用[4]就不正确了，或更确切地说，没有按照我们所希望的。问题出在记忆化只覆盖了第一次调用，即 factorialMem(3)。factorial 函数在随后的递归计算期间，直接调用了原始的函数，没有调用记忆化的版本。要解决这个问题，需要把进行递归调用的这一行代码[2]，改成使用记忆化的版本（factorialMem）。这个函数在后面的代码中声明，所以，可以使用 let rec ... and ... 语法来声明两个相互递归的函数。
还有一个简单的方法，就是使用 lambda 函数，只把记忆化的版本公开为可重用的函数。清单 10.7 只用几行代码实现这个函数。
清单10.7改正后可记忆化的 factorial 函数 (F# Interactive)
> let rec factorial = memoize(fun x->
printfn"Calculating factorial(%d)" x
if (x <= 0)then 1 else x * factorial(x - 1));; [1]
warning FS0040: This and other recursivereferences to the |
object(s) being defined will be checked forinitializationsoundness | [2]
at runtime through the use of a delayedreference... |
val factorial : (int -> int)
> factorial(2);;
factorial(2); factorial(1);factorial(0); <-- 先计算几个值
val it : int = 2
> factorial(4);;
factorial(4); factorial(3); <-- 只计算没有的值
val it : int = 24
在这个例子中的 factorial 表示值，它不是语法意义上定义为有参数的函数，相反，它就是值（恰好是函数类型），由 memoize 函数返回的。这就是说，我们并没有声明递归的函数，而是声明递归的值。我们在第八章创建决策树时，用 let rec声明递归值，但是，我们只用它来以更自然的方式写节点，在代码中并没有任何的递归调用。
这一次，我们创建了真正递归的值，因为，值 factorial 在声明它自己的时候就用到了。递归值的困难在于，如果我们不小心，写出引用某个值的代码，可能会在这个值的初始化期间，是无效的操作。下面是不正确初始化的例子：
let initialize(f) = f()
let rec num = initialize (fun _ -> num +1)
在这里，对值 num 的引用出现在 lambda 函数的内部，在初始化期间被调用，当 initialize 函数被调用时，lambda 函数被调用。如果运行这个代码，在 num 被声明的地方，会出现运行时错误。使用递归函数时，函数总是在执行递归调用的时候，才定义；代码可能永远保持循环，但是，这是不同的问题。
我们声明的 factorial，对 factorial 值的引用出现在 lambda 函数中，并不在初始化期间调用，所以，是有效的声明。而F# 编译器在编译时无法区分这两种情况，所以，会发出警告[2]，并增加了运行时检查。不要过于害怕这个！只要确保包含引用的 lambda 函数不在初始化过程中进行计算，就行了。
由于 factorial 声明进行递归调用时，使用记忆化版本，现在可以在任意计算步骤中，读缓存的值。例如，当我们计算 2 的阶乘后，再计算 4 的阶乘，只需要计算剩下的两个值。
注意
到目前为止，我们已经看到了函数编程中的两种优化方法。使用尾递归，要吧避免栈溢出，写出更好的递归函数；记忆化，能够优化任何无副作用的函数。
这两种方法都非常完美地适合迭代开发的风格，被认为是 F# 编程的重要方面。我们可以从简单的实现开始，往往是一个函数，可能是递归的，无副作用。在随后的过程中，对代码中需要优化的地方进行确认。正如我们前面看到的，演变代码的结构，添加面向对象方面，都很容易，优化所需要的改变也相当简单。迭代过程能够在复杂的领域花很小的代价，效益显著。
到目前为止，我们已经看到写高效函数的通用技巧；还有一种数据结构，本身适合于非常具体的优化：集合类型。在下一节，我们要讨论函数式列表，以及以函数方式使用 .NET 数组。