Java 開發者的函數式程式設計

Java 開發者的函數式程式設計 Functional Programming for Java Developers

議程 • 前情提要 • 初探函數程式設計 • 代數資料型態 • List 處理模式 • 不可變動特性 • 回到熟悉的 Java

議程 • lambda • closure • 動靜之間 • 沒有 lambda/closure 的 Java • Java SE 7 lambda/closure 提案

議程 • 一級函式與 λ 演算 • JDK8 的 Lambda 語法 • 介面預設方法（Default method） • 擴充的 Collection 框架 • 函數式風格的可能性

函數式程式設計？ • JDK8 的 Lambda 語法 • 一級函式概念 • 函數式設計 • λ 演算

函數式程式設計？ • Joel Spolsky 具備一級函式的程式語言，能讓你找到更多抽象化的機會 - 《約耳續談軟體》 • Simon Peyton Jones – 純函數式領域中學到的觀點和想法，可能會給主流領域帶來資訊、帶來啟發 - 《編程的頂尖對話》

函數式程式設計？ • I Have to Be Good at Writing Concurrent Programs • Most Programs Are Just Data Management Problems • Functional Programming Is More Modular • I Have to Work Faster and Faster • Functional Programming Is a Return to Simplicity

• 費式數的數學定義 F0 = 0 F1 = 1 Fn = Fn-1 + Fn-2 • 指令式程設（Imperative programming） int fib(int n) { int a = 1; int b = 1; for(int i = 2; i < n; i++) { int tmp = b; b = a + b; a = tmp; } return b; }

• 費式數的數學定義 F0 = 0 F1 = 1 Fn = Fn-1 + Fn-2 • 函數式程設 int fib(int n) { if(n == 0 || n == 1) return n; else return fib(n - 1) + fib(n - 2); }

• 費式數的數學定義 F0 = 0 F1 = 1 Fn = Fn-1 + Fn-2 • 函數式程設（Haskell） fib 0 = 0 fib 1 = 1 fib n = fib (n-1) + fib (n-2)

初探函數程式設計 • 使用非函數式語言可能撰寫出函數式風格式，然而可能… – 事倍功半 – 可讀性變差 – 執行效能不好 • 純函數式語言 – Haskell • 多重典範語言 – Scala

初探函數程式設計 • 將問題分解為子問題才是重點 – 遞迴只是程式語法上表現子問題外在形式 • 命令式加總數列 – 變數 sum 初始值為 0，逐一取得數列元素與 sum 相加後更新 sum，直到沒有下個元素後傳回 sum …（命令電腦如何求解） int sum(int[] nums) { int sum = 0; for(int num : nums) { sum += num; } return sum; }

初探函數程式設計 • 函數式、宣告式（Declarative）加總數列 – 空數列為 0（廢話？XD） – 非空數列為首元素加上剩餘數列加總 sum [] = 0 sum (x:xs) = x + sum xs • 將問題定義出來…

初探函數程式設計 • 等等 … 現在談的是 Java … • 用 Java 以函數式風格解這問題得先談談 … – 代數資料型態（Algebraic data type） – List 處理模式 – 不可變動性

代數資料型態 • 抽象資料型態（Abstract data type） – 封裝結構與操作，僅透露互動時的規格 • 代數資料型態（Algebraic data type） – 揭露資料的結構與規律性，使之易於分而治之（Divide and conquer）

代數資料型態 • 重新定義 List（使用 JDK8 新語法） public static interface List<T> { T head() default { return null; } List<T> tail() default { return null; } } • 非空 List 就是由尾端 List 與前端元素組成 head … tail

代數資料型態 • 空 List（沒頭沒尾） List<? extends Object> Nil = new List<Object>() { public String toString() { return "[]"; } }; public static <T> List<T> nil() { return (List<T>) Nil; } • 具有單元素的 List 就是 … … Nil x xs

代數資料型態 • 在 List（xs）前置一個元素（x） public static <T> List<T> cons(final T x, final List<T> xs) { return new List<T>() { private T head; private List<T> tail; { this.head = x; this.tail = xs; } public T head(){ return this.head; } public List<T> tail() { return this.tail; } public String toString() { return head() + ":" + tail(); } }; }

代數資料型態 • 具有單元素 1 的 List 就是 … cons(1, nil()) // 1:[] • 具有元素 2、1 的 List 就是 … cons(2, cons(1, nil())) // 2:1:[] • 具有元素 3、2、1 的 List 就是 … cons(3, cons(2, cons(1, nil()))) // 3:2:1:[]

代數資料型態 • 為了方便 … public static <T> List<T> list(T... elems) { if(elems.length == 0) return nil(); T[] remain = Arrays.copyOfRange(elems, 1, elems.length); return cons(elems[0], list(remain)); } • 具有元素 3、2、1 的 List 就是 … list(3, 2, 1) // 3:2:1:[]

