用递归代替循环
几乎是函数式编程里面最经典的思想。
# 在1-100中去除2,3的倍数
lst = []
for i in range(1, 101):
if i % 2 != 0 and i % 3 != 0:
lst.append(i)
lst_fp = [i for i in range(1, 101) if i % 2 != 0 and i % 3 != 0]
举这种简单的例子没什么意思。总之关键在于，在循环复杂时，设计一项好的递归，来代替循环完成功能。
设计递归解决问题
以下给一个基于方阵快速幂求解斐波那契数列第n项的程序，是Haskell语言，但应该看得懂。
-- 方阵快速幂.hs
-- 暂时先只实现二阶方阵
my_product :: Num a => [[a]] -> [[a]] -> [[a]]
my_product a b = [[sum [a !! i !! k * b !! k !! j | k <- [0..1]] | j <- [0..1]] | i <- [0..1]]
{-
self_product :: Num a => [[a]] -> [[a]]
self_product a = [[sum [a !! i !! k * a !! k !! j | k <- [0..1]] | j <- [0..1]] | i <- [0..1]]
-}
-- 测速度：1e6 0.04, 1e7 0.13, 1e8 2.06, 1e9 26.24 可能内存逐渐不够用了
self_product :: Num a => [[a]] -> [[a]]
self_product = \a -> my_product a a
-- 我曾经担心这样写会慢，害怕参数a对应的函数结果被计算两次。但是并不会。
-- 无论如何，函数的参数值只确定一次，而且在引用之前。虽然Haskell的惰性求值-引值计算在这个参数值被引用的时候（而不是在一开始）才计算其值，但是也只计算一次，所以不会慢。
-- 测速度：1e6 0.02, 1e7 0.16, 1e8 1.99, 1e9 26.24 可能内存逐渐不够用了
{-
fast_exp :: (Num a, Integral int) => [[a]] -> int -> [[a]]
fast_exp _ 0 = [[1, 0], [0, 1]]
fast_exp a num = if num `mod` 2 == 0 then self_product $ fast_exp a $ halfnum
else my_product a $ self_product $ fast_exp a $ halfnum
where halfnum = floor $ fromIntegral num / 2
-}
-- 这里的halfnum主要是对类型系统做妥协。好好读，学习这个写法
-- 通过写这个函数学会了$的用法：其实就是代替括号的，用来改变求值顺序的，但$不能像()一样滥用。
-- 最好还是先想好求值顺序，再在适当的位置加$，而不是一股脑地把$当做一个分隔符。
fast_exp :: (Num a, Integral int) => [[a]] -> int -> [[a]]
fast_exp a num | num == 0 = [[1, 0], [0, 1]]
| num `mod` 2 == 0 = self_product $ fast_exp a $ halfnum
| otherwise = my_product a $ self_product $ fast_exp a $ halfnum
where halfnum = floor $ fromIntegral num / 2
-- 优化一下写法。第一行其实并不需要这样优化，主要是第二行第三行不用if了，比较清楚（并不）。
fibo :: Integral int => int -> int
fibo num = fast_exp fibo_base num !! 0 !! 0 where fibo_base = [[1, 1], [1, 0]]
-- 方阵快速幂的应用：求解斐波那契
my_zero :: Integral int => int -> int
my_zero a = if a == 0 then 0 else 1
-- 用来测速度
用列表推导式（列表解析）代替for循环
会写就行。
# 在1-100中去除2,3的倍数
lst = []
for i in range(1, 101):
if i % 2 != 0 and i % 3 != 0:
lst.append(i)
# List Comprehension
lst_fp = [i for i in range(1, 101) if i % 2 != 0 and i % 3 != 0]
[(i, j) for i in range(2) for j in range(2)] # [(0, 0), (0, 1), (1, 0), (1, 1)]
[(i, j) for i, j in zip(range(2), range(2))] # [(0, 0), (1, 1)]
思想重点：通过列表统一处理解决问题，比如子列表的递归是一个很通用的思路。
基于列表推导式，设计递归解决问题
结合列表推导式，设计递归解决问题。
典型例子：快速排序。
def quick_sort(lst):
if lst == []: return []
head, tail = lst[0], lst[1:]
return quick_sort([elem for elem in tail if elem < head]) \
+ [head]\
+ quick_sort([elem for elem in tail if elem >= head])
用与或非逻辑代替流程控制
if-else
# 一个简单的判断逻辑的实现
def foo(num):
if num == 1: return "One"
elif num == 2: return "Two"
else: return "Other"
# Functional
def foo_fp(num):
self_return = lambda s: s
return (num == 1 and "One") \
or (num == 2 and "Two") \
or "Other"
# More Functional
def foo_fp_more(num):
self_return = lambda s: s
return (num == 1 and self_return("One")) \
or (num == 2 and self_return("Two")) \
or self_return("Other")
如果条件语句是不完备的话，其实可以异或一个None，懂得都懂。
while
FP while的范式如下：
# statement-based while loop
while <cond>:
<pre-suite>
if <break_condition>: break
else: <suite>
# FP-style recursive while loop
def while_block():
<pre-suite>
if <break_condition>: return 1
else: <suite>
return 0
while_FP = lambda: (<cond> and while_block()) or while_FP()
while_FP()
while FP的精髓在于，通过函数的副作用办事情，通过函数的返回值约定行为是继续还是终止。这样做的好处是把副作用的影响限制在函数体内。
基于echo()函数举一个例子：
welcome_str = "input something (input \"q\" to exit):"
# imperative version of "echo()"
def echo_input():
while 1:
x = input(welcome_str)
if x == 'q': break
else: print(x)
echo_input()
# utility function for "identity with side-effect"
def monadic_print(x):
print(x)
return x
# FP version of "echo()"
echo_FP = lambda: monadic_print(input(welcome_str)) == 'q' or echo_FP()
echo_FP()
while FP的缺点在于，不能很好地通过函数的返回值传递值。我们举一个这种缺点的例子：
# 在1-100中去除2,3的倍数，而且只保留前10个数
lst = []
i = 1
while len(lst) < 10:
if i % 2 != 0 and i % 3 != 0:
lst.append(i)
if i >= 100: break
else: i += 1
# FP
lst_fp = []
i = 1
def while_block():
if i % 2 != 0 and i % 3 != 0:
lst.append(i)
if i >= 100: return 1
else: i += 1
return 0
while_fp = lambda: (len(lst_fp) < 10 and while_block()) or while_fp()
while_fp()
上面的FP代码体现思想，但无法正常运行。只能把lst_fp和i定义为全局可修改的，才能正常跑通。
因为while_block()和while_FP的返回值都是0/1，所以对变量值的修改只能：
通过把变量声明为全局变量而执行。（可以更好地跟上面的while FP框架对应，但不推荐。）
还是通过函数的返回值传递值，在这种情况下需要把代码写得更复杂一点。（推荐，虽然复杂，但还是纯FP的实现。）
高阶函数
高阶函数概论
高阶函数的思想就是，函数可以作为参数，函数也可以作为返回值。
高阶函数的思想在Haskell里面体现的淋漓尽致：因为万物都可以通过函数表示，所以无论任何很奇怪的东西，都用函数实现其相似的结构和功能，再将其返回。
这部分内容很基本，等有心情再补吧。
高阶函数的三种范式：map reduce filter
map reduce filter三个函数代表了FP中的三种编程模式（或者叫范式）。灵活使用这三个函数，可以完成函数式编程中很大一部分的任务。下面是这三个函数的简单实现（基于FP）：
def map(f, lst):
return [f(x) for x in lst]
# 实际上map会更复杂一些，应该允许接收多个可迭代参数，不过无所谓
def reduce(f, lst):
assert len(lst) > 1
if len(lst) == 2:
return f(lst[0], lst[1])
head, tail = lst[0], lst[1:]
return f(head, reduce(f, tail))
# 也只是对reduce的一个最基本实现
def filter(f, lst):
return [x for x in lst if f(x)]
思想要点：
·函数作为参数的思想，高阶函数的思想
· 通过列表统一处理解决问题
高阶函数的实际应用
高阶函数的最有用之处就在于，其返回的不一定是一个简单的值或结构，而可以是一些乱七八糟的东西。
此处可以举个例子：Python：用来显示函数执行时间的装饰器。
monad
monad：实际上什么都不做，只是在执行函数体过程中产生一个副作用。
monad的好处：把副作用的影响局限在函数体内，从而方便定位bug和debug。
monad风格print
用上文提到过的monadic_print()举例：
def monadic_print(x):
print(x)
return x
python中的什么东西最像Haskell中的>>=？
# Normal
lst = xx.yy()
lst.sort()
# >>+
lst = xx.yy().sort()
代码分块并用函数封装
代码分块并用函数封装：这是一种代码风格。示例如下：
# imperative version
## step1
import numpy as np
x = np.array(range(1, 5))
y = x + 2
z1 = y ** 2
z2 = np.sin(y)
## step2
import matplotlib.pyplot as plt
plt.plot(x, z1)
plt.plot(x, z2)
plt.show()
# FP
## step1
def fun1():
import numpy as np
x = np.array(range(1, 5))
y = x + 2
z1 = y ** 2
z2 = np.sin(y)
return x, z1, z2 # only these three are used later
x, z1, z2 = fun1()
## step2
def fun2():
import matplotlib.pyplot as plt
plt.plot(x, z1)
plt.plot(x, z2)
plt.show()
fun2()
好处：
·方便分段调试（直接注释掉执行的那一句话，就可以不运行这一段）
· 可以明确变量和导入的模块/包的作用域
· 方便定位错误：把明显的错误定位于某段函数体内
-防止错误的传播：对每段代码写一个sanity check来确定阶段运行结果正确
蕴含的思想要点：通过表达式求值完成任务（关注对什么进行计算），而不是一直赋值，赋来赋去（不关注怎么进行计算）。
本文内容不用于商业目的，如涉及知识产权问题，请权利人联系51Testing小编(021-64471599-8017)，我们将立即处理
