[数据结构与算法]Go学习:函数式编程

函数式编程VS函数指针

• 函数是一等公民:参数,变量,返回值都可以是函数
• 高阶函数:函数的参数还可以是函数
• 函数->闭包

"正统"函数式编程

• 不可变性:不能有状态,只有常量和函数
• 函数只能有一个参数
• go语言是一个通用的语言,它不会再正统函数式编程做过多的文章

package main

import "fmt"

type iAdder func(int) (int, iAdder)

func adderi(base int) iAdder {
	return func(i int) (int, iAdder) {
		return base + i, adderi(base + i)
	}
}

func main() {
	a := adderi(0)
	for i := 0; i < 10; i++ {
		var s int
		s, a = 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
		fmt.Printf("0+1+...+%d=%d\n", i, s)
	}

}

闭包

闭包可以理解成 “定义再一个函数内部的函数”.再本质上闭包是将函数内部和函数外部连接起来的桥梁.或者说是函数和其引用环境的组合体

package main

import "fmt"

func adder() func(int) int {
	sum := 0
	return func(i int) int {
		sum += i
		return sum
	}
}

func main() {
	a := adder()
	for i := 0; i < 10; 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
		fmt.Printf("0+1+...+%d=%d\n", i, a(i))
	}

}

sum不是函数体里面定义的,是一个自由变量,自由变量就会连一根线连到sum上面,不断的找连接关系,连成一棵树最终会把所有我们要连接的变量都连到,就个就是函数式编程的闭包

其他语言的闭包

python中的闭包

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

• python原生支持闭包
• 使用_closure_来查看闭包内容

c++中闭包

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

• 过去:stl或者boost带有类似库
• c++11及以后:支持闭包

java中的闭包

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

• 1.8以后:使用Function接口和Lambda表达式来创建函数对象
• 匿名类或Lambda表达式均支持闭包

go语言闭包应用

斐波那契数列

package main

import "fmt"

func fibonacci() func() int {
	a,b:=0,1
	return func()int{
		a,b = b,a+b
		return a
	}
}
func main() {
	f := fibonacci()
	fmt.Println(f()) // 1
	fmt.Println(f()) // 1
	fmt.Println(f()) // 2
	fmt.Println(f()) // 3
	fmt.Println(f()) // 5
	fmt.Println(f()) // 8
	fmt.Println(f()) // 13
	fmt.Println(f()) // 21
}

为函数实现接口

package main

import (
	"bufio"
	"fmt"
	"io"
	"strings"
)

func fibonacci() intGen {
	a, b := 0, 1
	return func() int {
		a, b = b, a+b
		return a
	}
}

type intGen func() int

func (g intGen) Read(p []byte) (n int, err error) {
	next := g()
	if next > 10000 {
		return 0, io.EOF
	}
	s := fmt.Sprintf("%d\n", next)
	return strings.NewReader(s).Read(p)
}

func printFileContents(reader io.Reader) {
	scanner := bufio.NewScanner(reader)
	for scanner.Scan() {
		fmt.Println(scanner.Text())
	}
}

func fib(n int) int {
	var res int
	f := fibonacci()
	for i := 1; i < n; i++ {
		res = f()
	}
	return res
}
func main() {

	f := fibonacci()
	// 1
	// 1
	// 2
	// ...
	printFileContents(f)
}

使用函数遍历二叉树

package main

import "fmt"

type Node struct {
	Value       int
	Left, Right *Node
}

func CreateNode(value int) *Node {
	return &Node{Value: value}
}

func (node Node) Print() {
	fmt.Print(node.Value, " ")
}

func (node *Node) SetValue(value int) {
	if node == nil {
		fmt.Println("node is nil")
		return
	}
	node.Value = value
}

func (node *Node) Traverse() {
	node.TraverseFunc(func(n *Node) {
		n.Print()
	})
	fmt.Println()
}
func (node *Node) TraverseFunc(f func(node *Node)) {
	if node == nil {
		return
	}
	node.Left.TraverseFunc(f)
	f(node)
	node.Right.TraverseFunc(f)
}

func main() {
	root := Node{Value: 3}
	root.Left = &Node{Value: 1}
	root.Right = &Node{5,nil,nil}
	root.Right.Left = new(Node)
	root.Left.Right = CreateNode(2)
	root.Right.Left.SetValue(4)
	
	// 1 2 3 4 5
	root.Traverse()
	
	count := 0
	root.TraverseFunc(func(node *Node) {
		count++
	})
	// 5
	fmt.Println(count)
}

go语言对闭包的想法更为自然,不像其他的语言语法看起来怪怪的,不需要修饰如何访问自由变量,没有Lambda表达式,但是有匿名函数