函数式编程入门

Part I: 什么是函数式编程？

• 一种编程范式
• 编程范式
  • 命令式编程 :: 面向对象，面向过程
  • 声明式编程 :: 函数式编程

几个例子

将数组中所有数平方

• 命令式 (in Python)

def foo(xs):
    for i in range(len(xs)):
    xs[i] = xs[i] ** 2
    return xs

• 函数式 (in Haskell)

foo :: [Int] -> [Int]
foo xs = map (^2) xs

线性素数筛法 \(O(nloglogn)\)

• 命令式 (in Python)

def primes(n):
    P = [True for i in range(n+1)]
    for i in range(2, n+1):
        if P[i]:
            for j in range(i*i, n+1, i):
                P[j] = False
    return [i for i in range(2, n+1) if P[i]]

• 函数式 (in Haskell)

primes :: Int -> [Int]
primes n = takeWhile (<n) (filterPrime [2..])
  where filterPrime (p:xs) =
          p : filterPrime [x | x <- xs, x `mod` p /= 0]

求出所有小于23333的奇平方数的平方和(平方数的平方和)

• 命令式 (in C++)

int bar()
{
    int ans = 0;
    int i = 0;
    while (i++) {
        if (i * i >= 23333) break;
        if (i * i % 2 == 1) ans += i * i * i * i;
    }
    return ans;
}

• 函数式 (in Haskell)

oddSquareSum = (sum . map (^2) . takeWhile (<10000) . filter odd)
                 (map (^2) [1..])

命令式编程与函数式编程的主要区别：

• 命令式编程关注的是"what"，即"做什么"，它按步骤规定程序要做的事情，并在这一过程中改变状态(计算机的内存、硬盘)；
• 声明式编程，或者更确切些，函数式编程关注的是"how"，即"怎么做"，它描述处理数据的方式(定义函数)，组合这些"方式"，来完成对数据的处理；

• 命令式编程更加贴合机器的结构
• 函数式编程更加贴合数学与人的抽象思维

举例：

• \(x = x+1\)
• \(f(x) = x+1\)

主要特征

函数是头等公民 (first-class)

1. 头等公民：像值一样被传递、返回
2. 高阶函数 (higher-order function) ：以函数作为参数，或者返回一个函数的函数。

compose :: (a -> b) -> (b -> c) -> (a -> c)
compose f g = \x -> f (g x)

flip :: (a -> b -> c) -> (b -> a -> c)
flip f = \x y -> f y x

纯函数 (pure function)

• 无任何副作用的函数
• 不依赖于状态，也不改变状态

addOne :: Int -> Int
addOne x = x + 1

x = input()
print(x)

不可变性 (immutable)

没有变量，没有赋值，只有绑定。

dic = {'a': 1, 'b': 1, 'c': 3}
dic['b'] = 2
print(dic)

(let [m {:a 1 :b 1 :c 3}]
  (println (assoc m :b 2))
  (println m))

递归 (recursion)

函数式编程的基本概念中，没有"循环"(for, while, repeat)，只有递归。

• 循环：面向机器和具体思维。
• 递归：贴近数学和抽象思维。

求n维向量点乘

循环

def dot(xs, ys):
    n = len(xs)
    prod = 0
    for i in range(n):
        prod += xs[i] * ys[i]
    return prod

递归

dot :: [Double] -> [Double] -> Double
dot [] [] = 0.0
dot (x:xs) (y:ys) = x*y + dot xs ys

借助函数式编程工具箱：

dot xs ys = sum $ zipWith (*) xs ys

Laziness

惰性求值

• 不到万不得已的时候，并不会求出表达式的值，或者更贴切些，不会对表达式进行求值(表达式带来的副作用也不会发生)
• 真正需要的时候：输出到屏幕，写入文件，或者强制求值
• 对于实现的理解：线段树

Part II: 函数式编程工具箱

函数式编程工具箱 (functional programming toolbox): 一组函数式编程中常用的函数、工具或者思维。

map

将一个函数应用到列表的每个元素上，并返回由结果组成的新列表。

Example

map (+1) [1,2,3] -- [2,3,4]
map (^2) [1,2,3] -- [1,4,9]
map (\x -> 2*x-1) [1,2,3] -- [1,3,5]

实现

map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = f x : map f xs

filter

筛选出列表中符合条件的元素。

Example

filter even [1,2,3,4,5] -- [2, 4]
filter isPrime [1,2,3,4,5,6,7,8,9] -- [2,5,7]

实现

filter :: (a -> Bool) -> [a] -> [a]
filter _ [] = []
filter p (x:xs)
     | p x = x : filter xs
     | otherwise = filter xs

fold

• 也就是 reduce
• \(MapReduce\)

Example

fold (+) 0 [1,2,3,4,5] -- 15

等价于

5 + 0 => 5
4 + 5 => 9
3 + 9 => 12
2 + 12 => 14
1 + 14 => 15

展开为表达式

(1 + (2 + (3 + (4 + (5 + 0)))))

实现

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr _ z [] = z
foldr f z (x:xs) = f x (foldr f z xs)

map, filter

• 更普适的抽象
• map

map f xs = foldr (\x acc -> f x : acc) [] xs

• filter

filter f xs = foldr (\x acc -> if f x then x : acc else acc) [] xs

函数变换

• 函数是头等公民
• compose: \((f \circ g )(x) = f(g(x))\)
• flip: 交换两个参数的位置

  (flip concat) "Hello," "world!" -- "world!hello,"

Laziness, Recursion

• Laziness: 除非万不得已，不对表达式求值
• 通往无穷，操纵无穷的道路

能返回所有正整数的函数

