狠狠撸

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

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

議程
? 前情提要
? 初探函数程式设计
? 代数资料型态
? List 處理模式
? 不可变动特性
? 回到熟悉的 Java

前情提要

doc.openhome.cc

議程
? 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) {
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) {
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

? 從左邊開始折紙…

+

1
2 3 4 5

? 一折…

+

3
3 4 5

? 二折…

+

6
4 5

? 三折…

+

10
5

? 四折…


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
? 抽象資料型態
? 命令式風格
? 可變動的變數與物件
? 那麼…

以上純屬娛樂？

? 來當一下外貌協會…
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()
.findFirst().orElse(new Block(BLUE));

– 平行化
int sum = blocks.parallel()
.map(b -> b.getWeight())
.sum();

– 共用資料結構

? 現在許多語言都是多重典範（Paradigm）
? 即便 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 開發者的函數式程式設計

Recommended

More Related Content

What's hot (20)

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

More from Justin Lin (20)

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