# 函数式编程在 Java 和 Go 中的应用

函数式编程是一种 ["编程范式"](https://en.wikipedia.org/wiki/Programming_paradigm)（programming paradigm），就是如何编写程序的方法论。

函数式编程特点：

1. 函数是"第一等公民"
    
2. 只用"表达式"，不用"语句" "表达式"（expression）是一个单纯的运算过程，总是有返回值；"语句"（statement）是执行某种操作，没有返回值。函数式编程要求，只使用表达式，不使用语句。也就是说，每一步都是单纯的运算，而且都有返回值。
    
3. 没有"副作用" 所谓"副作用"（side effect），指的是函数内部与外部互动（最典型的情况，就是修改全局变量的值），产生运算以外的其他结果。 函数式编程强调没有"副作用"，意味着函数要保持独立，所有功能就是返回一个新的值，没有其他行为，尤其是不得修改外部变量的值。
    
4. 不修改状态 变量往往用来保存状态，函数式编程只是返回新的值，不修改系统变量，因此不修改状态。函数式编程使用参数保存状态，例如递归。
    
5. 引用透明 引用透明（Referential transparency），指的是函数的运行不依赖于外部变量或"状态"，只依赖于输入的参数，任何时候只要参数相同，引用函数所得到的返回值总是相同的。（幂等的）
    

为什么使用函数式编程；

1. 代码简洁，开发快速
    
2. 接近自然语言，易于理解
    
3. 易于"并发编程"
    

### Go 中的函数式编程

Go 没有 lambda 表达式，直接定义匿名函数作为变量

```go
func main() {
	f := func(word string) {
		fmt.Println(word)
	}
	f("test!")
}
```
#### 接口型函数

接口型函数的价值在于:

- 既能够将普通的函数类型（需类型转换）作为参数，也可以将结构体作为参数， 使用更为灵活，可读性也更好

**接口型函数要求接口只有一个方法**
接口型函数在调用实现的接口方法 时调用的就是接口型函数自身

```go
// 接口
type Getter interface {
	Get(key string) ([]byte, error)
}

// 函数类型，实现了 Getter
// 函数类型实现接口，称为接口型函数
// 使用者在调用时既能传入函数作为参数，也能传入实现了该接口的结构体作为参数
type GetterFunc func(key string) ([]byte, error)

// 实现了接口 Getter 的方法
func (f GetterFunc) Get(key string) ([]byte, error) {
	return f(key)
}


// 结构体实现 Getter 接口
type DB struct {
	url string
}

func (db *DB) Get(key string) ([]byte, error) {
	return []byte(key + db.url), nil
}

func GetFromSource(getter Getter, key string) []byte {
	buf, err := getter.Get(key)
	if err != nil {
		return nil
	}
	return buf
}
// 接口型函数的价值在于:
// 既能够将普通的函数类型（需类型转换）作为参数，也可以将结构体作为参数
// 使用更为灵活，可读性也更好
func TestImplementFunc(t *testing.T) {
	// 使用接口型函数，匿名函数类型换转为 GetterFunc，GetterFunc 是实现了 Getter 接口的接口型函数
	// 既可以使用匿名函数，也可以使用具名函数，只要参数和返回值与 Getter 接口的 Get 函数相同即可
	// 接口型函数要求接口只有一个方法
	// 接口型函数在调用实现的接口方法 Get 时调用的就是接口型函数自身
	GetFromSource(GetterFunc(func(key string) ([]byte, error) {
		return []byte(key), nil
	}), "key")

	// 也可以传入实现了 Getter 接口的结构体
	// 适用于逻辑复杂的请求，比如数据库访问等需要很多参数的情况
	GetFromSource(new(DB), "key")
}
```

##### http 包中的示例

例如在 http 中的 Handle 方法和 HandleFunc 方法中的第二个参数 Handler 就是一个接口，这个接口既可以传入接口型函数，也可以传入实现接口的结构体

```go
func Handle(pattern string, handler Handler) {
	DefaultServeMux.Handle(pattern, handler)
}
func HandleFunc(pattern string, handler func(ResponseWriter, *Request)) {
	DefaultServeMux.HandleFunc(pattern, handler)
}
```

Handler 接口

```go
type Handler interface {
	ServeHTTP(ResponseWriter, *Request)
}
```

实现了 Handler 接口的接口型函数 HandlerFunc 实现了 ServeHTTP 方法

```go
type HandlerFunc func(ResponseWriter, *Request)

func (f HandlerFunc) ServeHTTP(w ResponseWriter, r *Request) {
	f(w, r)
}
```

其中 Handle 和 HandleFunc 函数是相同的，因为 HandleFunc 函数将函数转换为了 HanderFunc 接口型函数

```go
func (mux *ServeMux) HandleFunc(pattern string, handler func(ResponseWriter, *Request)) {
	if handler == nil {
		panic("http: nil handler")
	}
	mux.Handle(pattern, HandlerFunc(handler))
}
```

这两个函数都是通过 ServMux 的 Handle 函数执行的，第二参数是 Handler 接口

```go
func (mux *ServeMux) Handle(pattern string, handler Handler)
```
##### 类似于 Java 中的函数式接口

Java 中的函数式接口也是只有一个方法。lambada 表达式、匿名函数相当于实现了这个函数式接口中的这个函数。


### Java 中的函数式编程

Java 中无法直接定义函数，Java 中的函数式编程几乎等同于 lambda 表达式！

Lambda 表达式、流式编程都是 Java 8 才有的，lambda 表达式主要应用于流式编程中。

```java
Random random = new Random(47);
long count = Stream.generate(() -> random.nextInt(10))
        .limit(10)
		//.peek((x) -> System.out.println(x))
        .peek(System.out::println)
        .count();
System.out.println(count);
```

Lambda 表达式 ()->{} 方法列表和方法体，省略方法名称，参数和返回值类型都是可以自动推断的

方法引用是用来简写 lambda 表达式的，方法引用只看传入参数和返回值，不看函数名称！

#### 函数式接口

函数式接口的特点： 每个接口有且仅有一个抽象方法，称为函数式方法，这个接口叫做函数式接口。 `@FunctionalInterface` 注释保证有且仅有一个抽象方法。

Stream 中的 generate 函数需要一个 Supplier 类型的对象，其中 Supplier 就是函数式接口。

```java
public static<T> Stream<T> generate(Supplier<T> s) {
    Objects.requireNonNull(s);
    return StreamSupport.stream(
            new StreamSpliterators.InfiniteSupplyingSpliterator.OfRef<>(Long.MAX_VALUE, s), false);
}
```

```java
@FunctionalInterface
public interface Supplier<T> {
    T get();
}
```

Stream 中的 peek 方法需要一个 Consumer 类型的对象，Consumer 也是一个函数式接口。

```java
Stream<T> peek(Consumer<? super T> action);
```

```java
@FunctionalInterface
public interface Consumer<T> {
    void accept(T t);
	....
}
```

可以将 lambda 表达式和方法引用赋值给函数式接口

```java
Random random = new Random(47);
Supplier<Integer> s = () -> random.nextInt(10);
Consumer<Integer> c = System.out::println;
```

Java 8 引入 java.util.function 包，定义了许多函数式接口。

### 闭包

1. 封装性：闭包可以将函数和它的环境封装在一起（变量捕获），使得函数可以访问它的环境中的变量，而无需暴露给外界。
    
2. 动态作用域：闭包可以在运行时动态的改变它的作用域，使得代码具有更高的灵活性和可扩展性。
    

#### Java 中的闭包

`i` 有单独的生命周期

```java
class Closure1 {
    int i;
    IntSupplier makeFun(int x) {
        return () -> x + i++;
    }
}
class SharedStorage {
    public static void main(String[] args) {
        Closure1 c1 = new Closure1();
        IntSupplier f1 = c1.makeFun(0);
        IntSupplier f2 = c1.makeFun(0);
        IntSupplier f3 = c1.makeFun(0);
        System.out.println(f1.getAsInt());
        System.out.println(f2.getAsInt());
        System.out.println(f3.getAsInt());
    }
}
```

Java 闭包中的变量必须是不可变的。用 final 修饰或者等同 final 的。

```java
class Closure2 {
    IntSupplier makeFun(int x) {
        int i = 0;
        //return () -> x++ + i++;   // x++ 和 i++ 都会报错
        //x++;  // 报错
        //i++;  // 报错
        return () -> x + i;
    }
}
```

#### Go 中的闭包

Go 语言中闭包不需要要求被捕获的变量必须是不可变的

```go
func HighFunction() func() int {
	i := 0
	return func() int {
		i++
		return i
	}
}

func main() {
	fmt.Printf("%#v \n", HighFunction()())
}
```

#### capture-by-value vs capture-by-reference

Python 和 go 函数式编程中的闭包都是 capture-by-reference，在闭包中可以直接修改外部变量的值，外部变量和闭包中的变量指向的是同一块内存

Java 闭包是 capture-by-value，值传递通过 copy 方式传进闭包，闭包中使用的变量和闭包外的变量指向不同的内存，因此闭包外的变量需要是 final 的。如果不是 final 的话，在闭包内修改变量不会影响闭包外的变量，导致数据不一致

* 值捕获（capture-by-value）：只需要在创建闭包的地方把捕获的值拷贝一份到对象里即可。Java 的匿名内部类和 Java 8 新的 lambda 表达式都是这样实现的。
    
* 引用捕获（capture-by-reference）：把被捕获的局部变量“提升”（hoist）到对象里。C#的匿名函数（匿名委托/lambda 表达式）就是这样实现的。
    

#### 闭包导致的 for 循环问题

for range 中的问题，for range 语法会将 nums 中的值全部赋值给同一块内存地址 n，`fmt.Printf("%#v \n", &n)` 可以看到所有 n 的地址都是同一个地址！funcs 函数数组中的所有函数都没有被执行，n 的值被包含在函数闭包中被延迟执行了，所有函数的指针的值都指向同一个地址。

```go
func main() {
	nums := []int{1, 2, 3, 4, 5}
	var funcs []func()
	for _, n := range nums {
		// num := n
		funcs = append(funcs, func() {
			fmt.Printf("%v ", n)
		})
		// funcs = append(funcs, func() {
		// 	fmt.Printf("%v ", num)
		// })
	}
	for _, f := range funcs {
		f()
	}
}
/*
5 5 5 5 5
*/
```

```go
func main() {
	nums := []int{1, 2, 3, 4, 5}
	var funcs []func()
	for i := 0; i < len(nums); i++ {
		// num := nums[i]
		funcs = append(funcs, func() {
			fmt.Printf("%v ", nums[i])
		})
		// funcs = append(funcs, func() {
		// 	fmt.Printf("%v ", num)
		// })
	}
	for _, f := range funcs {
		f()
	}
}
// 报错，因为 i 最后 ++ 后越界了
```

协程中也会遇到这种问题：

```go
func main() {
	nums := []int{1, 2, 3, 4, 5}
	for _, num := range nums {
		go func() {
			fmt.Printf("%v ", num)
		}()
		// 方法一
		// n := num
		// go func() {
		// 	fmt.Printf("%v ", n)
		// }()
		// 方法二
		// go func(n int) {
		// 	fmt.Printf("%v ", n)
		// }(num)
	}
	time.Sleep(1 * time.Second)
}
```

如果传递参数是指针的话，指针复制，所有协程中的指针指向同一块内存，这是 for range 的问题，不是闭包的问题

```go
func main() {

	nums := []int{1, 2, 3, 4, 5}
	for _, num := range nums {
		nPtr := &num
		go func(p *int) {
			fmt.Printf("%v ", *p)
		}(nPtr)
	}
	time.Sleep(1 * time.Second)
}
```

> 使用指针的时候要小心！

### Map Reduce

类似于 Java 的策略设计模式

#### Map

将 for 循环代码复用，多个 map 方法实现

```go
type Option func(word string) string

func UpperWord(word string) string {
	return strings.ToUpper(word)
}
func LowerWord(word string) string {
	return strings.ToLower(word)
}
func MapString(words []string, option Option) []string {
	var ans []string
	for _, word := range words {
		ans = append(ans, option(word))
	}
	return ans
}

func main() {
	words := strings.Split("My name is test", " ")
	words = MapString(words, UpperWord)
	fmt.Printf("%#v \n", words)
	words = MapString(words, LowerWord)
	fmt.Printf("%#v \n", words)
}
```

#### Reduce

统计字符串一共多少个字符

```go
func Reduce(words []string, f func(string) int) int {
	ans := 0
	for _, word := range words {
		ans += f(word)
	}
	return ans
}

func main() {
	words := strings.Split("My name is test", " ")

	cnt := Reduce(words, func(word string) int {
		return len(word)
	})
	fmt.Printf("%#v \n", cnt)
}
```

#### Filter

过滤偶数

```go
func Filter(nums []int, f func(num int) bool) []int {
	var ans []int
	for _, num := range nums {
		if f(num) {
			ans = append(ans, num)
		}
	}
	return ans
}
func main() {
	nums := []int{1, 2, 3, 4, 5, 6, 7}
	ans := Filter(nums, func(num int) bool {
		if num%2 == 0 {
			return true
		}
		return false
	})
	fmt.Printf("%#v \n", ans)
}
```

### Functional Options

通用的两种方式：

```go
type MyStruct struct {
	FirstName  string
	SecondName string
}

// 封装一下构造函数，让构造代码重用
func NewMyStruct(firstName string, secondName string) MyStruct {
	return MyStruct{
		FirstName:  firstName,
		SecondName: secondName,
	}
}

func main() {

	// 每次构建对象都十分复杂
	s1 := MyStruct{}
	s2 := MyStruct{
		FirstName: "firstName",
	}
	s3 := MyStruct{
		FirstName:  "firstName",
		SecondName: "secondName",
	}
	fmt.Printf("%#v \n", s1)
	fmt.Printf("%#v \n", s2)
	fmt.Printf("%#v \n", s3)

	// 输入无意义的字段
	ms1 := NewMyStruct("", "")
	ms2 := NewMyStruct("firstname", "")
	ms3 := NewMyStruct("firstname", "secondname")

	fmt.Printf("%#v \n", ms1)
	fmt.Printf("%#v \n", ms2)
	fmt.Printf("%#v \n", ms3)
}
```

```go
type MyStruct struct {
	FirstName  string
	SecondName string
}

type Option func(s *MyStruct)

func WithFirstName(firstName string) Option {
	return func(s *MyStruct) {
		s.FirstName = firstName
	}
}
func WithSecondName(secondName string) Option {
	return func(s *MyStruct) {
		s.SecondName = secondName
	}
}
func NewMyStruct(options ...Option) MyStruct {
	s := &MyStruct{}
	for _, option := range options {
		option(s)
	}
	return *s
}
func main() {
	ms1 := NewMyStruct()
	ms2 := NewMyStruct(WithFirstName("firstname"))
	ms3 := NewMyStruct(WithFirstName("firstname"), WithSecondName("secondname"))
	fmt.Printf("%#v \n", ms1)
	fmt.Printf("%#v \n", ms2)
	fmt.Printf("%#v \n", ms3)
}
```

### 柯里化

柯里化意为：将一个多参数的函数，转换为一系列单参数函数。

```go
func Add(x int, y int) int {
	return x + y
}

func Curry(x int) func(y int) int {
	return func(y int) int {
		return x + y
	}
}

func main() {
	fmt.Printf("%#v \n", Add(1, 1))
	fmt.Printf("%#v \n", Curry(1)(1))
}
```

### 尾递归优化

尾递归调用（Tail Call）是函数式编程的一个重要概念，指某个函数的最后一步是调用另一个函数。

递归非常耗费内存，因为需要同时保存成千上百个调用记录，很容易发生"栈溢出"错误（stack overflow）。但对于尾递归来说，由于只存在一个调用记录，所以永远不会发生"栈溢出"错误。

计算 n 的阶乘，最多需要保存 n 个调用记录，复杂度 O(n) 。如果改写成尾递归，只保留一个调用记录，复杂度 O(1) 。

```go
func fib(n int) int {
	if n == 1 {
		return 1
	}
	return n * fib(n-1)
}
func fib2(n int, total int) int {
	if n == 1 {
		return total
	}
	return fib2(n-1, n*total)
}

func main() {
	fmt.Printf("%#v \n", fib(10))
	fmt.Printf("%#v \n", fib2(10, 1))
}
```