positives :: [Int]
positives = 1 : map (+1) positives

理论依据：

[1,2,3, ...] == 1 : [1+1, 2+1, 3+1, ...] == 1 : [2, 3, 4, ...]

不Lazy的实现

positives = () =>
    [1].concat
    (
        positives().map(x => x+1)
    )

不管在什么情况下调用，都会形成死循环！

窥见无穷

take 10 positives -- [1,2,3,4,5,6,7,8,9,10]
-- or even...
let squares = map (^2) positives
take 3 squares -- [1,4,9]

魔力之源

take 的实现

take :: Int -> [a] -> [a]
take _ [] = []
take 0 _ = []
take n (x:xs) = x : take (n-1) xs

到底发生了什么...

take 10 positives -- note: positives = 1 : map (+1) positives
== take 10 (1:map (+1) positives)
== 1 : take 9 (map (+1) positives)
== 1 : take 9 (map (+1) (1 : map (+1) positives))
== 1 : take 9 (2 : map (+2) positives)
== 1 : 2 : take 8 (map (+2) positives)
-- ...
== 1:2:3:4:5:6:7:8:9:10: take 0 (map (+10) positives)
== [1,2,3,4,5,6,7,8,9,10]

Part III: 实际应用中的优劣

很多时候函数式编程看起来像一把精巧优美却华而不实的绣花剑，的确，在实际应用之中，函数式编程有一些不足与劣势。但事实上，他也具有很多命令式编程所不具备的优点。

劣势

quickSort :: [Int] -> [Int]
quickSort [] = []
quicksort (x:xs) =
    let smaller = filter (<=x) xs
        larger = filter (>x) xs
    in quickSort smaller ++ [x] ++ quickSort larger

• 效率！效率！效率！（时间，空间）
• 伪函数式编程：用函数式语言进行指令式编程

优势

• 不可变 :: 安全性，一致性
• 纯函数 :: 便于调试
• 事实上是一种更先进，更有编码效率的编程范式

如果使用Lisp语言，能让程序变得多短？以Lisp和C的比较为例，我听到的大多数说法是 C代码的长度是Lisp的7倍到10倍 。但是最近，New Architect杂志上有一篇介绍ITA软件公司的文章，里面说" 一行Lisp代码相当于20行C代码 "，因为此文都是引用ITA总裁的话，所以我想这个数字来自ITA的编程实践。 如果真是这样，那么我们可以相信这句话。ITA的软件，不仅使用Lisp语言，还同时大量使用C和C++，所以这是他们的经验谈。

Part IV: One Step Further

• 相较于命令式编程，函数式编程更加贴近于数学，更为“抽象”。
• 背后的数学理论。

1. Lambda Calculus & Y-Combinator

几个例子

所以，他到底是什么？

答案：一种计算模型。

什么是计算模型？

• 图灵机
• 一个用于计算的数学模型
• 定义一组符号，一组规则

不那么严谨的定义

合法的Lambda表达式

1. Variable: \(x\)
2. Lambda Abstraction: \(\lambda \ x. x\)
3. Lambda Application: \((\lambda \ x. x) \ y\)

演算规则

1. \(\alpha\) 替换: \(\lambda \ x.3x+1 \rightarrow \lambda \ y . 3y+1\)
2. \(\beta\) 规约: \((\lambda \ x.3x+1) \ \pi \rightarrow 3 \pi + 1\)

柯里化

• Lambda演算中的函数永远只接收一个参数
• 多参数函数的实现通过柯里化实现

举个例子：

(a, b) => a + b

利用柯里化可以写成

a => (b => a + b)

Y Combinator

• 怎样在 \(\lambda\)-calculus 中实现递归？
• Y组合子: 生成递归函数的魔术棒

Y组合子的形式

递归？不动点？

Y组合子事实上求出了函数的不动点:

不动点和递归有什么关系？

构造辅助函数

metaFact fact n = if n == 0 then 1 else n * fact (n-1)

• fact 是一个未知量(\(x\))：我们要求解的递归函数
• metaFact fact \(=\) fact !!
• \(f(x) = x\) 不动点

小结

1. metaFact 的不动点即为我们想要的递归函数 fact
2. Y组合子能求出函数的不动点
3. Y + 辅助函数 = 递归!

2. 类型系统

1. 类型系统的背后是类型论
2. 编程语言中的类型检查、推导和运算体系
3. 目的：减少bug
4. 函数式语言 \(\neq\) 弱类型语言

3. Monad

“一个单子（Monad）说白了不过就是自函子范畴上的一个幺半群而已。”

“A monad is just a monoid in the category of endofunctors, what's the problem?”

by James Iry in Brief, Incomplete and Mostly Wrong History of Programming Languages

Monad到底是什么？

1. 本质：源于范畴论
2. 实际应用：与数学理论关系不大

“运算描述”

• “纯”与“不纯”
• 实际应用需要“状态”
• 描述运算而不是执行运算

main :: IO ()
main = do
    putStrLn "What is your name?"
    name <- getLine
    putStrLn "Hello, " ++ name

4. Haskell中的理论体现

Haskell的故事

1. 由一群计算机理论博士设计
2. 一个玩具，一个试验场

Lambda Calculus & Currying

add :: Int -> Int -> Int
add x y = x + y

addOne :: Int -> Int
addOne = add 1

addOne y = 1 + y

add :: Int -> (Int -> Int)

Type System

Haskell具有完备且强大的类型系统。

例子：代数数据类型

自定义列表

data List a = EmptyList | Cons a (List a)

自定义二叉树

data Tree a = EmptyTree | Node a (Tree a) (Tree a)

Monad

谢谢大家！