代數資料型態 • 代數資料型態（Algebraic data type） – 揭露資料的結構與規律性，使之易於分而治之（Divide and conquer）

List 處理模式 • 函數式、宣告式加總數列 – 空數列為 0 – 非空數列為首元素加上尾端數列加總 sum [] = 0 sum (x:xs) = x + sum xs public static Integer sum(List<Integer> lt) { if(lt == Nil) return 0; else return ((Integer) lt.head()) + sum(lt.tail()); } sum(list(1, 2, 3, 4, 5)) // 15

• 如果想將一組整數都加一 – 空數列為空數列 – 非空數列為首元素加 1 結合加一後的尾端數列 public static List<Integer> addOne(List<Integer> lt) { if(lt == Nil) return (List<Integer>) Nil; else return cons((Integer) lt.head() + 1, addOne(lt.tail())); } • 如果想讓一組整數都減 2 – +1 改為 –2，addOne 改為 subtractTwo • 如果想讓一組整數都乘 3 – +1 改為 *3，addOne 改為 multiplyThree

• 如果 +1、-2、*3 是個可傳入的函式 • 咦？JDK8 的 Lambda 不就是一級函式概念？ • 定義函式介面（Functional interface） interface F1<P, R> { R apply(P p); } • 從一組整數對應至另一組整數是 List 常見處理模式 public static <T, R> List<R> map(List<T> lt, F1<T, R> f) { if(lt == nil()) return nil(); else return cons(f.apply(lt.head()), map(lt.tail(), f)); }

• 如果想將一組整數都加一 map(list(1, 2, 3, 4, 5), x -> x + 1) • 如果想讓一組整數都減 2 map(list(1, 2, 3, 4, 5), x -> x - 2) • 如果想讓一組整數都乘 3 map(list(1, 2, 3, 4, 5), x -> x * 3) • map 很好用，有一百萬種用法 … XD

• 過濾一組整數，只留下大於 3 的部份… public static List<Integer> greaterThanThree(List<Integer> lt) { if(lt == Nil) return (List<Integer>) Nil; else { if(((Integer) lt.head()) > 3) return cons(lt.head(), greaterThanThree(lt.tail())); else return greaterThanThree(lt.tail()); } } • 過濾一組整數，只留下小於 10 的部份… public static List<Integer> lessThanTen(List<Integer> lt) { if(lt == Nil) return (List<Integer>) Nil; else { if(((Integer) lt.head()) < 10) return cons(lt.head(), lessThanTen(lt.tail())); else return lessThanTen(lt.tail()); } }

• 過濾一組整數是常見的 List 處理模式 … public static <T> List<T> filter(List<T> lt, F1<T, Boolean> f) { if(lt == nil()) return nil(); else { if(f.apply(lt.head())) return cons(lt.head(), filter(lt.tail(), f)); else return filter(lt.tail(), f); } }

• 過濾一組整數，只留下大於 3 的部份… filter(list(1, 2, 3, 4, 5), x -> x > 3) // 4:5:[] • 過濾一組整數，只留下小於 10 的部份… filter(list(19, 9, 7, 19, 10, 4), x -> x < 10) // 9:7:4:[] • filter 很好用，可以設定一百萬種過濾條件 … XD

• 類似地，從一組整數求值，也是常見的 List 處理模式 interface F2<P, R> { R apply(R r, P p); } public static <T, R> R reduce(List<T> lt, F2<T, R> f2, R r) { if(lt == nil()) return r; else return reduce(lt.tail(), f2, f2.apply(r, lt.head())); } • 加總一組整數 reduce(list(1, 2, 3, 4, 5), (r, x) -> r + x, 0) // 15

• reduce 別名 foldLeft + 0 1 2 3 4 5 • 從左邊開始折紙…

• reduce 別名 foldLeft + 1 2 3 4 5 • 一折…

• reduce 別名 foldLeft + 3 3 4 5 • 二折…

• reduce 別名 foldLeft + 6 4 5 • 三折…

• reduce 別名 foldLeft + 10 5 • 四折…

• reduce 別名 foldLeft 15 5 5 5 • 折完收工…XD • reduce 很好用，可以有一百萬種求值方式 … XD

• 流程中變數可變動 – 容易設計出貫穿函式前後的流程，而不易將問題分解為子問題 • 函式引用可變動非區域變數 – 會受到副作用（Side effect）影響，也就是不可見的輸入或輸出影響 • 物件狀態可變動 – 對方法而言，物件值域（Field）就是非區域變數 – 物件將會是副作用集合體，追蹤變數的難度提昇至追蹤物件狀態 – 在多執行緒共用存取的情況下，維持物件狀態的同步將會更為困難

