编程范式系列-函数式编程

SystemDesign 编程范式

创建时间:2020-02-04 12:29

字数:1.9k 阅读:

评论:

1. 从c++到函数式编程
2. 函数式编程

1. 从c++到函数式编程

C++很大程度上解决了C语言中的各种问题和不便，尤其是通过类、模板、虚函数和运行时识别，解决了C语言的泛型编程问题。函数式编程 -> 更为抽象的泛型。

2. 函数式编程

2.1 定义

函数式编程只关心**定义的输入数据和输出数据相关的关系，数学表达式里面其实是在做一种映射(mapping)，输入的数据和输出的数据关系是什么样子的，是用函数来定义的。

2.2 特征

2.2.1 优势

stateless

不维护任何状态，给数据，我做处理，然后给你处理完的数据，中间的过程量用完就没了

无状态的话并行执行无害了，重构代码无伤害

immutable

输入数据动了，输出数据也会变，意味着新的数据集会被返回

惰性求值

表达式不在它被绑定到变量之后立即求值，而是在该值被取用的时候求值。

确定性

f(x)=y, 这个函数无论在什么场景下，都会得到同样的结果，这个我们称之为函数的确定性。而不是像程序中的很多函数那样，同一个参数，却会在不同的场景下计算出不同的结果。所谓不同的场景，就是我们的函数会根据运行中的状态信息的不同而发生变化。

2.2.2 劣势
- 数据复制很严重
- 函数式编程抽象度更高，实现方式上，函数套函数，函数返回函数，函数里定义函数…

2.3 函数式编程用到的技术

first class function 头等函数

把函数当成变量来使用。可以像变量一样被创建、修改，并当成变量一样传递、返回，或者是在函数中嵌套函数

tail recursion optimization 尾递归优化

如果递归很深的话，stack受不了，会导致性能大幅度下降。因此我们使用尾递归优化技术，每次递归的时候都会重用stack

map & reduce
pipeline

将函数实例成一个个action，然后将一组action放到一个数组或列表中，再把数据传给这个action list，数据就被各个函数所操作，最终得到我们想要的结果。

recursing

将复杂问题用简单的代码描述出来。

currying 颗粒化

将一个函数的多个参数分解成多个函数，然后将函数多层封装起来，每层函数都返回一个函数去接收下一个参数，这可以简化函数的多个参数。

higher order function 高阶函数

函数当参数，把传入的函数做一个封装，然后返回这个封装函数

2.4 函数式编程的理念

// 非函数式，有状态的
int cnt;
void increment() {
    cnt ++;
}

// 函数式， 无状态的
int increment(int cnt) {
    return cnt + 1;
}

把函数当成变量来用，关注描述问题而不是怎么实现的，可以让代码更易读
因为函数返回里面的这个函数，所以函数关注的是表达式，关注的是描述这个问题，而不是如何实现的

2.4.1 函数式编程例子

下面我们看一下相关的示例。比如，我们有 3 辆车比赛，简单起见，我们分别给这 3 辆车有 70% 的概率可以往前走一步，一共有 5 次机会，然后打出每一次这 3 辆车的前行状态。

// Imperative Programming 
from random import random

time = 5
car_positions = [1, 1, 1]

while time:
    # decrease time
    time -= 1

    print ''
    for i in range(len(car_positions)):
        # move car
        if random() > 0.3:
            car_positions[i] += 1

        # draw car
        print '-' * car_positions[i]

下面这个例子是将循环分成了几个小函数，但是相互之间的参数是共享的，函数是有状态的。

// make it to some function model 
from random import random

def move_cars():
    for i, _ in enumerate(car_positions):
        if random() > 0.3:
            car_positions[i] += 1

def draw_car(car_position):
    print '-' * car_position

def run_step_of_race():
    global time
    time -= 1
    move_cars()

def draw():
    print ''
    for car_position in car_positions:
        draw_car(car_position)

time = 5
car_positions = [1, 1, 1]

while time:
    run_step_of_race()
    draw()

