函數式編程簡介

函數式編程更加強調程序執行的結果而非執行的過程，倡導利用若干簡單的執行單元讓計算結果不斷漸進，逐層推導復雜的運算，而不是設計一個復雜的執行過程。 – 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 實現

Arrays.asList(0, 1, 2, 3, 4, 5, 6, 7, 8, 10).stream().reduce(0, Integer::sum);

同樣的代碼用 Clojure 實現

(apply + [0 1 2 3 4 5 6 7 8 10]) ; -> 46
#_(reduce + [0 1 2 3 4 5 6 7 8 10])

例子二 fabonacci數列

// 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)

比起命令式的語言，函數式語言更加關注執行的結果，而非執行的過程。

函數式編程的歷史

從Hilbert 23個數學難題談起

1900年，Hilbert 提出了數學界懸而未決的10大問題，后續陸續添加成了23個問題，被稱為著名的 Hilbert 23 Problem。針對其中第2個決定數學基礎的問題——算術公理之相容性，年輕的哥德爾提出了哥德爾不完備定理，解決了這個問題形式化之后的前兩點，即數學是完備的嗎？數學是相容的嗎？哥德爾用兩條定理給出了否定的回答。所謂不完備，即系統中存在一個為真，但是無法在系統中推導出來的命題。比如：U說：“U在PM中不可證”。雖然和說謊者很類似，但其實有明顯的差異。我們可以假設U為可證，那么可以推出PM是矛盾（不相容）的；但是假設U不可證，卻推導不出PM是矛盾的。U的含義是在M中不可證，而事實上，它被證明不可證，所以U是PM中不可證的真命題。基于第一條不完備定理，又可以推導出第二條定理。如果一個（強度足以證明基本算術公理的）公理系統可以用來證明它自身的相容性，那么它是不相容的。

而最后一個問題，數學是確定的嗎？也就是說，存在一個算法判定一個給定的命題是否是不確定的嗎（Entscheidungsproblem 確定性問題）？這個問題引起了阿隆佐·邱奇和年輕的阿蘭·圖靈的興趣。阿隆佐·邱奇的lambda calculus和圖靈的圖靈機構造出了可計算數，圖靈的那篇論文 ON COMPUTABLE NUMBERS, WITH AN APPLICATION TO THE ENTSCHEIDUNGSPROBLEM 的意義不在于證明可計算數是否可數，而在于證明可判定性是否成立。在1936年他們對判定性問題分別獨立給出了否定的答案。也就是現在被我們熟知的圖靈停機問題：不存在這樣一個程序（算法），它能夠計算任何程序（算法）在給定輸入上是否會結束（停機）。圖靈借此發明了通用圖靈機的概念，為后來的馮·諾依曼體系的計算機體系提供了理論基礎。

Lambda Calculus

Lambda 表達式包含三個要素

1. 變量
2. lambda 抽象
3. lambda 應用
   據此我們可以用函數給出布爾值的定義

   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
   

自然數的定義

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

函數式編程語言的發展

在這之后，隨著通用計算機的產生，人們發覺使用機器碼寫程序太沒有效率。所以1956年左右，John Buckus發明了Fortran（FORmula TRANslating 的縮寫）語言，如果對編譯原理有了解，那么對BNF范式就不陌生了。與此同時，John McCarthy 發明了Lisp語言，現代的Clojure就是Lisp的方言之一。1966年，Niklaus Wirth發明了Pascal。1969年，Ken Thompson和Dennis Ritchie發明了C語言，過程式語言由于其高效和可移植性迅速崛起。1973年，Robin Milner 發明了ML（Meta Language），后來演變成了OCaml和Stardard ML。1977年，John Buckus在其圖靈獎的演講中創造了 Functional Programming 這個詞。1990年，惰性求值的函數式編程語言 Haskell 1.0 發布。

神奇的 Y Combinator

(def Y (fn [f]
         ((fn [x] (x x))
          (fn [x]
            (f (fn [y]
                 ((x x) y)))))))

Lisp、ML以及Haskell的關系

Lisp是動態語言，使用S表達式

ML和Haskell都是靜態強類型函數式語言

ML是第一個使用Hindley-Milner type inference algorithm的語言

Lisp和ML都是call-by-value，但是Haskell則是call-by-name

Lisp和ML都是不純的編程語言，但是Haskell是side effect free的

函數是一等公民

函數是一等公民，指的是你可以將函數作為參數、返回值、數據結構存在，而且不僅可以用函數名引用，甚至可以匿名調用。

1. 作為參數

