函数式编程

本篇来学习Go语言的函数式编程，函数式编程不是Go语言独有的，像Python也是支持函数式编程的，不过Go语言支持函数式编程主要体现在闭包上。

Go语言闭包应用：1）不需要修饰如何访问自由变量；2）没有Lambda表达式，但是有匿名函数 （其实两者差不多）。

接下来谈一谈函数式编程和函数指针的区别，其实我个人更倾向于函数式编程，因为在函数式编程（如Python）中，函数是一等公民，因此参数，变量及返回值都可以是函数；而像函数指针（如C++、Java）函数只是一个名字，其实就是指针。

在函数式编程中，有一个高阶函数的概念，也就是说一个函数可以作为参数传给另外一个函数，或者一个函数的返回值为另外一个函数（若返回值为该函数本身，则为递归），满足其一则为高阶函数，如python中的map，reduce，filter等。还有就是闭包这个概念。

当然可能有人要拿出"正统"函数式编程来说话了，需要满足两点：1）不可变性：不能有状态，只有常量和函数；2）函数只能有一个参数。

这个"正统"函数式编程要求里面不能有变量，只有常量和函数这两种，甚至连选择、循环语句都不能使用；更过分的要求是参数只能有一个参数，之前的参数列表都不能用了，太特么变态了吧。由于Go语言设计时要求按照了这个规定，但是实际上灵活性很大，可以不按照上面"正统"函数式编程的要求来。

下面结合一个例子说明Go语言的函数式编程：计算1+2+3+...+9=?我们先用普通的方法，接着使用函数式编程，然后试着体会两者的不同之处。

普通方法实现的代码如下，这个其实非常简单：

package main
import "fmt"
//定义求和函数，测试函数式编程
func test(n int)int{
 sum:=0
 for i:=0;i<n;i++{
 sum+=i
 }
 return sum
}
func main() {
 fmt.Println(test(10))
}
//运行结果：
45

接下来看一下如何使用函数式编程来实现这个功能：

package main
import "fmt"
//定义求和函数，测试函数式编程
func functionaltest()func(int)int{
 sum:=0
 return func(v int) int {
 sum+=v
 return sum
 }
}
func main() {
 a:=functionaltest()
 for i:=0;i<10;i++{
 fmt.Printf("0+1+...+%d=%d\n",i,a(i))
 }
}
//运行结果：
0+1+...+0=0
0+1+...+1=1
0+1+...+2=3
0+1+...+3=6
0+1+...+4=10
0+1+...+5=15
0+1+...+6=21
0+1+...+7=28
0+1+...+8=36
0+1+...+9=45

其实上面就是闭包，在函数体中包含自由变量和局部变量，这里的sum就是自由变量，v是局部变量。

下面是我从网上找的其他语言如何通过闭包来实现相应的功能：

1）Python中的闭包：python原生支持闭包、使用_closure_来查看闭包内容

def test():
 sum = 0
 def f(value):
 nonlocal sum
 sum += value
 return sum 
 return f

2)C++中的闭包：过去stl或者boost带有类似库；C++11及以后：支持闭包，以下是C++14下编译通过的：

auto test(){
　　auto sum = 0;
 return [-] (int value) mutable {
　　　　sum += value;
　　　　return sum;
　　}
} 

3)Java中的闭包：1.8以后使用Function接口和Lambda表达式来创建函数对象，函数本身不能作为参数和返回值的；1.8以前匿名类或Lambda表达式均支持闭包

Function<Integer,Integer> test() {
　　final Holder<Integer> sum = new Holder<>(0);
 return (Integer value) -> {
　　　　sum.value += value;
　　　　return sum.value;
　　}
}

还有一个问题就是前面说的"正统"函数式编程要求：1）不可变性：不能有状态，只有常量和函数；2）函数只能有一个参数。我们尝试使用代码来实现这个要求，但是实现正统函数式编程不能有状态，那么应该将状态（函数执行结果）放在另一个函数中：

//使用正统函数式编程,只有常量和函数，没有变量
type itest func(int)(int,itest)
func ftest(base int)itest{
 return func(v int) (int, itest) {
 return base+v,ftest(base+v)
 }
}
func main() {
 a:=ftest(0)
 for i:=0;i<10;i++{
 var s int
 s,a =a(i)
 fmt.Printf("0+1+...+%d=%d\n",i,s)
 }
}
//运行结果：
0+1+...+0=0
0+1+...+1=1
0+1+...+2=3
0+1+...+3=6
0+1+...+4=10
0+1+...+5=15
0+1+...+6=21
0+1+...+7=28
0+1+...+8=36
0+1+...+9=45

