# 函数式编程与面向对象编程[1]: Lambda表达式 函数柯里化 高阶函数.md

2016.5.2 11:19:09

## 什么是lambda表达式

### 例子

For example, in Lisp the 'square' function can be expressed as a lambda expression as follows:

(lambda (x) (* x x))

### 定义

“Lambda 表达式”(lambda expression)是一个匿名函数，Lambda表达式基于数学中的λ演算得名，直接对应于其中的lambda抽象(lambda abstraction)，是一个匿名函数，即没有函数名的函数。Lambda表达式可以表示闭包（注意和数学传统意义上的不同）。

Lambda calculus (also written as λ-calculus) is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution. It was first introduced by mathematician Alonzo Church in the 1930s as part of an investigation into the foundations of mathematics. Lambda calculus is a universal model of computation equivalent to a Turing machine (Church-Turing thesis, 1937). Its namesake, Greek letter lambda (λ), is used in lambda terms (also called lambda expressions) to denote binding a variable in a function.

Lambda calculus may be typed and untyped. In typed lambda calculus functions can be applied only if they are capable of accepting the given input's "type" of data.

Lambda calculus has applications in many different areas in mathematics, philosophy,linguistics, and computer science. Lambda calculus has played an important role in the development of the theory of programming languages. Functional programming languages implement the lambda calculus. Lambda calculus also is a current research topic in Category theory.

## λ演算(λ-calculus)

Lambda演算和函数式语言的计算模型天生较为接近，Lambda表达式一般是这些语言必备的基本特性。如：

Scheme:

(lambda(x)(+x1))

\x->x+1

λ演算是一套用于研究函数定义、函数应用和递归的形式系统。函数的作用 (application) 是左结合的：

f x y = (f x) y

$$f(x,y)=x2+y2$$

#### 匿名函数表达

$$(x,y) \rightarrow x^2 + y^2$$

#### 柯里化表达

$$x \rightarrow (y \rightarrow x^2 + y^2 )$$

#### lambda演算的历史

λ演算由 Alonzo Church 和 Stephen Cole Kleene 在 20 世纪三十年代引入，Church 运用 lambda 演算在 1936 年给出 判定性问题 (Entscheidungsproblem) 的一个否定的答案。这种演算可以用来清晰地定义什么是一个可计算函数。关于两个 lambda 演算表达式是否等价的命题无法通过一个通用的算法来解决，这是不可判定性能够证明的头一个问题，甚至还在停机问题之先。Lambda 演算对函数式编程有巨大的影响，特别是Lisp 语言。

### Church 整数

$$0 = \lambda f\cdot \lambda x\cdot x$$ $$1 = \lambda f\cdot \lambda x\cdot f x$$ $$2 = \lambda f\cdot \lambda x\cdot f (f x )$$ $$3 = \lambda f\cdot \lambda x\cdot f(f (f x ))$$ $$...$$ $$n = \lambda f\cdot \lambda x\cdot f^n( x )$$

 以单一参数函数 f 为参数，返回另一个单一参数的函数。

(注意在 Church 原来的 lambda 演算中，lambda 表达式的形式参数在函数体中至少出现一次，这使得我们无法像上面那样定义 0)

### C#Lambda表达式

C#的Lambda 表达式都使用 Lambda 运算符 =>，该运算符读为“goes to”。语法如下：

形参列表=>函数体
(input parameters) => expression
(input parameters) => {statement;}

() => Console.Write("0个参数")
I => Console.Write("1个参数时参数列中可省略括号，值为：{0}",i)
(x,y) => Console.Write("包含2个参数，值为：{0}*{1}",x,y)

//两条语句时必须要大括号
I => { i++;Console.Write("两条语句的情况"); }

Lambda 表达式是一种可用于创建委托或表达式目录树类型的匿名函数。 通过使用 lambda 表达式，可以写入可作为参数传递或作为函数调用值返回的本地函数。 Lambda 表达式对于编写 LINQ 查询表达式特别有用。

List<User> users = new List<User>();
Func<User, bool> predicate = ((user) =>
{
return user.UserId > 100;
}
);
List<User> temps = users.Where(predicate).ToList();

### Java Lambda表达式

Java 8的一个大亮点是引入Lambda表达式，使用它设计的代码会更加简洁。当开发者在编写Lambda表达式时，也会随之被编译成一个函数式接口。下面这个例子就是使用Lambda语法来代替匿名的内部类，代码不仅简洁，而且还可读。 没有使用Lambda的老方法：

Runnable r = new Runnable(){
@Override
public void run(){
System.out.println("Running without Lambda");
}
};

Runnable r =() -> {
System.out.println("Running without Lambda");
};

### C++ Lambda表达式

ISO C++ 11 标准的一大亮点是引入Lambda表达式。基本语法如下：

[capture list] (parameter list) ->return type { function body }

## scala的匿名函数

scala的匿名函数使用非常的广泛，这也是函数式语言的标志之一。

