函数式编程 FUNCTIONAL PROGRAMMING byvoid@byvoid.com
什么是函数式编程?
真相是
从停机问题开始 Bug
假设有停机判定算法 function halting(func, input) { } return if_func_will_halt_on_input;
充分利用停机判定 function ni_ma(func) { if (halting(func, func)) { for(;;) // } } ni_ma(ni_ma)
尼玛, 悖论! ni_ma ni_ma
LAMBDA 演算语法 < > ::= < > < > ::= < + >. < > < > ::= (< > < >) x y. x + y
LAMBDA 演算语法 (( x y. x + y) 2 3) let add = x y. x + y (add 2 3)
LAMBDA 演算公理 x y. x + y => a b. a + b ( x y. x + y) a b => a + b
函数生成器 let mul = x y. x * y let con = x y. xy mul 3 5 - > 3 * 5 con BYV oid - > BYVoid
基本表达式 not let not = false - > true true - > false
基本表达式 and let and = true true - > true true false - > false false true - > false false false - > false
广义 AND let and = true value - > value false value - > false value true - > value value false - > false
定义 IF if let if = λ cond tvalue fvalue. (cond and tvalue) or (not cond and fvalue) if true a b - > (true and a) or (not true and b) - > a or false - > a
递归? n let fact = λ n. if (n == 0) 1 (n * fact n- 1) fact
如何表示递归 let fact = λ n. if (n == 0) 1 (n * fact n- 1) let P = λ self n. if (n==0) 1 (n * self(self n- 1)) let fact n = P (P n)
如此一来 fact 4 - > P (P 4) - > if (4==0) (1) (4 * P(P n- 1)) - > 4 * P(P 3) - > 4 * 3 * P(P 2) - > 4 * 3 * 2 * P(P 1) - > 4 * 3 * 2 * 1
可惜 let fact = λ n. if (n == 0) 1 (n * fact n- 1) λ
大胆的想法 fact let P = λ self n. if (n==0) 1 (n * self n- 1) P P(fact) - > λ n. if (n==0) 1 (n * fact n- 1) P(fact) = fact
不动点 P P(fact) = fact
找到不动点 let P = λ self n. if (n==0) 1 (n * self n- 1)
神奇的 Y 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)
终于有了 Y 组合子 self Y Y Y- Combinator Paul Graham Hackers and Painters
图灵等价 Y λ λ λ λ λ
停机问题的等价命题 λ λ n f(n)=g(n)
真实世界中的函数式编程 λ
HASKELL Haskell Haskell Curry Y (Currying) Haskell
HASKELL Haskell for Haskell
第一个 HASKELL 程序 Haskell GHC ghci let max a b = if a>b then a else b Prelude> max 3 4 4 Prelude> max 1.0001 1 1.0001 Prelude> max "BYVoid" "CmYkRgB123" "CmYkRgB123"
列表 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]
列表求和 acc.hs accumulate [] = 0 accumulate (elem:rest) = elem + accumulate rest main = print (accumulate [1,2,3]) runghc acc.hs 6
判断回文 palindrome [] = True palindrome [_] = True palindrome (elem:rest) = (elem == last rest) && (palindrome(init rest)) >palindrome [1, 2, 3, 2, 1] True >palindrome [1, 1, 2] False >palindrome "madam" 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] [1, 2, 3] >compress "aaabbaccc" "abac"
惰性求值 Haskell [1..] [1,3..] (eager evaluation) Haskell (lazy evaluation) [1,3..]!! 42 85
FIBONACCI 数列 Haskell Fibonacci 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
解释一下 fib = 1:1:zipWith (+) fib (tail fib) 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' d (Node 'a' Empty Empty) (Node 'c' Empty Empty) b e ) (Node 'e' Empty a c g (Node 'g' (Node 'f' Empty Empty) f Empty ) )
中序遍历 inorder Empty = [] inorder (Node value left right) = inorder left ++ [value] ++ inorder right >inorder tree "abcdefg"
树的高度 height Empty = 0 height (Node value left right) = max (height left) (height right) + 1 >height tree 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 4
高阶函数 inorder_func value left right = left ++ [value] ++ right inorder = traverse inorder_func [] >inorder tree "abcdefg"
工程中的函数式编程 Haskell Python JavaScript Ruby C++ 11 C# Scala
匿名函数 Python lambda x : x**2 C# x => x**2 JavaScript function (x) {return x * x} C++ 11 [](int x) - > int {return x * x;}
闭包 function make_closure() { var inner_varible = 0; return function () { return inner_varible++; } } var counter = make_closure(); counter(); // 0 counter(); // 1
用闭包实现柯里化 pow function pow5(x) { } return Math.pow(x, 5); pow5(2); // 32
谢谢大家 byvoid@byvoid.com HTTP://WWW.BYVOID.COM/BLOG
参考资料 http://zh.wikipedia.org/wiki/ http://mindhacks.cn/2006/10/15/cantor- godel- turing- an- eternal- golden- diagonal/ /blog/godel- incompleteness- theorems- agnosticism/ http://www.haskell.org/haskellwiki/ 99_questions https://developer.mozilla.org/en/ JavaScript/Guide/Closures http://www.cprogramming.com/c++11/c++11- lambda- closures.html