(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. 數據結構

(def dictionary {:a "abandon"}) ;; map is also a function, data is code.
(dictionary :a) ;-> "abandon"
(:a dictionary) ;-> "abandon"

4. 匿名函數

((fn [x] (* x x))
        2) ;-> 4

(map 
    (fn [num] (+ 1 num)) ;; anonymous function
    [1 2 3 4 5]) ;-> (2 3 4 5 6)

5. 模塊化

在面向對象中，對象是一等公民。所以我們處處要從對象的角度去考慮計算問題，然后產生一種共識——數據應該和它相關的操作放到一起，也就是我們所說的封裝。確實沒錯，但是我們得知道封裝的意義在哪里？功能內聚好理解（分塊）和局部性影響（控制可變性）。函數式編程同樣考慮這些，功能內聚不一定要用類的方式（考慮一下JS的prototype，也是一種面向對象），只要模塊做得好，一樣能達到效果。局部性影響，其本質是封裝可變因素以避免其擴散到代碼各處。函數式給出了自己的答案，消除可變因素。

高階函數和惰性求值也非常有利于模塊化。

純函數和不可變性

純函數是指執行過程中沒有副作用的函數，所謂副作用是說超出函數控制的操作，比如在執行過程中操作文件系統、數據庫等外部資源。純函數還具有引用透明性的特點，也就是同樣的輸入導致同樣的輸出，以至于完全可以用函數的值代替對函數的調用。

引用透明

舉個例子：

(inc 1) ; -> 2

(= (inc (inc 1)
   (inc 2))) ; -> true

你們可能就會問，這種東西究竟有什么用呢？純函數可以很方便地進行緩存。

(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"

不可變計算

談到不可變性，我們做個游戲。統計在座的一共有多少人數。我們都知道從某個人開始依次報數，最后得到的數字就是總人數，其實這就是一種不可變計算的游戲，為什么這么說呢？因為報數其實一個計算的過程，第一個人計算出1這個數，傳遞給第二個人。然后第二個人拿著前面的1進行加一操作，然后把結果2傳遞給后面的人做加法，以此類推。為了提高統計的效率，我也可以進行分組，然后每組自行報數，最后統計結果。但是如果我在白板上寫個數字1，然后讓大家來過來該這個數字，很大可能會出現錯誤，因為這個數字成為了競態條件。在多并發的情況下，就得用讀寫鎖來控制。所以不可變性特別利于并發。

不可變的鏈式結構

好了，現在我們有個新的需求，設計一個不可變列表收集大家的名字。每個節點存儲一個姓名的字符串，并且有個指針指向下一個節點。但是這也打破了列表的不可變性。怎么辦？我們可以把新的節點指向舊有的列表，然后返回一個新的列表。這就是不可變列表實現的機制。隨便一提，這也是區塊鏈不可變特征的由來。

Clojure的創造者Rich Hickey擴展了Ideal Hash Tree數據結構，實現了Persistent Vector。由于此處的葉子節點可以擴展成32個，所以可以大量存儲數據。利用Ideal Hash Tree的特點可以快速索引出數據，與此同時，數據的“增刪改”也能做到近常數化的時間，并且總是產生新的數據結構替換原有的數據結構，即一種不可變的鏈式存儲結構。

不可變的樹狀結構

Zipper數據結構類似于文本編輯器中的 gap buffer，編輯文本時，光標左邊和右邊分別是獨立的buffer，光標處也是單獨的buffer，這樣便可以方便地添加文字，也很方便刪除左右buffer中的文字；移動光標會涉及buffer之間的拷貝。基本上能在常數時間內完成編輯。Zipper數據結構模仿了這種方式，能在常數時間內完成樹的編輯工作，也能很快地重新構建一棵樹。

遞歸

可計算很大問題就是得實現遞歸功能。

(defn reverse-seq [coll]
  (when-let [elem (first coll)]
    (concat (reverse-seq (rest coll)) [elem])))
(reverse-seq [1 2 3]) ; -> (3 2 1)

和循環無異的尾遞歸

(defn gcd [& nums]
  (reduce #(if (zero? %2)
                %
                (recur %2 (mod % %2))) nums))
(gcd 8 16) ; -> 8

生成式測試

生成式測試會基于輸入假設輸出，并且生成許多可能的數據驗證假設的正確性。

(defn add [a b]
  (+ a b))
;; 任取兩個整數，把a和b加起來的結果減去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}

測試結果表明，剛才運行了100組測試，并且都通過了。理論上，程序可以生成無數的測試數據來驗證add方法的正確性。即便不能窮盡，我們也獲得一組統計上的數字，而不僅僅是幾個純手工挑選的用例。

抽象是什么

抽取共性，封裝細節，忘記不重要的差異點。這樣的好處是可以做到局部化影響和延遲決策。

命名

命名就是一種抽象，重構中最重要的技法就是重命名和提取小函數

(* 3 3 3)
(* x x x)
(* y y y)
->
(defn cube [x]
  (* x x x))

延遲決策

例如：我們定義數對 pair

pair:: (cons x y)
firstpair -> x
secondpair -> y

那么它的具體實現會是這樣的

(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)))

高階函數

