C++函数式编程

当我们说自函数式编程来说,我们会视如下函数式编程的增长相:

  • 函数式编程的老三不行特色:
    • immutable data
      不可变数据
      :像Clojure一样,默认上变量是不可变的,如果你如果改变量,你用把变量copy出去修改。这样一来,可以于你的先后少杀多Bug。因为,程序中之状态糟糕维护,在出现的时节又不好维护。(你得试想一下假设你的顺序来个复杂的状态,当以后人家改变而代码的时光,是格外易出bug的,在互相着这样的题目即使还多矣)
    • first class
      functions
      :这个技术好为你的函数就像变量一样来使用。也就是说,你的函数可以像变量一样叫创造,修改,并不失为变量一样传递,返回或是在函数中嵌套函数。这个有些像Javascript的Prototype(参看Javascript的面向对象编程)
    • 尾递归优化:我们理解递归的坏处,那就算是要是递归很酷的言辞,stack受不了,并会促成性大下滑。所以,我们采用尾递归优化技术——每次递归时都见面引用stack,这样一来能够提升性能,当然,这亟需语言还是编译器的支持。Python就不支持。

  • 函数式编程的几独技术
    • map &
      reduce
       :这个技能毫无多说了,函数式编程最广泛的技术就是指向一个聚做Map和Reduce操作。这比较由过程式的言语来说,在代码上只要双重爱看。(传统过程式的言语需要运用for/while循环,然后于各种变量中管多少倒过来倒过去的)这个好像C++中的STL中之foreach,find_if,count_if之流的函数的玩法。
    • pipeline:这个技能之意是,把函数实例成一个一个的action,然后,把一组action放到一个数组或是列表中,然后拿数据传给这个action
      list,数据就比如一个pipeline一样顺序地被逐一函数所操作,最终收获我们纪念使的结果。
    • recursing
      递归
       :递归最特别的益处就是简化代码,他得管一个扑朔迷离的题目因此特别粗略的代码描述下。注意:递归的精华是讲述问题,而及时正是函数式编程的精髓。
    • currying:把一个函数的大半只参数分解成多独函数,
      然后把函数多层封装起来,每层函数都回一个函数去接受下一个参数这样,可以简化函数的大多独参数。在C++中,这个充分像STL中之bind_1st或是bind2nd。
    • higher order function
      高阶函数
      :所谓高阶函数就是函数当参数,把传播的函数做一个卷入,然后返回这个封装函数。现象上即是函数传进传出,就像面向对象对象满天飞一样。

 

  • 还有函数式的组成部分利益
    • parallelization
      并行:
      所谓并行的意思就是是于彼此环境下,各个线程之间未欲同还是互斥。
    • lazy evaluation
      惰性求值
      :这个要编译器的支撑。表达式不在其让绑定到变量之后虽及时求值,而是在该值被抱用之下求值,也就是说,语句如果x:=expression; (把一个表达式的结果赋值给一个变量)明显的调用这个表达式被计算并把结果放置到 x 中,但是先不随便实际于 x 中的凡什么,直到通过后的表达式中至 x 的援而出了对它的值的急需的时节,而后面表达式自身的求值也得以于延缓,最终为了扭转于外界看来的某某符号而计量是快速增长的负树。
    • determinism 确定性:所谓明显的意思就是是像数学那样 f(x) = y
      ,这个函数无论在什么状况下,都见面获取同的结果,这个我们叫函数的醒目。而不是比如说程序中之众多函数那样,同一个参数,却会于不同之情景下计算起不同的结果。所谓不同之面貌的意就是是我们的函数会依据局部运行着之状态信息的不等而发生变化。

点的那些东西最肤浅了,还是于咱们来循序渐近地扣押有的例子吧。

咱们先行用一个极度简易的例证来证实一下啊是函数式编程。

事先看一个非函数式的例证:

1
2
3
4
int cnt;
void increment(){
    cnt++;
}

这就是说,函数式的应有怎么写吗?

1
2
3
int increment(int cnt){
    return cnt+1;
}

若恐怕会见当是事例太普通了。是的,这个例子就是是函数式编程的则:不借助让表面的多寡,而且也未更改外部数据的值,而是返回一个新的价值为您

咱重来拘禁一个略例子:

1
2
3
4
5
6
7
8
9
10
def inc(x):
    def incx(y):
        return x+y
    return incx
 
inc2 = inc(2)
inc5 = inc(5)
 
print inc2(5) # 输出 7
print inc5(5) # 输出 10

咱得以看到上面十分例子inc()函数返回了其他一个函数incx(),于是我们好用inc()函数来布局各种本子的inc函数,比如:inc2()和inc5()。这个技能其实就是是点所说的Currying技术。从之技能达到,你可能体会到函数式编程的理念:拿函数当成变量来所以,关注被描述问题如无是怎么落实,这样可吃代码更便于读。

Map & Reduce

在函数式编程中,我们无应当为此循环迭代的艺术,我们相应用越高级的不二法门,如下所出示之Python代码

