函數(shù)式編程簡介
2018-07-20 來源：編程學(xué)習(xí)網(wǎng)
函數(shù)式編程更加強調(diào)程序執(zhí)行的結(jié)果而非執(zhí)行的過程，倡導(dǎo)利用若干簡單的執(zhí)行單元讓計算結(jié)果不斷漸進，逐層推導(dǎo)復(fù)雜的運算，而不是設(shè)計一個復(fù)雜的執(zhí)行過程。 – wiki
例子一 累加運算
// sum
List<Integer> nums = Arrays.asList(0, 1, 2, 3, 4, 5, 6, 7, 8, 10);
public static Integer sum(List<Integer> nums){
int result = 0;
for (Integer num : nums) {
result += num;
}
return result;
}
sum(nums); // -> 46
同樣的代碼用 Java8 Stream 實現(xiàn)
Arrays.asList(0, 1, 2, 3, 4, 5, 6, 7, 8, 10).stream().reduce(0, Integer::sum);
同樣的代碼用 Clojure 實現(xiàn)
(apply + [0 1 2 3 4 5 6 7 8 10]) ; -> 46
#_(reduce + [0 1 2 3 4 5 6 7 8 10])
例子二 fabonacci數(shù)列
// java
public static int fibonacci(int number){
if (number == 1) {
return 1;
}
if(number == 2) {
return 2;
}
int a = 1;
int b = 2;
for(int cnt = 3; cnt <= number; cnt++) {
int c = a + b;
a = b;
b = c;
}
return b;
}
// java8
Stream.iterate(new int[]{1, 1}, s -> new int[]{s[1], s[0] + s[1]})
.limit(10)
.map(n -> n[1])
.collect(toList())
// -> [1, 2, 3, 5, 8, 13, 21, 34, 55, 89]
// clojure
(->> (iterate (fn [[a b]] [b (+ a b)]) [1 1])
(map second)
(take 10))
; -> (1 2 3 5 8 13 21 34 55 89)
比起命令式的語言，函數(shù)式語言更加關(guān)注執(zhí)行的結(jié)果，而非執(zhí)行的過程。
函數(shù)式編程的歷史
從Hilbert 23個數(shù)學(xué)難題談起
1900年，Hilbert 提出了數(shù)學(xué)界懸而未決的10大問題，后續(xù)陸續(xù)添加成了23個問題，被稱為著名的 Hilbert 23 Problem。針對其中第2個決定數(shù)學(xué)基礎(chǔ)的問題——算術(shù)公理之相容性，年輕的哥德爾提出了哥德爾不完備定理，解決了這個問題形式化之后的前兩點，即數(shù)學(xué)是完備的嗎？數(shù)學(xué)是相容的嗎？哥德爾用兩條定理給出了否定的回答。所謂不完備，即系統(tǒng)中存在一個為真，但是無法在系統(tǒng)中推導(dǎo)出來的命題。比如：U說：“U在PM中不可證”。雖然和說謊者很類似，但其實有明顯的差異。我們可以假設(shè)U為可證，那么可以推出PM是矛盾（不相容）的；但是假設(shè)U不可證，卻推導(dǎo)不出PM是矛盾的。U的含義是在M中不可證，而事實上，它被證明不可證，所以U是PM中不可證的真命題�；诘谝粭l不完備定理，又可以推導(dǎo)出第二條定理。如果一個（強度足以證明基本算術(shù)公理的）公理系統(tǒng)可以用來證明它自身的相容性，那么它是不相容的。
而最后一個問題，數(shù)學(xué)是確定的嗎？也就是說，存在一個算法判定一個給定的命題是否是不確定的嗎（Entscheidungsproblem 確定性問題）？這個問題引起了阿隆佐·邱奇和年輕的阿蘭·圖靈的興趣。阿隆佐·邱奇的lambda calculus和圖靈的圖靈機構(gòu)造出了可計算數(shù)，圖靈的那篇論文 ON COMPUTABLE NUMBERS, WITH AN APPLICATION TO THE ENTSCHEIDUNGSPROBLEM 的意義不在于證明可計算數(shù)是否可數(shù)，而在于證明可判定性是否成立。在1936年他們對判定性問題分別獨立給出了否定的答案。也就是現(xiàn)在被我們熟知的圖靈停機問題：不存在這樣一個程序（算法），它能夠計算任何程序（算法）在給定輸入上是否會結(jié)束（停機）。圖靈借此發(fā)明了通用圖靈機的概念，為后來的馮·諾依曼體系的計算機體系提供了理論基礎(chǔ)。
Lambda Calculus
Lambda 表達式包含三個要素
- 變量
- lambda 抽象
- lambda 應(yīng)用
據(jù)此我們可以用函數(shù)給出布爾值的定義data BOOL = FALSE | TRUE TRUE = λx.λy.x FALSE = λx.λy.y not = λb.b FALSE TRUE and = λb1.λb2.b1 b2 FALSE or = λb1.λb2.b1 TRUE b2 xor = λb1.λb2.b1 (not b2) b2
自然數(shù)的定義
data NAT = Z | S NAT
0 = λf.λs.s
1 = λf.λs.f s
2 = λf.λs.f f s
succ n = λf.λs.f (n f s)
zero? n = n (λb.FALSE) TRUE
add = succ n1 n2
函數(shù)式編程語言的發(fā)展
在這之后，隨著通用計算機的產(chǎn)生，人們發(fā)覺使用機器碼寫程序太沒有效率。所以1956年左右，John Buckus發(fā)明了Fortran（FORmula TRANslating 的縮寫）語言，如果對編譯原理有了解，那么對BNF范式就不陌生了。與此同時，John McCarthy 發(fā)明了Lisp語言，現(xiàn)代的Clojure就是Lisp的方言之一。1966年，Niklaus Wirth發(fā)明了Pascal。1969年，Ken Thompson和Dennis Ritchie發(fā)明了C語言，過程式語言由于其高效和可移植性迅速崛起。1973年，Robin Milner 發(fā)明了ML（Meta Language），后來演變成了OCaml和Stardard ML。1977年，John Buckus在其圖靈獎的演講中創(chuàng)造了 Functional Programming 這個詞。1990年，惰性求值的函數(shù)式編程語言 Haskell 1.0 發(fā)布。
神奇的 Y Combinator
(def Y (fn [f]
((fn [x] (x x))
(fn [x]
(f (fn [y]
((x x) y)))))))
Lisp、ML以及Haskell的關(guān)系
Lisp是動態(tài)語言，使用S表達式
ML和Haskell都是靜態(tài)強類型函數(shù)式語言
ML是第一個使用Hindley-Milner type inference algorithm的語言
Lisp和ML都是call-by-value，但是Haskell則是call-by-name
Lisp和ML都是不純的編程語言，但是Haskell是side effect free的
函數(shù)是一等公民
函數(shù)是一等公民，指的是你可以將函數(shù)作為參數(shù)、返回值、數(shù)據(jù)結(jié)構(gòu)存在，而且不僅可以用函數(shù)名引用，甚至可以匿名調(diào)用。
1. 作為參數(shù)
(map inc [1 2 3 4 5]) ;-> (2 3 4 5 6) ;; inc is an argument
2. 作為返回值
(defn add [num]
(fn [other-num] (+ num other-num))) ;; as return-value
(def add-one (add 1))
(add-one 2) ;-> 3
(defn flip [f] ;; as argument and return-value
(fn [x y]
(f y x)))
3. 數(shù)據(jù)結(jié)構(gòu)
(def dictionary {:a "abandon"}) ;; map is also a function, data is code.
(dictionary :a) ;-> "abandon"
(:a dictionary) ;-> "abandon"
4. 匿名函數(shù)
((fn [x] (* x x))
2) ;-> 4
(map
(fn [num] (+ 1 num)) ;; anonymous function
[1 2 3 4 5]) ;-> (2 3 4 5 6)
5. 模塊化
在面向?qū)ο笾�，對象是一等公民。所以我們處處要從對象的角度去考慮計算問題，然后產(chǎn)生一種共識——數(shù)據(jù)應(yīng)該和它相關(guān)的操作放到一起，也就是我們所說的封裝。確實沒錯，但是我們得知道封裝的意義在哪里？功能內(nèi)聚好理解（分塊）和局部性影響（控制可變性）。函數(shù)式編程同樣考慮這些，功能內(nèi)聚不一定要用類的方式（考慮一下JS的prototype，也是一種面向?qū)ο螅�，只要模塊做得好，一樣能達到效果。局部性影響，其本質(zhì)是封裝可變因素以避免其擴散到代碼各處。函數(shù)式給出了自己的答案，消除可變因素。
高階函數(shù)和惰性求值也非常有利于模塊化。
純函數(shù)和不可變性
純函數(shù)是指執(zhí)行過程中沒有副作用的函數(shù)，所謂副作用是說超出函數(shù)控制的操作，比如在執(zhí)行過程中操作文件系統(tǒng)、數(shù)據(jù)庫等外部資源。純函數(shù)還具有引用透明性的特點，也就是同樣的輸入導(dǎo)致同樣的輸出，以至于完全可以用函數(shù)的值代替對函數(shù)的調(diào)用。
引用透明
舉個例子：
(inc 1) ; -> 2
(= (inc (inc 1)
(inc 2))) ; -> true
你們可能就會問，這種東西究竟有什么用呢？純函數(shù)可以很方便地進行緩存。
(defn fibonacci [number]
(if (or (zero? number) (= 1 number)) 1
(+
(fibonacci (dec number))
(fibonacci (- number 2)))))
(fibonacci 30) ; -> "Elapsed time: 185.690208 msecs"
(def fibonacci
(memoize (fn [number] ;;
(if (or (zero? number) (= 1 number)) 1
(+
(fibonacci (dec number))
(fibonacci (- number 2)))))))
(fibonacci 30) ; -> "Elapsed time: 0.437114 msecs"
不可變計算
談到不可變性，我們做個游戲。統(tǒng)計在座的一共有多少人數(shù)。我們都知道從某個人開始依次報數(shù)，最后得到的數(shù)字就是總?cè)藬?shù)，其實這就是一種不可變計算的游戲，為什么這么說呢？因為報數(shù)其實一個計算的過程，第一個人計算出1這個數(shù)，傳遞給第二個人。然后第二個人拿著前面的1進行加一操作，然后把結(jié)果2傳遞給后面的人做加法，以此類推。為了提高統(tǒng)計的效率，我也可以進行分組，然后每組自行報數(shù)，最后統(tǒng)計結(jié)果。但是如果我在白板上寫個數(shù)字1，然后讓大家來過來該這個數(shù)字，很大可能會出現(xiàn)錯誤，因為這個數(shù)字成為了競態(tài)條件。在多并發(fā)的情況下，就得用讀寫鎖來控制。所以不可變性特別利于并發(fā)。
不可變的鏈?zhǔn)浇Y(jié)構(gòu)
好了，現(xiàn)在我們有個新的需求，設(shè)計一個不可變列表收集大家的名字。每個節(jié)點存儲一個姓名的字符串，并且有個指針指向下一個節(jié)點。但是這也打破了列表的不可變性。怎么辦？我們可以把新的節(jié)點指向舊有的列表，然后返回一個新的列表。這就是不可變列表實現(xiàn)的機制。隨便一提，這也是區(qū)塊鏈不可變特征的由來。
Clojure的創(chuàng)造者Rich Hickey擴展了Ideal Hash Tree數(shù)據(jù)結(jié)構(gòu)，實現(xiàn)了Persistent Vector。由于此處的葉子節(jié)點可以擴展成32個，所以可以大量存儲數(shù)據(jù)。利用Ideal Hash Tree的特點可以快速索引出數(shù)據(jù)，與此同時，數(shù)據(jù)的“增刪改”也能做到近常數(shù)化的時間，并且總是產(chǎn)生新的數(shù)據(jù)結(jié)構(gòu)替換原有的數(shù)據(jù)結(jié)構(gòu)，即一種不可變的鏈?zhǔn)酱鎯Y(jié)構(gòu)。
不可變的樹狀結(jié)構(gòu)
Zipper數(shù)據(jù)結(jié)構(gòu)類似于文本編輯器中的 gap buffer，編輯文本時，光標(biāo)左邊和右邊分別是獨立的buffer，光標(biāo)處也是單獨的buffer，這樣便可以方便地添加文字，也很方便刪除左右buffer中的文字；移動光標(biāo)會涉及buffer之間的拷貝。基本上能在常數(shù)時間內(nèi)完成編輯。Zipper數(shù)據(jù)結(jié)構(gòu)模仿了這種方式，能在常數(shù)時間內(nèi)完成樹的編輯工作，也能很快地重新構(gòu)建一棵樹。
遞歸
可計算很大問題就是得實現(xiàn)遞歸功能。
(defn reverse-seq [coll]
(when-let [elem (first coll)]
(concat (reverse-seq (rest coll)) [elem])))
(reverse-seq [1 2 3]) ; -> (3 2 1)
和循環(huán)無異的尾遞歸
(defn gcd [& nums]
(reduce #(if (zero? %2)
%
(recur %2 (mod % %2))) nums))
(gcd 8 16) ; -> 8
生成式測試
生成式測試會基于輸入假設(shè)輸出，并且生成許多可能的數(shù)據(jù)驗證假設(shè)的正確性。
(defn add [a b]
(+ a b))
;; 任取兩個整數(shù)，把a和b加起來的結(jié)果減去a總會得到b。
(def test-add
(prop/for-all [a (gen/int)
b (gen/int)]
(= (- (add a b) a) b)))
(tc/quick-check 100 test-add)
; -> {:result true, :num-tests 100, :seed 1515935038284}
測試結(jié)果表明，剛才運行了100組測試，并且都通過了。理論上，程序可以生成無數(shù)的測試數(shù)據(jù)來驗證add方法的正確性。即便不能窮盡，我們也獲得一組統(tǒng)計上的數(shù)字，而不僅僅是幾個純手工挑選的用例。
抽象是什么
抽取共性，封裝細節(jié)，忘記不重要的差異點。這樣的好處是可以做到局部化影響和延遲決策。
命名
命名就是一種抽象，重構(gòu)中最重要的技法就是重命名和提取小函數(shù)
(* 3 3 3)
(* x x x)
(* y y y)
->
(defn cube [x]
(* x x x))
延遲決策
例如：我們定義數(shù)對 pair
pair:: (cons x y)
firstpair -> x
secondpair -> y
那么它的具體實現(xiàn)會是這樣的
(defn cons [x y]
(fn [m]
(cond (= m 0) x
(= m 1) y)))
(defn first [z]
(z 0))
(defn second [z]
(z 1))
也可以是這樣的，還可以是其它各種各樣的形式。
(defn cons [x y]
(fn [b]
(b x y))
(defn first [z]
(z (fn [x y] x)))
(defn second [z]
(z (fn [x y] y)))
高階函數(shù)
高階函數(shù)就是可以接收函數(shù)的函數(shù)，高階函數(shù)提供了足夠的抽象，屏蔽了很多底層的實現(xiàn)細節(jié)。比如Clojure中的 map 高階函數(shù)，它接收 (fn [v] ...) ，把一組數(shù)據(jù)映射成另外一組數(shù)據(jù)。
過程抽象
(map inc [1 2 3 4 5]) ; -> (2 3 4 5 6)
這些函數(shù)抽象出映射這樣語義，除了容易記憶，還能很方便地重新編寫成高效的底層實現(xiàn)。也就是說，一旦出現(xiàn)了更高效的 map 實現(xiàn)算法，現(xiàn)有的代碼都能立刻從中受益。
函數(shù)的組合
函數(shù)組合之后會產(chǎn)生巨大的能量
神奇的加法
(((comp (map inc) (filter odd?)) +) 1 2) ; -> 4
怎么去理解這個函數(shù)的組合？我們給它取個好聽的名字
(def special+ ((comp (map inc) (filter odd?)) +))
(special+ 1 2) ; -> 4
; <=> 等價于
(if (odd? (inc 2))
(+ 1 3))
1)
這個未必是個好的組合方式，但是不可否認的是，我們可以用這些隨意地將這些函數(shù)組合到一起，得到我們想要的結(jié)果。
transducer
(def xf (comp (filter odd?) (take 10)))
(transduce xf conj (range))
;; [1 3 5 7 9 11 13 15 17 19]
這里直接將求值延遲到了 transduce 計算的時候，換句話說， xf 定義了一種過程：filter出奇數(shù)并取出前10個元素。同等的代碼，如果用表達式直接書寫的話，如下：
(->> (range)
(filter odd?)
(take 10))
這里的問題就是我們沒能使用高階函數(shù)抽象出過程，如果把 conj 換成其他的reduce運算，現(xiàn)在的過程無法支撐，但是tranducers可以！
(transduce xf + (range)) ;-> 100
我們再看一個tranducer的神奇使用方式：
(defn log [& [idx]]
(fn [rf]
(fn
([] (rf))
([result] (rf result))
([result el]
(let [n-step (if idx (str "Step: " idx ". ") "")]
(println (format "%sResult: %s, Item: %s" n-step result el)))
(rf result el)))))
(def ^:dynamic *dbg?* false)
(defn comp* [& xforms]
(apply comp
(if *dbg?*
(->> (range)
(map log)
(interleave xforms))
xforms)))
(binding [*dbg?* true]
(transduce
(comp*
(map inc)
(filter odd?))
+
(range 5))) ;; -> 9
Step: 0. Result: 0, Item: 1
Step: 1. Result: 0, Item: 1
Step: 0. Result: 1, Item: 2
Step: 0. Result: 1, Item: 3
Step: 1. Result: 1, Item: 3
Step: 0. Result: 4, Item: 4
Step: 0. Result: 4, Item: 5
Step: 1. Result: 4, Item: 5
之所以會出現(xiàn)上述的結(jié)果，是因為 interleave xforms 將 (map inc) 以及 (filter odd?) 和logs進行了交叉，得到的結(jié)果是 (comp (map inc) (log) (filter odd?) (log)) ，所以如果是偶數(shù)就會被filter清除，看不見log了。
首先一定得理解：每個tranducer函數(shù)都是同構(gòu)的！
形式如下
(defn m [f]
(fn [rf]
(fn [result elem]
(rf result (f elem)))))
這意味著 (m f) 的函數(shù)都是可以組合的，組合的形式如下：
(comp (m f) (m1 f1) ...)
展開之后
((m f)
((m1 f1)
((m2 f2) ...)))
->
(fn [result elem]
(((m1 f1)
((m2 f2) ...)) result (f elem)))
所以可以看到第一個執(zhí)行的一定是 comp 的首個 reducing function 參數(shù)。故：
- xform 作為組合的前提
- 執(zhí)行順序從左到右；
- + 作為 reducing function 最后執(zhí)行；
Monad
什么是 Monad 呢？A monad is just a monoid in the category of endofunctors.
- Identity—For a monad m, m flatMap unit => m
- Unit—For a monad m, unit(v) flatMap f => f(v)
- Associativity—For a monad m, m flatMap g flatMap h => m flatMap {x => g(x) flatMap h}
// java8 實現(xiàn)的 9*9 乘法表 public class ListMonad<T>{ private List<T> elements; private ListMonad(T elem) { this.elements = singletonList(elem); } private ListMonad(List<T> elems) { this.elements = elems; } public <U> ListMonad<U> flatmap(Function<T, ListMonad<U>> fn) { List<U> newElements = new ArrayList<>(); this.elements.forEach(elem -> newElements.addAll(fn.apply(elem).elements)); return new ListMonad<>(newElements); } public <X> ListMonad<X> uint(X elem) { return new ListMonad<>(elem); } public <U> ListMonad<U> apply(ListMonad<Function<T, U>> m) { return m.flatmap(this::map); } public <U> ListMonad<U> map(Function<T, U> fn) { return flatmap(t -> uint(fn.apply(t))); } public static void main(String[] args) { ListMonad<Integer> m = new ListMonad<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9)); ListMonad<Integer> m1 = new ListMonad<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9)); ListMonad<Integer> list = m.apply(m1.map(x -> y -> x * y)); // [1...81] } }
表達式優(yōu)于語句
S表達式
- 原子，或者；
- 形式為 (x ? y) 的表達式，其中x和y也是S表達式。
舉個例子，遞增一組數(shù)據(jù)，過濾奇數(shù)，然后進行排序，最終取出第一個。如果取不到，返回 :not-found 。
(-> [1 2 3]
(->> (map inc)
(filter odd?)
(sort)
(first))
(or :not-found))
; -> 3
(-> [1 1 3]
(->> (map inc)
(filter odd?)
(sort)
(first))
(or :not-found)
; -> :not-found
當(dāng)然你也可以寫成
(if-let [r (first (sort (filter odd? (map inc [1 1 1]))))]
r
:not-found)
; -> :not-found
其實兩者都是S表達式，但是下面的寫法更加偏向于語句。從串聯(lián)起來讀來講，前者明顯是由于后者的。這要是放在其他函數(shù)式語言上，效果更加顯著。比如下面重構(gòu)if-else控制語句到Optional類型。
if-else -> Optional
Optional<Rule> rule = ruleOf(id);
if(rule.isPresent()) {
return transform(rule.get());
} else {
throw new RuntimeException();
}
public Rule transform(Rule rule){
return Rule.builder()
.withName("No." + rule.getId())
.build();
}
這是典型的語句可以重構(gòu)到表達式的場景，關(guān)鍵是怎么重構(gòu)呢？
第一步，調(diào)轉(zhuǎn) if 。
Optional rule = ruleOf(id);
if(!rule.isPresent()) {
throw new RuntimeException();
}
return transform(rule.get());
第二步， Optional.map 函數(shù)
...
return rule.map(r -> transform(r)).get();
第三步， inline transform 函數(shù)
...
rule.map(r -> Rule.builder()
.withName("No." + r.getId())
.build()).get();
第四步， Optional.orElseThrow 函數(shù)
...
rule.map(r-> Rule.builder()
.withName("No." + r.getId())
.build())
.orElseThrow(() ->new RuntimeException());
第五步，注 if 釋語句中的 throw new RuntimeException()
if(!rule.isPresent()) {
// throw new RuntimeException();
}
這時候發(fā)現(xiàn)語句中為空，即可將整個語句刪除�？梢钥紤] inline rule 。
ruleOf(id).map(r-> Rule.builder()
.withName("No." + r.getId())
.build())
.orElseThrow(() ->new RuntimeException());
完畢。
我們認識事物的方式
- 把幾個簡單的想法合并成一個復(fù)合概念，從而創(chuàng)造出所有復(fù)雜的概念。
- 簡單的或復(fù)雜的兩種思想融合在一起，并立即把它們聯(lián)系起來，不要把它們統(tǒng)一起來，從而得到它所有的關(guān)系思想。
- 把他們與其他所有陪伴他們的真實存在的想法分開：這就是所謂的抽象，因此所有的一般想法都是被提出來的。
來自：https://lambeta.com/2018/02/17/The-Simple-Summary-of-FP/
標(biāo)簽： isp 代碼 數(shù)據(jù)庫
版權(quán)申明：本站文章部分自網(wǎng)絡(luò)，如有侵權(quán)，請聯(lián)系：west999com@outlook.com
特別注意：本站所有轉(zhuǎn)載文章言論不代表本站觀點！
本站所提供的圖片等素材，版權(quán)歸原作者所有，如需使用，請與原作者聯(lián)系。
