函数式编程的理念

1. FP 理念

1.1 不变性

• 没有变量的概念, 只有'值'.
  • 避免改变状态及可变数据.
  • 三部曲: 编写函数, 使用REPL工具测试, 使用.

1.2 声明性风格

• 代码是描述期望结果的表达式.
  • 将表达式组合起来, 可以同时隐藏执行细节和复杂性.
• 声明性只提出what to do 而不是解决how to do.
  • 例如, 使用foreach 来遍历集合数据, 其实是在重复how to do(命令式).
  • 提取通用的'思想'为词语(函数名), 已经是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);

• C#的LINQ借鉴的是FP的高阶函数以及monad，只是和SQL长的比较像而已(可能是为了避免学习成本)。

1.3 类型

• 每个表达式都有对应的类型, 这确保了表达式组合的正确性.
• 泛型是一种代码重用技术.
  • 使用类型占位符来将真正的类型延迟到运行时再决定.
  • 类型模板, 在需要时插入真实的类型.
  • 包装: 打包了某种具体类型.
    • 包装类: int?其实是指Nullable<T>对int类型的包装。

1.4 表达式求值

• 整个程序就是一个大的表达式.
  • 关心的是表达式的副作用, 而不是其返回值.
  • 没有语句的概念.

2. 高阶函数

• 方便函数的定制.
  • 隐藏具体的执行细节, 将可定制的部分(行为)抽象处理传递给某个高阶函数使用.
  • 类似OO 的模板方法.
• 提升
  ('a -> 'b) -> M<'a> -> M<'b>
  lift2: ('a -> 'b -> 'c) -> M<'a> -> M<'b> -> M<'c>
  • 允许将一个对值进行处理的函数转换为一个在不同设置中完成相同任务的函数.

3. 柯里化(Currying) 和部分函数应用

• 柯里化（Currying）

function addBy(value) 
{ 
  return function(n) {  
    // 将value 的进行闭包处理
    return n + value; 
  };
}
var add10 = addBy(10);
var result11 = add10(1);

// orElse
var result11 = addBy(10)(1);

• 多个参数时:
  let fakeAddFn n1 = fun n2 -> fun n3 -> fun n4 -> n1 + n2 + n3 + n4

4. 递归及优化

• 尾递归优化:
  • 当在递归调用的时候,不需要做任何工作, 则可以从当前的调用栈直接跳到下一次的调用栈上去.
  • 关键是对累加器的使用.
  • 当需要处理非常庞大的列表时.

public int Factorial(int n) {
    return n <= ? 1 : n * Factorial(n - 1);
}
>> 每次递归都卡在了n*_ 上, 必须等后面的结果返回后,当前函数的调用栈才能返回.
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

• fold 自带累加器的化简函数, 抽取了遍历并化简核心的步骤, 仅将需要自定义的部分以参数的形式放出来.
  • fold 的累加器需要指定一个初始值, 而reduce 的初始累加器使用列表的第一个值.

5. 记忆化

• FP 函数是没有副作用的
  • 也就意味着以相同的参数调用同一函数将会返回相同的结果.
  • 对于一些会被多次调用的函数, 将对应参数的求值结果缓存起来, 以后遇到相同的参数直接返回缓存结果.
• 通用的记忆化函数

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

6. 惰性求值

• 立刻求值: 将表达式n % 2 == 0 ? "right" : "wrong"绑定到标识（即变量名）isEven上
• 将isEven 绑定到某种结构上, 结构知道如何求值,并且是按需求求值.
  • var isEven = new Lazy<string> (() => n % 2 == 0 ? "right" : "wrong");
  • 使用isEven.value 来即可求值并拿到结果.
• 通过函数，函数表达了某种可以得到值的方式，但是需要调用才能得到.
  • var isEven = (Func<string>)(() => n % 2 == 0 ? "right" : "wrong");
  • 通过函数调用isEven() 来立刻获取值.

7. 延迟

• 回调函数: 延后了某种行为, 且该行为对上下文有依赖.
• 手段: 在函数调用结束后自动调用指定的行为(函数).
  • 在进行尾递归优化时, 之前累加器累加的值, 延迟使得可以累加行为.
• 延迟可以推导出bind: 外层匹配模式.

// binding:
('a -> 'b)    -> 'a -> 'b
// map:
('a -> 'b)    -> M<'a> -> M<'b>
// bind:
('a -> M<'b>) -> M<'a> -> M<'b>

10. Mics

• 一等用来描述'值', 函数被看做一等公民, 就是函数等价于'值'的概念.
• 高阶函数: 以一个函数(而不是值)作为参数; 返回一个函数作为结果.
• 编程方式
  • 命令式编程: 建立在直接操作和检查程序状态之上.
    • 局限于细节.
    • 函数式的思路是将程序拆分并抽象成多个函数再组装回去.
  • 面向对象编程
    • js 是利用现有的对象作为原型来生产特定的实例.
    • 必须有一个语义的自引用(this).
  • 元编程
    • 可以通过编写代码来改变某些代码被解释的方式.
    • this 引用的动态性质可以用来元编程.
• 集合中心编程.
  • 用100 个函数操作一个数据结构, 比用10 个函数操作10 个数据结构要好.
• 闭包的两个重点
  • 闭包会捕获一个值(或引用), 并多次返回相同的值.
  • 每个新的闭包都会捕获不一样的值.