• 不可變動特性（Immutability）是函數式風格中的基本特性 – 每個程式片段就易於分解為更小的片段 – 引用了非區域變數，函式也不會有副作用 – 物件不會是副作用集合體，也就不會有多執行緒下共用存取的問題 • 發現了嗎？剛剛一連串的設計中，沒有改變任何 List 狀態或變數參考！ – 對應轉換首元素 + 對應轉換餘數列 – 過濾首元素 + 過濾餘數列 – 處理首元素 + 處理餘數列

流程控制轉換 • 迴圈的問題 – 修改變數值或物件狀態 – 易在迴圈中對數個變數或物件進行改變，使得演算流程趨於複雜 – 迴圈中可能同時處理了數個子問題 • 迴圈的本質 – 處理重複性問題，每次的重複操作就是一個子操作 – 子操作就是子問題，獨立出來成為函式後重複呼叫 • 咦？這不就是遞迴嗎？迴圈與遞迴都是處理子問題的外在形式！ • 分解出子問題才是重點！

不可變動特性 • 強制將問題分解為子問題的手段 • 強制剝離邏輯泥團（ Logical clump）的手段 • 因為不可變動特性，所以流程控制語法 … – 無法使用迴圈，使用遞迴取代 – 必須是運算式 • if(cond) return some; else return other; • cond : some ? other; – 沒有 null？

• 傳回 null 時 … String name = selectBy(id); if(name == null) { name = "guest"; } • 設計 getOrElse 方法 String getOrElse(String original, String replacement) { return original == null ? replacement : original; } String name = getOrElse(selectBy(id), "Guest")

• 設計 Option 物件 public class Option<T> { private final T value; public Option(T value) { this.value = value; } public T getOrElse(T replacement) { return this.value == null ? replacement : this.value; } } Option<T> selectBy(T replace) { ... return new Option(rs.next() ? rs.getString("name") : null); } String name = selectBy(id).getOrElse("Guest")

回到熟悉的 Java • 抽象資料型態 • 命令式風格 • 可變動的變數與物件 • 那麼… 以上純屬娛樂？

回到熟悉的 Java • 來當一下外貌協會… map(list(1, 2, 3, 4, 5), x -> x + 1) filter(list(1, 2, 3, 4, 5), x -> x > 3) reduce(list(1, 2, 3, 4, 5), (r, x) -> r + x, 0) • 若有群聰明的傢伙已經寫好這些呢？… int sum = names.stream() .filter(s -> s.length() < 3) .map(s -> s.length()) .reduce(0, (sum, len) -> sum + len);

• 既然他們寫好這些了，細節你怎麼會知道？ – 延遲（Laziness） int sum = blocks.stream() .filter(b -> b.getColor() == BLUE) .map(b -> b.getWeight()) .reduce(0, (sum, len) -> sum + len); – 捷徑（short-circuiting） Block blueBlock = blocks.stream() .filter(b -> b.getColor() == BLUE) .findFirst().orElse(new Block(BLUE)); – 平行化 int sum = blocks.parallel() .filter(b -> b.getColor() == BLUE) .map(b -> b.getWeight()) .sum(); – 共用資料結構

回到熟悉的 Java • 現在許多語言都是多重典範（Paradigm） • 即便 Java 是… – 抽象資料型態 – 命令式風格 – 可變動的變數與物件 • 還是可以適當取用函數式特性… • 你有辦法駕馭這高級的特性嗎？

回到熟悉的 Java • 還記得右邊這本書？ – 第一章 Customer 中 statement 方法，如果將其中變數都設成 final 會如何？

命令式與函數式 • 函數式的特性、訓練與思考只是為了… – 得到乾淨的程式碼 – 培養對重複流程的敏感度 – 能夠將問題分解為子問題 • 命令式不也就是需要這些東西嗎？ So … Why Functional Programming matters?

延伸閱讀 • http://caterpillar.onlyfun.net/Gossip/Programme r/index.html – 程式語言的特性本質（四）往數學方向抽象化的函數程式設計 – 物件導向語言中的一級函式 – List處理模式 – 抽象資料型態與代數資料型態 – 不可變動性帶來的思維轉換 • http://www.javaworld.com.tw/roller/caterpillar/c ategory/%E6%8A%80%E8%A1%93 – 命令式至函數式隨記（一） ~ （六）

感謝 Orz 林信良 http://openhome.cc caterpillar@openhome.cc

Java 開發者的函數式程式設計

More Related Content

What's hot

Similar to Java 開發者的函數式程式設計

More from Justin Lin

Java 開發者的函數式程式設計