A pratical introduction to FP

原文:https://maryrosecook.com/blog/post/a-practical-introduction-to-functional-programming

什么是函数式编程的指导性原则

不是下面这些函数式编程的语言特征

  • immutable data
  • first class function
  • tail call optimization

不是下面这些函数式的变成技巧

  • mapping
  • reducing
  • pipelining
  • recursing
  • currying
  • high order function

不是下面这些函数式语言带来的优势

  • parallelization
  • lazy evalution
  • determinism

只有一种东西可以表达函数式编程的核心特征:absence of side effects。函数式编程不依赖于当前函数的外部的数据,而且也不改变当前函数的外部数据

unfunctional function:

a = 0
def increment():
global a
a += 1

functional function:

def increment(a):
return a + 1

几个要注意的简单的原则:

  • Don’t iterate over lists. Use map and reduce.
  • Write declaratively, not imperatively
  • Use pipelines

对waterflow问题的数学描述和函数编程解决方案

原文: http://philipnilsson.github.io/Badness10k/posts/2013-10-11-functional-waterflow.html

waterflow 问题

假设如下图(1),我们在不同的x轴的每一个点都有一个不同的y轴高度。

图1

该图可以用一个数组表示,然后数组里的每一个值表示的Y的高度,而数组的序列号(index)则表示为图中
的X轴。

比如上图可以用数组表示为: [2,5,1,2,3,4,7,7,6]

现在假设从上面(Y轴)向下下雨(如图2),而且雨从来也不用考虑会停,那么上图在不同高度的Y轴之间最
多可以收集多少雨水?

图2

另外,我们假设1升为(X轴的单位)X(Y轴的单位),即1x1为1升。现在如图2中,最左边的因为没有东西
挡住,所以雨水会洒出,最右边的也是一样。

数学描述与答案

请去上面的原文里查看。另外该作者也有另外几篇关于函数式编程的文章,也非常不错,放在附录里了。

附录

最后

最近迷上了函数式编程(functional programming),不知道为什么?!

Python functional programming aspect

名词解释

  • TCO (Tail Call Optimization): 尾调优化
  • CPS (Continuous Passing Style): 续传样式

TCO 库

  • tail call optimization
  • optimized tail recursion
  • continuation passing style
  • pseudo call-with-current-continuation

tco库的主要动机:

重复的调用function的时候,并不会增加执行栈(execution stack)的大小,并且在函数式编程中可以随时从一个执行栈的某一部分跳转到另外一部分之前的代码,同时并不需要穿越中间的函数调用和return。

第一个实例,二叉搜索树

假定我们有一个二叉树,现在我们需要在这个二叉树上搜索制定的节点(node)。

使用尾递归(tail recursion)

from itertools import groupby
from random import sample

nbrlevels = 16
n = 2 ** nbrlevels - 1
t = sample(range(2 * n), n)
t.sort()

def make_tree(l):
if len(l) == 1:
return [l[0], [], []]

return [l[0], make_tree(l[1:len(l)//2+1]), make_tree(l[len(l)//2+1:])]

tree = make_tree(t)

如果使用tco,则:

  • 递归调用自己,且不重载(overloading stack)
  • 在递归的内部不退出递归的情况下调用其他的函数

待续—

参考:
1) http://baruchel.github.io/python/2015/11/07/explaining-functional-aspects-in-python/
2) https://github.com/baruchel/tco
3) https://en.wikipedia.org/wiki/Continuation-passing_style
4) https://blogs.msdn.microsoft.com/ericlippert/2010/10/21/continuation-passing-style-revisited-part-one/
5) https://www.zhihu.com/question/24453254
6) http://blog.pengyifan.com/articles/functional-programming-for-the-rest-of-us/
7) http://blog.csdn.net/hikaliv/article/details/4548561
8) https://segmentfault.com/n/1330000005012969
9) http://baruchel.github.io/python/2015/07/10/continuation-passing-style-in-python/
10) https://github.com/baruchel/tco