函数式编程范式(3):实战举例

快速排序

快速排序由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

python命令式版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def sub_sort(array,low,high):
key = array[low]
while low < high:
while low < high and array[high] >= key:
high -= 1
while low < high and array[high] < key:
array[low] = array[high]
low += 1
array[high] = array[low]
array[low] = key
return low
def quick_sort(array,low,high):
if low < high:
key_index = sub_sort(array,low,high)
quick_sort(array,low,key_index)
quick_sort(array,key_index+1,high)

python 函数式版本

1
2
3
4
5
def q_sort(l):
if l == []: return []
less = filter(lambda x: x < l[0], l[1:])
more = filter(lambda y: y >= l[0], l[1:])
return q_sort(less) + [l[0]] + q_sort(more)

scala 版本

1
2
3
4
5
def quickSort(xs: List[Int]): List[Int] = {
if (xs.isEmpty) xs
else
quickSort(xs.filter(x=>x<xs.head)):::xs.head::quickSort(xs.filter(x=>x>xs.head))
}

Haskell版本:

1
2
3
q_sort n=case n of
[]->[]
(x:xs)->q_sort [a|a<-xs,a<=x]++[x]++q_sort [a|a<-xs,a>x]

$${ a| a \in N ,a <10} $$

Haskell 版本2

1
2
3
4
5
6
7
quicksort :: Ord a => [a] -> [a]
quicksort [] = []
quicksort (p:xs) =
(quicksort lesser) ++ [p] ++ (quicksort greater)
where
lesser = filter (< p) xs
greater = filter (>= p) xs

Memoisation

实际上,Memoisation(备忘?装饰器?)是一种用于通过缓存来加速程序的技术,它通过记住输入量的计算结果,例如函数调用结果,来实现其加速目的。如果遇到相同的输入或者具有相同参数的函数调用,那么之前存储的结果就可以被再次使用,从而避免一些不必要的计算。在很多情况下,可以使用一个简单的数组来存储结果,但也可以使用许多其他的数据结构,例如关联数组,它在Perl语言中叫做哈希,在Python语言中称为字典。
我的理解就是缓存,一旦函数被调用,就把参数和结果缓存起来,如果有人再次调用,直接返回结果,不再重新计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def F(n):
if n==1: return 1
if n==0: return 0
else: return F(n-1)+F(n-2)
def memoize(f):
memo = {}
def new_f(x):
if x not in memo:
memo[x] = f(x)
return memo[x]
return new_f
print "旧版本的fib"
%timeit -n 10 F(30)
F=memoize(F)
print "新版本的fib"
%timeit -n 1 -r 1 F(40)
%timeit -n 1 -r 1 F(40)
旧版本的fib
10 loops, best of 3: 334 ms per loop
新版本的fib
1 loops, best of 1: 243 µs per loop
1 loops, best of 1: 5.01 µs per loop

并行计算

不需要任何改动,所有FP程序都是可以并发执行的。由于所有的数据(变量?符号)都是不可变的,根本不需要采用锁机制,因此完全不需要担心死锁或是并发竞争的发生。在FP程序中没有哪个线程可以修改任何数据,更不用说多线程之间了。这使得我们可以轻松的添加线程,至于那些祸害并发程序的老问题,想都不用想!
FP关于并行的优势不仅于此。就算某个FP程序本身只是单线程的,编译器也可以将其优化成可以在多CPU上运行的并发程序。

1
2
3
String s1 = somewhatLongOperation1();
String s2 = somewhatLongOperation2();
String s3 = concatenate(s1, s2);

如果是函数式程序,编译器就可以对代码进行分析,然后可能分析出生成字符串s1和s2的两个函数可能会比较耗时,进而安排它们并行运行。这在指令式编程中是无法做到的,因为每一个函数都有可能修改其外部状态,然后接下来的函数又可能依赖于这些状态的值。在函数式编程中,自动分析代码并找到适合并行执行的函数十分简单,和分析C的内联函数没什么两样。从这个角度来说用FP风格编写的程序是“永不过时”的.。

硬件厂商已经没办法让CPU运行得再快了。他们只能靠增加CPU核的数量然后用并行来提高运算的速度。这些厂商故意忽略一个事实:只有可以并行的软件才能让你花大价钱买来的这些硬件物有所值。指令式的软件中只有很小一部分能做到跨核运行,而所有的函数式软件都能实现这一目标,因为FP的程序从一开始就是可以并行运行的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import requests
from multiprocessing import Pool
# 读取github 用户名单300人
with open('github_users') as f:
users=f.readlines()
urls=map(lambda x:'https://github.com/{0}?tab=repositories'.format(x.strip()), users)
# 定义每一个爬虫的小程序
def get_count(url):
try: return requests.get(url,timeout=10).text.count("public source")
except : return -1
#多线程爬取
pool=Pool(100)
results=pool.map(get_count,urls)
pool.close()
pool.join()

函数式编程之设计模式

Functional languages have plenty of best practice rules of the form “when you encounter problem X, use code that looks like Y”, which is basically what a design pattern is.

oo vs fp

工厂模式

函数式编程语言中的一个常见特性是一等(first-class)(或高阶)函数,它允许函数充当任何其他数据结构。多亏这一特性,我可以轻松创建基于一些条件返回其他函数的函数,这就是工厂的精髓。例如,如果您有一个将两个数字相加的通用函数,您可以将局部套用用作一个工厂来创建总是将其参数加 1 的函数,即一个增量器

1
2
def adder(x:Int)(y:Int) = x+y
val incrememnter=adder(1)_

currying 被构建到语言或运行时中,因此函数工厂的概念是生来就有的,且不需要额外的结构。
设计模式(很大程度上依赖于结构来解决问题,因而需要大量开销来实现)似乎是一个针对大问题的解决方案。

策略模式

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
35
36
37
38
public interface Strategy {
int compute(int a, int b);
}
public class Add implements Strategy {
public int compute(int a, int b) { return a + b; }
}
public class Multiply implements Strategy {
public int compute(int a, int b) { return a * b; }
}
public class Context {
private final Strategy strategy;
public Context(Strategy strategy) { this.strategy = strategy; }
public void use(int a, int b) { strategy.compute(a, b); }
}
new Context(new Multiply()).use(2, 3);
```
在Scala中,函数是头等公民,可以直接实现如下 。
```scala
type Strategy = (Int, Int) => Int
class Context(computer: Strategy) {
def use(a: Int, b: Int) { computer(a, b) }
}
val add: Strategy = _ + _
val multiply: Strategy = _ * _
new Context(multiply).use(2, 3)

假如策略包含很多方法的话,我们可以使用元组或者样例类把所有方法封装在一起。