1
2
3
name_len = map(len, ["hao", "chen", "coolshell"])
print name_len
# 输出 [3, 4, 9]

公可以看出这么的代码很爱读,因为,这般的代码是在叙述如干什么,而未是怎么干

我们再次来拘禁一个Python代码的事例:

1
2
3
4
5
6
def toUpper(item):
      return item.upper()
 
upper_name = map(toUpper, ["hao", "chen", "coolshell"])
print upper_name
# 输出 ['HAO', 'CHEN', 'COOLSHELL']

顺手说一下,上面的例证个是休是跟我们的STL的transform有些像?

1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
 
int main() {
  string s="hello";
  string out;
  transform(s.begin(), s.end(), back_inserter(out), ::toupper);
  cout << out << endl;
  // 输出:HELLO
}

在上面Python的异常例子中我们得以视,我们写义了一个函数toUpper,这个函数没有变动传上的价值,只是把染进的价做个大概的操作,然后回。然后,我们管其用当map函数中,就得挺明亮地描述有我们怀念要怎么。而休会见失掉了解一个在循环中的怎么落实之代码,最终以宣读了无数循环的逻辑后才发觉原是者还是大意思。
下面,我们看描述实现方式的过程式编程是怎耍的(看上去是匪是匪设函数式的不可磨灭?):

1
2
3
4
upname =['HAO', 'CHEN', 'COOLSHELL']
lowname =[]
for i in range(len(upname)):
    lowname.append( upname[i].lower() )

对此map我们别忘了lambda表达式:你可以大概地了解吧就是一个inline的匿名函数。下面的lambda表达式相当给:def
func(x): return x*x

1
2
3
squares = map(lambda x: x * x, range(9))
print squares
# 输出 [0, 1, 4, 9, 16, 25, 36, 49, 64]

咱重来瞧reduce怎么玩?(下面的lambda表达式中来三三两两单参数,也就是说每次打列表中落鲜独价值,计算结果后将这价更推广归,下面的表达式相当给:((((1+2)+3)+4)+5)

1
2
print reduce(lambda x, y: x+y, [1, 2, 3, 4, 5])
# 输出 15

Python中的除了map和reduce外,还有有别的如filter, find, all,
any的函数做辅助(其它函数式的言语也来),可以为你的代码更简短,更易读。
我们又来拘禁一个比较复杂的事例:

计算数组中正数的平均值
1
2
3
4
5
6
7
8
9
10
11
12
13
num =[2, -5, 9, 7, -2, 5, 3, 1, 0, -3, 8]
positive_num_cnt = 0
positive_num_sum = 0
for i in range(len(num)):
    if num[i] > 0:
        positive_num_cnt += 1
        positive_num_sum += num[i]
 
if positive_num_cnt > 0:
    average = positive_num_sum / positive_num_cnt
 
print average
# 输出 5

万一用函数式编程,这个事例可以形容成这样:

1
2
positive_num = filter(lambda x: x>0, num)
average = reduce(lambda x,y: x+y, positive_num) / len( positive_num )

C++11玩的法:

1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
#include <algorithm>
#include <numeric>
#include <string>
#include <vector>
using namespace std;
 
vector num {2, -5, 9, 7, -2, 5, 3, 1, 0, -3, 8};
vector p_num;
copy_if(num.begin(), num.end(), back_inserter(p_num), [](int i){ return (i>0);} );
int average = accumulate(p_num.begin(), p_num.end(), 0) / p_num.size();
cout << "averge: " << average << endl;

我们可以看出,函数式编程有如下好处:

1)代码更简便易行了。
2)数据集,操作,返回值都加大至了协同。
3)你以宣读代码的时刻,没有了循环体,于是就好掉了若干临时变量,以及变量倒来倒去逻辑。
4)你的代码变成了在叙述您如果怎么,而无是怎么去干。

最后,我们来拘禁一下Map/Reduce这样的函数是怎来兑现之(下面是Javascript代码)

map函数
1
2
3
4
5
6
7
var map = function (mappingFunction, list) {
  var result = [];
  forEach(list, function (item) {
    result.push(mappingFunction(item));
  });
  return result;
};

下面是reduce函数的javascript实现(谢谢 @下雨在家 修正的自原先的简易版本)

reduce函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function reduce(actionFunction, list, initial){
    var accumulate;
    var temp;
    if(initial){
        accumulate = initial;
    }
    else{
        accumulate = list.shfit();
    }
    temp = list.shift();
    while(temp){
        accumulate = actionFunction(accumulate,temp);
        temp = list.shift();
    }
    return accumulate;
};

Declarative Programming vs Imperative Programming

前提到了多次的函数式编程关注的凡:describe what to do, rather than how
to do it. 于是,我们拿先的过程式的编程范式叫做 Imperative
Programming –
指令式编程,而将函数式的这种范式叫做 Declarative
Programming –
声明式编程。

脚我们看一下连锁的示范(本示例来自立刻篇稿子 )。

遵照,我们有3辆车比赛,简单起见,我们独家让当时3部车来70%的概率可以向前方走相同步,一共发5次会,我们从来各个一样软就3部车之进步状态。