函数式写法

from random import random

def move_cars(car_positions):
    return map(lambda x: x + 1 if random() > 0.3 else x, car_positions)

def output_car(car_position):
    return '-' * car_position

def run_step_of_race(state):
    return {'time': state['time'] - 1, 'car_positions': move_cars(state['car_positions'])}

def draw(state):
    print ''
    print '\n'.join(map(output_car, state['car_positions']))

def race(state):
    draw(state)
    if state['time']:
        race(run_step_of_race(state))

race({'time': 5,
      'car_positions': [1, 1, 1]})

上面的代码依然把程序的逻辑分成了函数。不过这些函数都是函数式的，它们有三个特点：它们之间没有共享的变量；函数间通过参数和返回值来传递数据；在函数里没有临时变量。

2.5 函数式语言常用函数

map()
reduce()
filter()

好处：

数据集、对数据的操作和返回值都放在了一起。
没有了循环体，就可以少了些临时用来控制程序执行逻辑的变量，也少了把数据倒来倒去的控制逻辑。
代码变成了在描述你要干什么，而不是怎么干

2.5.1 E.G

process:

找出偶数
乘3
转成字符串

def process(num):
# filter out non-evens
if num % 2 != 0:
    return
num = num * 3
num = 'The Number: %s' % num
return num

nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

for num in nums:
    print process(num)

# 输出：
# None
# The Number: 6
# None
# The Number: 12
# None
# The Number: 18
# None
# The Number: 24
# None
# The Number: 30

pipeline way

使用了yield关键字，返回generator，一个可迭代对象，并没有真正的执行函数。意味着只有其返回的迭代对象被迭代时，yield函数才会真正运行

def even_filter(nums):
for num in nums:
    if num % 2 == 0:
        yield num
def multiply_by_three(nums):
    for num in nums:
        yield num * 3
def convert_to_string(nums):
    for num in nums:
        yield 'The Number: %s' % num

nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
pipeline = convert_to_string(multiply_by_three(even_filter(nums)))
for num in pipeline:
    print num
# 输出：
# The Number: 6
# The Number: 12
# The Number: 18
# The Number: 24
# The Number: 30

使用map & reduce

def even_filter(nums):
return filter(lambda x: x%2==0, nums)

def multiply_by_three(nums):
    return map(lambda x: x*3, nums)

def convert_to_string(nums):
    return map(lambda x: 'The Number: %s' % x,  nums)

nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
pipeline = convert_to_string(
               multiply_by_three(
                   even_filter(nums)
               )
            )
for num in pipeline:
    print num

pipeline model

class Pipe(object):
def __init__(self, func):
    self.func = func

def __ror__(self, other):
    def generator():
        for obj in other:
            if obj is not None:
                yield self.func(obj)
    return generator()

@Pipe
def even_filter(num):
    return num if num % 2 == 0 else None

@Pipe
def multiply_by_three(num):
    return num*3

@Pipe
def convert_to_string(num):
    return 'The Number: %s' % num

@Pipe
def echo(item):
    print item
    return item

def force(sqs):
    for item in sqs: pass

nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

force(nums | even_filter | multiply_by_three | convert_to_string | echo)

3. 修饰器模式 decorator

Python 用一个函数来构造另一个函数

def hello(fn):
    def wrapper():
        print "hello, %s" % fn.__name__
        fn()
        print "goodbye, %s" % fn.__name__
    return wrapper

@hello
def Hao():
    print "i am Hao Chen"

Hao()


// code result:
$ python hello.py
hello, Hao
i am Hao Chen
goodbye, Hao

Hello 注解就是我们前面定义的hello函数，hello函数中需要一个参数fn，用来做回调，hello函数中返回了一个inner函数wrapper，回调了传进来的fn

4. 总结

函数式编程，将运算过程尽量写成一系列嵌套的函数调用，关注的是做什么而不是怎么做，被称为声明式编程。以stateless和immutable为主要特点。

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 stone2paul@gmail.com