scala中的集合类List有一个map方法，该方法接收一个函数作为参数，对List中的每一个元素使用参数指定的方法，此处非常适合用匿名函数，请看下面代码：

val l=List(1,2,3)
l.map(i=>i+9)

i=>i+9中的=>是参数列表和返回值的分隔符，如果少于两个参数可以不写小括号，后面部分是函数的返回值。如果函数体包含多行代码可以使用花括号，例如：

l.map((i)=>{
println("HI");
i+9
})

### scala函数特有特性之调配curried

def add (i:Int,j:Int):Int=i+j

// 多参数的写法
def multiply(x: Int, y: Int) = x * y

Moses Schnfinkel 和 Gottlob Frege 发明了如下的表达方式:

def multiply(x: Int)(y: Int) => x * y

// 柯里化的写法
def multiply(x: Int)(y: Int) = x * y

// 计算两个数的乘积
multiply(6)(7)

multiply(6)返回的是函数(y: Int)=>6*y，再将这个函数应用到7

(6 * y ) (7) = 42

curried不太好理解，enjoy it!函数柯里化的主要功能是提供了强大的动态函数创建方法，通过调用另一个函数并为它传入要柯里化（currying）的函数和必要的参数而得到。通俗点说就是利用已有的函数，再创建一个动态的函数，该动态函数内部还是通过已有的函数来发生作用.

Function.prototype.bind = function(context) {
var _this = this,
_args = Array.prototype.slice.call(arguments, 1);
return function() {
return _this.apply(context, _args.concat(Array.prototype.slice.call(arguments)))
}
}

rotate = (\x -> (\y -> (y, -x)))

rotate = (\(x, y) -> (y, -x))

• 一来，二维向量的两个坐标通常是成对出现的，很少会有“部分应用”的需要，所以也就自然用不到科里化的任何好处；
• 二来，当你需要把一个向量rotate两次的时候，科里化版本就会体现出异常的麻烦了。

    如果某些参数在大部分情况下，总是需要同时给出，才具有真实的意义，那么应该把这些参数组合成一个组合型参数来处理，而不应该科里化。
如果要定义的多参函数是一个闭合函数，那么它是很可能需要被多次应用的，这种情况下，应该用组合型参数的方式来处理。
如果先指定某一些参数就有明确的意义，那么就应该用科里化的方式来处理。

currying和partial application会affect performance吗？

### 匿名函数

(x: Double) => 3 * x  // 该匿名函数将传给它的参数乘3

## 高阶函数(Higher-order function)

### 变量可以指向函数

abs(-10)
10

abs
<built-in function abs>

 x = abs(-10)
x
10

f = abs
f
<built-in function abs>

f = abs
f(-10)
10

### 高阶函数

def add(x, y, f):
return f(x) + f(y)

x ==> -5
y ==> 6
f ==> abs
f(x) + f(y) ==> abs(-5) + abs(6) ==> 11

add(-5, 6, abs)
11

<script type="text/javascript" src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=default"></script>

684 篇文章47 人订阅

0 条评论

## 相关文章

### 从yield关键字看IEnumerable和Collection的区别

C#的yield关键字由来以久，如果我没有记错的话，应该是在C# 2.0中被引入的。相信大家此关键字的用法已经了然于胸，很多人也了解yield背后的“延迟赋值”...

2247

### C#基础知识系列一（goto、i++、三元运算符、ref和out、String和string、重载运算符）

这两天在网上看到的总结很多，尤其是博客园中的，很多很多，也给了我很多的启发，当然自己也总结过，而且有很多人也给与我一些意见和看法。不管怎样，自己还是先把所谓...

1262

### ST算法

RMQ（Range Minimum/Maximum Query），即区间最值查询。对于长度为n的数列arr，回答若干询问Q(i,j)，返回数列arr中下标在i...

2262

723

### 1798: [Ahoi2009]Seq 维护序列seq

1798: [Ahoi2009]Seq 维护序列seq Time Limit: 30 Sec  Memory Limit: 64 MB Submit: 2930...

3065

3369

### R中字段抽取、字段合并、字段匹配

1、字段抽取 字段抽取，是根据已知列数据的开始和结束位置，抽取出新的列 字段截取函数：substr(x,start,stop) tel <- '1892225...

8879

### leetcode-179-Largest Number（理解规则，自定义cmp函数进行排序）

1、这道题给定一个vector，里面存放着int类型的非负整数，要求把这些非负整数拼起来，尽可能拼成一个最大的整数。

1933

### Leetcode Regular Expression Matching

Given an input string (s) and a pattern (p), implement regular expression matchi...

942

### Javascript基础回顾 之(一) 类型

本来是要继续由浅入深表达式系列最后一篇的，但是最近团队突然就忙起来了，从来没有过的忙！不过喜欢表达式的朋友请放心，已经在写了:) 在工作当中发现大家对Jav...

3797