例如, 使用foreach 來(lái)遍歷集合數(shù)據(jù), 其實(shí)是在重復(fù)how to do(命令式).
提取通用的'思想'為詞語(yǔ)(函數(shù)名), 已經(jīng)是what to do 了.
// csharp
return sourceList.Where(item => item %2 == 0);
// or LINQ
stylereturn from item in sourceList where item % 2 == 0 select item;
// if we have a function(abstract) already.
return sourceList.Where(NumberIsEven);
public int Factorial(int n) {
return n <= ? 1 : n * Factorial(n - 1);
}
>> 每次遞歸都卡在了n*_ 上, 必須等后面的結(jié)果返回后,當(dāng)前函數(shù)的調(diào)用棧才能返回.
n (n-1) ... 3 2 1 // state
--------------------------------------------------------
n*f(n-1) -> (n-1)*f(n-2) -> ... -> 3*f(2) -> 2*f(1) -> 1 // stack in
|
n*r <- (n-1)*(r-1) <- ... <- 3*2 <- 2*1 <- 1 // stack out
private int FactorialHelper(acc, n) {
return n <= 1 ? acc : FactorialHelper(acc * n, n - 1);
}
public int Factorial(int n) { return FactorialHelper(1, n); }
init f(1, n) // stack in
| // stack pop, jump to next
n f(n, n-1) // stack in
| // stack pop, jump to next
n-1 f(n*(n-1), n-2) // stack in
| // stack pop, jump to next
... ... // stack in
| // stack pop, jump to next
2 f((k-1), 1) // stack in
| // stack pop, jump to next
1 k // return result
let memorize f =
let cache = new Dictionary<_, _>()
fun p ->
match cache.TryGetValue(p) with
| true, result -> result
| _ ->
let result = f p
cache.Add(p, result)
result
