谈谈函数式编程

[AlexiaChen]

---

title: 谈谈函数式编程
date: 2016-09-05 15:38:56
tags:
- 函数式编程
- lambda演算
- Y组合子

什么是函数式编程

其实有关于函数式编程我有在之前的博文《编程语言为何如此众多》提到过，有兴趣的可以去看看 :)

那么到底什么是函数式呢？听上去好厉害，好高大上的样子。

大家都知道面向对象编程提到的几个特性：封装，继承，多态，一切皆对象。那么其实函数式编程也有它固有的几个特点：不可变量，惰性求值，高阶函数，无副作用，一切皆函数。

从停机问题开始

调程序的时候经常会遇到死循环的Bug，聪明的你有没有想过发明一个自动检查程序里面有没有死循环的工具呢？不管你有没有过这种想法，反正我有过，可惜答案是，没有！

停机问题在wiki上的描述比较学术，又是什么图灵机，又是数学中的集合。因为涉及到计算理论的东西，为了防止小白看不懂，下面用一个小白话来讲，

停机问题：给定任意一个程序及其输入，判断该程序是否能够在有限次计算以内结束。

假设存在停机算法

如果存在停机算法，那么对于给定任意一个函数以及这个函数的输入,停机算法就能告诉你这个函数会不会结束。

function isHalting(func,input){
    return if_func_will_halt_on_input;
}

利用停机判定

设一个函数，并调用它自身:

function foo(func){
    if(isHalting(func,func)){
        while(true);
    }
}

// 判定自身
foo(foo);

这是一个悖论：当函数foo以foo为输入时，到底停机还是不停机？

lambda演算语法

停机问题只是个引子，接下来让我们步入正题。

用形式化的表述，λ演算的语法只有三条：

• <表达式> ::= <标识符>
• <表达式> ::= λ <标识符+> . <表达式>
• <表达式> ::= (<表达式> <表达式>)

例如，根据以上语法，可以写一个加法函数。注意，这个函数是匿名的:

λ x y. x + y

之前定义的3条语法，前二条是用于产生函数，第三条用于函数调用。

; 输出5 
((λx y. x + y) 2 3) 

;为了方便，把匿名函数绑定到一个变量
let add = λ x y. x + y
;输出5
(add 2 3) 

看到这里，其实知道Lisp语言的同学可能就有种似曾相识的感觉了。Lisp语言就是一种函数式编程语言，函数式编程语言就是基于lambda演算发展起来的。细心的人已经发觉，lambda演算与图灵机模型对比，它其实更加侧重于计算的描述，甚至表达式不需要关心函数名，它仅仅是个描述计算过程的计算体。所谓的lambda表达式就是这种计算体的一种叫法，只是在各种编程语言环境下，lambda表达式换了个语法而已。

lambda演算公理

以下是lambda演算的公理系统:

置换公理

• λ x y. x + y => λ a b. a + b

代入公理

• (λx y. x + y) a b => a + b

函数生成器

lambda演算相当于一个函数生成器:

let mul = λx y. x*y
let con = λx y. xy

; 代入

mul 3 5  -­‐> 3 * 5 
con 'fu' 'ck' -->  'fuck'

定义IF函数

大家都知道在函数式编程里，一切皆函数，就连什么平时接触到的for，if等语句都不例外。那么在函数式编程里面如何构造一个IF函数呢？

;第一个参数condition为if函数的判断条件，如为真，则执行true_value,反之，false_value

let if = λ condition true_value false_value .
         (condition and true_value) or (not condition and false_value)


;调用if,输出15

if true (mul 3 5) (add 2 3)

=> (true and (mul 3 5)) or (not true and (add 2 3))
=> (mul 3 5) or false 
=> (mul 3 5)
=> 15

;调用if,输出5

if false (mul 3 5) (add 2 3)

=> (false and (mul 3 5)) or (not false and (add 2 3))
=> false or (add 2 3) 
=> (add 2 3)
=> 5
         

递归

来个有意思点的计算，定义一个计算n的阶乘的函数:

let fact = λ n .
          if (n == 0) 1 
                     (mul (n 
                          (fact n - 1)))