高階函數就是可以接收函數的函數，高階函數提供了足夠的抽象，屏蔽了很多底層的實現細節。比如Clojure中的 map 高階函數，它接收 (fn [v] ...) ，把一組數據映射成另外一組數據。

過程抽象

(map inc [1 2 3 4 5]) ; -> (2 3 4 5 6)

這些函數抽象出映射這樣語義，除了容易記憶，還能很方便地重新編寫成高效的底層實現。也就是說，一旦出現了更高效的 map 實現算法，現有的代碼都能立刻從中受益。

函數的組合

函數組合之后會產生巨大的能量

神奇的加法

(((comp (map inc) (filter odd?)) +) 1 2) ; -> 4

怎么去理解這個函數的組合？我們給它取個好聽的名字

(def special+ ((comp (map inc) (filter odd?)) +))
(special+ 1 2) ; -> 4

; <=> 等價于
(if (odd? (inc 2))
    (+ 1 3))
    1)

這個未必是個好的組合方式，但是不可否認的是，我們可以用這些隨意地將這些函數組合到一起，得到我們想要的結果。

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出奇數并取出前10個元素。同等的代碼，如果用表達式直接書寫的話，如下：

(->> (range)
     (filter odd?)
     (take 10))

這里的問題就是我們沒能使用高階函數抽象出過程，如果把 conj 換成其他的reduce運算，現在的過程無法支撐，但是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

之所以會出現上述的結果，是因為 interleave xforms 將 (map inc) 以及 (filter odd?) 和logs進行了交叉，得到的結果是 (comp (map inc) (log) (filter odd?) (log)) ，所以如果是偶數就會被filter清除，看不見log了。

首先一定得理解：每個tranducer函數都是同構的！

形式如下

(defn m [f]
    (fn [rf] 
        (fn [result elem]
            (rf result (f elem)))))

這意味著 (m f) 的函數都是可以組合的，組合的形式如下：

(comp (m f) (m1 f1) ...)

展開之后

((m f) 
    ((m1 f1) 
        ((m2 f2) ...)))
->
(fn [result elem]
    (((m1 f1) 
        ((m2 f2) ...)) result (f elem)))

所以可以看到第一個執行的一定是 comp 的首個 reducing function 參數。故：

1. xform 作為組合的前提
2. 執行順序從左到右；
3. + 作為 reducing function 最后執行；

Monad

什么是 Monad 呢？A monad is just a monoid in the category of endofunctors.

1. Identity—For a monad m, m flatMap unit => m
2. Unit—For a monad m, unit(v) flatMap f => f(v)
3. Associativity—For a monad m, m flatMap g flatMap h => m flatMap {x => g(x) flatMap h}

   // java8 實現的 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]
       }
   }
   

表達式優于語句

S表達式

1. 原子，或者；
2. 形式為 (x ? y) 的表達式，其中x和y也是S表達式。

舉個例子，遞增一組數據，過濾奇數，然后進行排序，最終取出第一個。如果取不到，返回 :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

當然你也可以寫成

(if-let [r (first (sort (filter odd? (map inc [1 1 1]))))] 
    r 
    :not-found)
; -> :not-found

其實兩者都是S表達式，但是下面的寫法更加偏向于語句。從串聯起來讀來講，前者明顯是由于后者的。這要是放在其他函數式語言上，效果更加顯著。比如下面重構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();
}

這是典型的語句可以重構到表達式的場景，關鍵是怎么重構呢？

第一步，調轉 if 。

Optional rule = ruleOf(id);

if(!rule.isPresent()) {
    throw new RuntimeException();
} 

return transform(rule.get());

第二步， Optional.map 函數

...
return rule.map(r -> transform(r)).get();

第三步， inline transform 函數

...
rule.map(r -> Rule.builder()
                    .withName("No." + r.getId())
                    .build()).get();

第四步， Optional.orElseThrow 函數

...
rule.map(r-> Rule.builder()
                    .withName("No." + r.getId())
                    .build())
    .orElseThrow(() ->new RuntimeException());

第五步，注 if 釋語句中的 throw new RuntimeException()

if(!rule.isPresent()) {
   // throw new RuntimeException();
}

這時候發現語句中為空，即可將整個語句刪除。可以考慮 inline rule 。

ruleOf(id).map(r-> Rule.builder()
                    .withName("No." + r.getId())
                    .build())
    .orElseThrow(() ->new RuntimeException());

完畢。

我們認識事物的方式

1. 把幾個簡單的想法合并成一個復合概念，從而創造出所有復雜的概念。
2. 簡單的或復雜的兩種思想融合在一起，并立即把它們聯系起來，不要把它們統一起來，從而得到它所有的關系思想。
3. 把他們與其他所有陪伴他們的真實存在的想法分開：這就是所謂的抽象，因此所有的一般想法都是被提出來的。

 

來自：https://lambeta.com/2018/02/17/The-Simple-Summary-of-FP/