# 函数式编程（Functional Programming）简介

In computer science, functional programming is a programming paradigm—a style of building the structure and elements of computer programs—that treats computation as the evaluation of mathematical functions and avoids changing-state and mutable data.

What is the essence of functional programming: is it equational reasoning(no side effect) or is it higher-order functions? There is no clear agreement about the answer to this question.

## 程序的状态

sum = 0
for i in range(1,11):
sum += i


┌────────────┐ │ ┌────────────┐
│ assignment │ │ │  function  │
└────────────┘ │ └────────────┘
│
a = a + 1;   │   return a+1;
│


(define (addup n)
(if (= n 1)
1
(+ n (addup (- n 1))))


(define (addup2 n sum)
(if (= n 1)
(+ sum 1)
(addup2 (- n 1) (+ n sum))))



## 函数式编程的本质

1. 高阶函数（higher-order functions）
2. 没有副作用（no side effect）

### 高阶函数（higher-order functions）

Functions that operate on other functions (accept them as arguments or return value) are called higher order functions.

Python就具有高阶函数的性质，比如

def twice(function, x):
return function(function(x))

def f(x):
return x + 3

print(twice(f, 7)) # 13


How, and when, do you use higher order functions? Well, I’m glad you asked. You write your program as a big monolithic blob of code without worrying about class hierarchies. When you see that a particular piece of code is repeated, you break it out into a function (fortunately they still teach this in schools). If you see that a piece of logic within your function needs to behave differently in different situations, you break it out into a higher order function.

l = [1,2,3]
map(lambda x: 2*x, l) # => [2, 4, 6]


A programming language is said to have first-class functions if it treats functions as first-class citizens. Specifically, this means the language supports passing functions as arguments to other functions, returning them as the values from other functions, and assigning them to variables or storing them in data structures.

## # 没有副作用（side effect）

In a pure functional programming language, the following are prohibited:

1. Assignments to variables(except as initialisations)
2. Assignments to fields of heap-allocated records
3. Calls to external functions that have visible effects: print, flush, gutter, exit

int x = 1;

void func_a() {
x++;
}

void func_b() {
x = x * 2;
}

// the order of execution is fixed, otherwise the result won’t be guaranteed.
func_a();
func_b();


## 函数式编程的其它特性

### Effective Data Structures

zs = xs ++ ys


Clojure语言全部的数据结构就都是immutable的，而且还保持了非常高效的新建和复制操作。

### Domain Specific Languages(DSL)

DSL是针对某个特定领域或特定问题而创建的语言，它的一个指令可能是别的通用的编程语言的几十句甚至更多。使用DSL来解决特定问题可以大大地提升效率和减少犯错的机会。 DSL更是Lisp语言的“秘密武器”——Beating the Averages by Paul Graham 一些常见的DSL比如：

• Makefiles, as well as it’s newer generation counterparts Ant, Rake, etc.
• HTML, Postscript, PDF, TeX

Lisp是最早的函数式编程语言，又叫做LISt Processing，即寓意是一种专门对列表（list）进行处理的语言。 list虽然字面上是线性的列表，但其实是tree的结构，因为它是可以嵌套的，即list中还可以有list。 tree是一种非常强大的结构，各种各样的代码到最后都是用抽象语法树（abstract syntax tree）来表示的。

list既是Lisp代码的基本结构，又可以作为一种表示数据的基本结构（这里可以联想到XML语言来帮助理解——把XML的尖括号替换成括号，去掉全部的属性值，就是用Lisp来表示数据的雏型了）。 这其实与函数式编程没有什么关系了，只是与Lisp的语言设计相关，但Lisp作为函数式编程的代表语言，所以它的特性也一直伴随着函数式编程被大众所认识。

1. 设计新的DSL语法
2. 是沿用该种语言的代码来描述DSL，也就是使用这个语言的类库，比如用网络库来解决网络通信问题。

### Closure

function startAt(x)
function incrementBy(y)
return x + y
return incrementBy

variable closure1 = startAt(1)
variable closure2 = startAt(5)
closure1(3) // => 4
closure2(3) // => 8