不过这种正统函数式编程理解起来非常困难，写起来也不容易理解。

斐波那契数列理解闭包

接下来通过斐波那契数列来加深自己对于闭包的理解，同样先使用普通方法，然后使用闭包的方式实现。

普通方法实现输出斐波那契数列：

//chapter06/fibonaqitest/fibonaqi.go文件
package fibonaqi
//1,1,2,3,5,8,13,21...
func FBtest(n int)int{
 a,b:=0,1
 for i:=0;i<n;i++{
 a,b = b,a+b
 }
 return a
}
//chapter06/fibonaqitest/main.go文件：
package main
import (
 "chapter06/fibonaqitest/fibonaqi"
 "fmt"
)
func main() {
 fmt.Println(fibonaqi.FBtest(5))
}
//运行结果：
5

再来试试闭包的实现：

//chapter06/fibonaqitest/fibonaqi.go文件
//闭包
func FPtest()func()int{
 a, b:=0,1
 return func() int {
 a,b=b,a+b
 return a
 }
}

但是这边有一个问题，就是这个函数内无法判断何时输出。其实这种和生成器非常相似，因此每次调用会执行一次该函数：

func main() {
 f:=fibonaqi.FPtest()
 fmt.Println(f()) //闭包函数测试
 fmt.Println(f()) 
}
//运行结果：
1
1

但是这个闭包其实变成了生成器，如果我们想输出斐波那契数列中小于10000的元素，我们需要多次调用这个生成器，直到输出的元素小于10000才停止运行，那么有没有简单的方法呢？我们可以让这个斐波那契函数实现一个输出内容的接口就行了：

//闭包
func FPtest()func()int{
 a, b:=0,1
 return func() int {
 a,b = b,a+b
 return a
 }
}
type IntGenerator func() int
func (g IntGenerator)Read(p[]byte)(n int,err error){
 next:=g() //获取下一个元素
 if next >10000{ //达到10000以上结束
 return 0, io.EOF
 }
 s:=fmt.Sprintf("%d\n",next) //转换成字符串
 // TODO: incorrect if p is too small!
 return strings.NewReader(s).Read(p)
}
//之前用于从文件中输出内容的函数
func PrintFileContent(reader io.Reader){
 scanner:=bufio.NewScanner(reader)
 for scanner.Scan(){
 fmt.Println(scanner.Text())
 }
}
func main() {
 var ft fibonaqi.IntGenerator =fibonaqi.FPtest()
 fibonaqi.PrintFileContent(ft)
}
//运行结果：
1
1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
6765

不过这个代码有一个瑕疵就是这个p对象不能太小，太小就无法输出信息，后续会对这段代码进行修改。

二分搜索树遍历理解闭包

接下来使用之前介绍的二分搜索树遍历的例子来加深对闭包的理解。学过二分搜索树的人肯定知道中序遍历结果是0 9 2 0 6：

但是之前的遍历函数只能实现遍历的功能，接下来让函数实现接口，那它就能干很多事了：

//函数闭包，演示二分搜索树的遍历
func (node *treeNode)Traverse(){
 node.TraverseFunc(func(n *treeNode) {
 n.Print()
 })
 fmt.Println()
}
func (node *treeNode)TraverseFunc(f func(*treeNode)){
 if node==nil{
 return
 }
 node.left.TraverseFunc(f)
 f(node)
 node.right.TraverseFunc(f)
}
func main() {
 var root treeNode //声明一个二分搜索树对象
 root = treeNode{value: 2} //二分搜索树root节点初始化
 root.left = &treeNode{} //二分搜索树root节点左子树初始化
 root.right = &treeNode{6, nil, nil} //二分搜索树root节点右子树初始化,其本质也是一个treeNode对象
 root.right.left =new(treeNode) //给二分搜索树root节点的左子树的左侧创建一个节点
 root.left.right = createTreeNode(9)
 root.reverse()
 fmt.Println("********************")
 root.Traverse()
 //数一下二分搜索树中元素的个数
 nodeCount:=0
 root.TraverseFunc(func(node *treeNode) {
 nodeCount++
 })
 fmt.Println("********************")
 fmt.Println("节点总数为：",nodeCount)
}
//运行结果：
0
9
2
0
6
节点总数为： 5

看到没，我们后实现的TraverseFunc函数的功能非常强大，不仅仅限于遍历。