对此Imperative Programming来说,代码如下(Python):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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]

我们可以将这简单重复循环化一些函数模块,这样便于我们重新便于地看代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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()

地方的代码,我们得由主循环开始,我们好非常了解地盼程序的主导,因为我们管程序的逻辑分成了几单函数,这样一来,我们的代码逻辑吗会变换得几乎只稍散,于是我们读代码时只要考虑的上下文就丢掉了过多,阅读代码也会更易。不像第一独示范,如果没注释和认证,你要得花来日子了解一下。若果把代码逻辑封装成了函数后,我们尽管一定给被每个相对独立的程序逻辑取了只名,于是代码成了自解释的

然而,你见面发觉,封装成函数后,这些函数都见面靠让共享的变量来并其状态。于是,我们于宣读代码的经过时,每当我们上到函数里,一量朗诵到看了一个表面的变量,我们立刻要去查此变量的上下文,然后还要以大脑里推演这个变量的状态,
我们才晓得程序的真正逻辑。也就是说,这些函数间必需知道其他函数是怎么改其中间的共享变量的,所以,这些函数是发生状态的

咱们知道,有状态并无是一致起十分好的政工,无论是对代码用,还是针对代码的竞相来说,都是发副作用的。因此,我们如果想个方法把这些状态为丢,于是起了俺们的
Functional Programming
的编程范式。下面,我们来探视函数式的章程应怎么形容?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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]})

面的代码依然拿程序的逻辑分成了函数,不过这些函数都是functional的。因为其来三独症状:

1)它们中莫共享的变量。
2)函数间透过参数与归值来传递数据。
3)在函数里没有临时变量。

俺们还可见到,for循环被递归取代了(见race函数)——
递归是函数式编程中拉动用到的技能,正而前方所说之,递归的本来面目就是是描述问题是什么。

C++ 1

Pipeline

pipeline 管道借鉴于Unix
Shell的管道操作——把多单令串起来,前面命令的出口成为后面命令的输入,如此就一个流式计算。(注:管道绝对是一个伟人的申,他的只要哲学就是KISS

让每个功能就是开同样起事,并把当下起事好最好,软件或者程序的拼装会变得愈加简易与直观。这个设计意见影响很深,包括今之Web
Service,云计算,以及数据的流式计算等等)

遵照,我们如下的shell命令:

1
ps auwwx | awk '{print $2}' | sort -n | xargs echo

而我们抽象成函数式的言语,就比如下这样:

1
xargs(  echo, sort(n, awk('print $2', ps(auwwx)))  )

啊得以接近下面这法:

1
pids = for_each(result, [ps_auwwx, awk_p2, sort_n, xargs_echo])

好了,让我们来瞧函数式编程的Pipeline怎么耍?

我们事先来拘禁一个之类的程序,这个序的process()有三个步骤:

1)找有偶数。
2)乘以3
3)转成字符串返回

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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(第一种办法)应该怎么形容?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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

咱们应用了Python的要字 yield,这个重中之重字主要是回到一个Generator,yield
是一个类 return
的关键字,只是这函数返回的凡独Generator-生成器。所谓生成器的意是,yield返回的凡一个而迭代的目标,并从未真的的行函数。也就是说,只发生那个回来的迭代对象为真正迭代时,yield函数才见面正真的运转,运行及yield语句时就见面停住,然后等下一样软的迭代。(这个是个比较奇怪的第一字)这就算是lazy
evluation。

吓了,根据前的原则——“运Map &
Reduce,不要使用循环
”,那我们因此比较朴实的Map & Reduce吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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

然而她们之代码用嵌套使用函数,这个略带沉,如果我们能够像下这个样子就吓了(第二种方式)。

1
2
3
pipeline_func(nums, [even_filter,
                     multiply_by_three,
                     convert_to_string])

那么,pipeline_func 实现如下:

1
2
3
4
def pipeline_func(data, fns):
    return reduce(lambda a, x: x(a),
                  fns,
                  data)

吓了,在朗诵了如此多之先后后,你可以回头看一下立刻首文章的开对函数式编程的叙说,可能你就是再次有痛感了。

最后,本人欲马上首浅显易懂的篇章能给您感受及函数式编程的思考,就如OO编程,泛型编程,过程式编程一样,我们绝不太纠结是勿是咱的先后就算是OO,就是functional的,我们第一之品中的寓意

参考

  • Wikipedia: Functional
    Programming
  • truly understanding the difference between procedural and
    functional
  • A practical introduction to functional
    programming
  • What is the difference between procedural programming and
    functional programming?
  • Can someone give me examples of functional programming vs
    imperative/procedural
    programming?
  • OOP vs Functional Programming vs
    Procedural
  • Python – Functional Programming
    HOWTO

补充:评论中redraiment的斯评价世家也可读一诵读。

感谢网友S142857 提供的shell风格的python pipeline:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
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)

转载自酷壳,自己留作笔记,感觉是,原文地址:http://coolshell.cn/articles/10822.html