问题出现了，我们在定义fact的时候引用的自身（废话，递归不调用自身还叫递归？）。虽然在实际的编译器处理过程中，编译器都可以识别这种定义，但是这不符合严谨的数学公理体系。

如何表达递归

之前的fact函数不是无法引用自身吗？那么我们把“自身”参数化，那么函数内部就可以引用了。

let P = λ self n .
        if ( n == 0) 1 (mul 
                        (n
                         (self n - 1))

然后，再令:

let fact n = P (P n)

; 然后调用,输出24
fact 4
-> P (P 4)
-> if (4 == 0) 1 (mul 4 (P (P n-1)))
-> (mul 4 (P (P 3)))
-> 4 * P (P 3)
-> 4 * 3 * P (P 2)
-> 4 * 3 * 2 * P (P 1)
-> 4 * 3 * 2 * 1
-> 24

可惜，以上还不是真正的递归,只是每次额外多传入了一个参数，反复调用而已。我们的目的是要一个真正的递归函数,但是lambda演算没有这样一个公理可以在定义函数的时候引用自身，怎么办？

Y组合子与不动点

不管之前的说法，我们就认定真正的fact是存在的:

;之前的函数P，为了方便，乘法表示就不用自定义的函数mul了
let P = λ self n .
        if ( n == 0) 1 ( n * self (n - 1))
                         
; 函数P接收2个参数，但是我们可以让函数柯里化(Currying),有时候又称部分求值(Partial Evaluation)
; P接收一个fact，本质上又产生了一个新的单参函数

P (fact) -> λ n .
        if ( n == 0) 1 ( n * fact (n - 1))

注: 函数柯里化本质的意义是把一个多参的函数转换成单参函数作为返回值的形式,这样方便优化，有兴趣可以看知乎的讨论，柯里化对函数式编程有何意义？, 如何理解functional programming里的currying与partial application?

然后，神奇的事发生了,细心的人发现，函数 P (fact) 与之前定义的函数fact相等，

• P (fact) = fact

我们发现了函数P的一个不动点,什么是不动点呢？就是一个点（广义上的）在一个函数的映射下,函数的值仍然为这个点: f(x) = x 。所以，思路就是找到不动点，如果找到了不动点，就可以把“伪递归”函数P转化为真正的递归函数了。

所以，我们假设需要一个函数Y，它可以找到这个伪递归函数的不动点，即：

• Y(F) = f = F(Y(F))

其中F(f) = f, 那么就有

• Y(P) = fact

只要有了Y，就可以把伪递归函数变换成真递归函数了。

构造Y组合子

一起来一睹Y组合子的尊容吧:

• let Y = λ F. G(G)
• 其中G = λ self. F(self(self))

验证一下

Y(P)
= G(G) , 其中G = λ self. P(self(self))
= P(G(G))
= λ n. if (n==0) 1 (n * G(G) n - 1)
假设 Y(P) = fact, 那么
Y(P) = fact = λ n. if (n==0) 1 (n * fact n-1)

这就是我们梦寐以求的真正的递归函数!

所以，当我们想定义递归函数的时候，只需要增加一个self参数，按伪递归的方法定义，然后再用Y组合子一套用，就变成我们想要的真递归了。

图灵等价

以上已经成功地推导出了Y组合子，就相当于在λ演算公理体系中推导出了一条定理：

• 可以在定义函数的过程中引用自身

这条定理是证明λ演算与图灵机等价的一个重要步骤。

那么这两个不同的计算模型等价意为着什么呢？

意味着它的计算能力与我们现实生活中的物理计算机的计算能力是一致的，图灵机的工作模型更接近于物理上的机器，冯诺依曼架构就是图灵机的物理实现。换句话说，也就是说，我们写的任何程序都能用λ演算来描述，同时λ演算描述的函数一定可以由计算机计算。

停机问题的等价问题

回想之前的停机问题，即不可判定一个图灵机在给定任意输入的时候是否可以停机。

这个命题在λ演算中的等价命题是：

不存在一个算法能判定任何两个λ函数是否等价，即对于所有的n，有f(n)=g(n)

现实世界中的函数式编程

之前都是在分析λ演算的理论，是数学化的思维，下面就请看基于λ演算发展出来的函数式语言是什么样子？ 用工程化的思维来看看现实世界的函数式编程。

Haskell

Haskell是一种纯函数式编程语言，它追求的是最纯粹的函数式，名字是为了纪念Haskell Curry而命名的。之前提到的Y组合子就是这位老哥发现的，此外他还提出了函数柯里化(Currying)，即部分求值。

Haskell中的一切都是函数，甚至没有命令式编程（面向过程或面向对象）中变量的概念。它的变量全部都是只允许一次赋值，然后不可改变，就像数学推导中对变量的赋值一样。

Haskell还没有一般意义上的控制流，如for循环等，取而代之的是递归。

Haskell还有两个重要的特性，即无副作用和惰性求值。

无副作用指的是任何函数在给定同样输入的情况下每次调用的结果都一样，跟数学中的函数是一样的。而惰性求值指的是函数除非需要，否则不会立即计算。

第一个Haskell程序

let max a b = if a>b then a else b


max 3 4   -- print 4

max 1.001 1 -- print 1.001

max "MathxH" "ChenAlex1233"  -- print "ChenAlex1233"

列表

Haskell中的列表定义是这样的：

• list X :: = [] || elem : (list X)
  即：

• 空列表 = []

• [1] = 1:[]

• [1,2,3] = 1:2:3:[]

输入2:1:3:7:8:[] 可以看到
[2,1,3,7,8]

模式匹配

定义：

• let first (elem:rest) = elem

输入first [1,3] 可以看到结果是1。
elem:rest 是Haskell的函数参数模式匹配。
对于列表[1,3],实质上是1:3:[], elem匹配了1，rest匹配了3:[]， 也就是[3]。

列表求和

accumulate [] = 0
accumulate (elem:rest) = elem + accumulate rest
main = print (accumulate [1,2,3]) -- print 6

判断回文

palindrome [] = True
palindrome [_] = True
palindrome (elem:rest) = (elem == last rest) && (palindrome(init rest)) -- init:返回一个列表中除了最后一个元素的其他元素

palindrome [1,2,3,2,1] -- print True
palindrome [1,1,2]   -- print False
palindrome "madam"  -- print True

删除连续重复元素

cut cond [] = []
cut cond (elem:rest) = if cond elem then 
                         cut cond rest else
                         elem:rest
compress [] = []
compress (elem:rest) = elem : compress (cut (== elem) rest)

compress [1,2,2,2,3,3]  -- print [1,2,3]
compress "aaabbaccc"  -- print "abac"

下面来点华丽的推导过程：

compress [1,2,2,2,3,3]
=> 1 : compress (cut (== 1) [2,2,2,3,3])
=> 1 : compress (if (== 1) 2 then cut (== 1) [2,2,3,3] else [2,2,2,3,3])
=> 1 : compress [2,2,2,3,3]
=> 1 : 2 : compress (cut (== 2) [2,2,3,3])
=> 1 : 2 : compress (if (== 2) 2 then cut (== 2) [2,3,3] else [2,2,3,3])
=> 1 : 2 : compress (cut (== 2) [2,3,3])
=> 1 : 2 : compress (if (== 2) 2 then cut (== 2) [3,3] else [2,3,3])
=> 1 : 2 : compress (cut (== 2) [3,3])
=> 1 : 2 : compress (if (== 2) 3 then cut (== 2) [3] else [3,3])
=> 1 : 2 : compress [3,3]
=> 1 : 2 : 3 : compress (cut (== 3) [3])
=> 1 : 2 : 3 : compress (if (== 3) 3 then cut (== 3) [] else [3])
=> 1 : 2 : 3 : compress (cut (== 3) [])
=> 1 : 2 : 3 : compress []
=> 1 : 2 : 3 : []
=> [1,2,3]

惰性求值

Haskell中可以定义无穷列表，例如：

• [1..]表示所有的正整数
• [1,3..]表示所有的奇数

这在大多数编程语言中都是不可思议的，因为大多数语言都是及早求值(early evaluation)，Haskell的惰性求值(lazy evaluation)特性可以让列表按需取用。

例如[1,3..] !! 42 可以返回结果85

斐波那契数列

如何用Haskell实现斐波那契数列呢？最符合数学化的描述方法是:

fib 0 = 1
fib 1 = 1
fib a = fib (a - 1) + fib (a - 2)

不巧的是，这个算法是O(2^N)的，因为Haskell编译器还没有聪明到可以实现递归记忆化。

斐波那契数列的线性算法

让我们利用无穷列表来实现线性算法！ 一行代码就可以了：

• fib = 1:1:zipWith (+) fib (tail fib)

fib !! 4是5， fib !! 42 是433494437
fib !! 1000输出：
7033036771142281582183525487718354977018
1269836358732742604905087154537118196933
5797422494945626117334877504492417659910
8818636326545022364710601205337412127386
7339111198139373125598767690091902245245
323403501

解释下以上代码:

tail返回列表除了第一项以外的后面内容，例如 tail [1..] 返回 [2..]

zipWith是将两个列表的每个元素通过一个函数非别计算，并返回结果的列表，例如：

• zipWith (*) [2,3,5] [1,2,3] 返回[2,6,15]

于是乎，fib = 1:1:zipWith (+) fib (tail fib) 生成了一个无穷列表，前面两个元素都是1，后面的元素由现有列表错位相加而成，即:

[1,  1,  2,  3,  5,  8,  13,  21…]   //fib    

+ [1, 2, 3, 5, 8, 13, 21, 34…] //tail fib
= [2, 3, 5, 8, 13, 21, 34, 55…]

由于惰性求值，列表不会被立即计算，只有当我们用到其中元素的时候才会算。

快速排序

qsort (elem:rest) = (qsort lesser) ++ [elem] ++ (qsort greater)
   where
    lesser = filter (< elem) rest
    greater = filter (>= elem) rest

++ 用于列表连接
filter返回列表中满足条件的元素组成的列表

二叉树并表示

data Tree a = Empty | Node a (Tree a) (Tree a)
tree = Node 'd'
    (Node 'b'
       (Node 'a' Empty Empty)
       (Node 'c' Empty Empty)
    )
    (Node 'e'
      Empty
      (Node 'g'
        (Node 'f' Empty Empty)
        Empty
      )
    )

以上代码构建了一个二叉树，是这样的:

       d
      / \
     b   e
    / \   \
   a   c   g
          /
         f

下面对这个二叉树进行中序遍历:

inorder  Empty  =  [] 
inorder  (Node  value  left  right)  = 
inorder  left  ++  [value]  ++  inorder  right 

inorder tree  -- print "abcdefg"

然后求树的高度:

height  Empty  =  0 
height  (Node  value  left  right)  =  
max  (height  left)  (height  right)  +  1 

height tree -- print 4

高阶函数

高阶函数的参数是函数，通过部分求值可以返回函数。

traverse  func  zero  Empty  =  zero 
traverse  func  zero  (Node  value  left  right)  = 
func  value  
(traverse  func  zero  left)  
(traverse  func  zero  right) 
height_func  _  a  b  =  max  a  b  +  1 

traverse  height_func  0  tree  -- print 4

中序遍历函数：

inorder_func value left right = left ++
[value] ++ right

通过部分求值产生低阶函数：

inorder = traverse inorder_func []

inorder tree -- print "abcdefg"

闭包

function  make_closure()  { 
  var  inner_varible  =  0; 
  return  function  ()  { 
    return  inner_varible++; 
  } 
} 
var  counter  =  make_closure(); 
counter();  //  0 
counter();  //  1

用闭包实现柯里化

多数编程语言无法部分求值，原因是柯里化与参数表机制冲突。但可以用闭包实现。但是Java，C++ 11等主流编程语言对于闭包的支持就是半残。下面用js来表达吧。

function pow(x, y){
    return x ^ y;
}


// 对pow函数部分求值
function  pow5(x)  { 
  return  pow(x,  5); 
} 
pow5(2);  //输出  32

上面的代码实质上是:

function  pow5(x)  { 
  return  function (x, 5){
    return x ^ 5;
};  
} 

EOF