Functional Programming 簡介

以大家的老朋友 C# 談 FP

這幾年由於 Reactive Programming 興起，使得 FP 這古老的 Programming Paradigm 又成為顯學，FP 大都使用 JavaScript、Haskell … 等偏 FP 語言闡述，很少人使用 C# 來談 FP，本系列將使用大家的老朋友 C#，帶領大家一步一步進入 FP 世界。

Version

C# 7.2

本文為 Funtional Programming in C# 一書第一章的讀後心得

Introduction

  • FP 是一種 Programming Paradigm，不是 Design Pattern 也不是 Framework，更不是 Language
  • 是一種以 function 為中心的 思考方式 與 程式風格
  • 有別於目前主流 Imperative、OOP，所以被稱為邪教 ?

Imperative

以 command 或 statement 方式，一行一行的執行程式

Function

在討論什麼是 Functional Programming 之前，我們先來定義什麼是 Function :

Mathematical Function

fp000

在數學裡，function 就是 x 與 y = f(x) 的對應關係。

f(x) 結果只與 x 的輸入有關，不會其他任何東西相關。

fp001

  • Domain : 所有的 x 稱為 定義域
  • Codomain : 所有 可能 的 f(x) 稱為 對應域
  • Range : 所有 實際 的 f(x) 稱為 值域

這些都不是什麼高深的數學，在國一的代數我們就會了

1
2
3
4
int func(int x)
{
    return 2 * x + 1;
}
  • int : 為 Codomain
  • int x : 為 Domain

Pure Function : Codomain 只與 Domain 相關。

Pure Function 就是 Mathematical Function 在程式語言的實踐

Programming Function

1
2
3
4
5
6
7
8
int z = 1;
int w = 0;

int func(int x)
{
    w = 3;
    return 2 * x + z + 1;
}

func() 可以讀取 func() 外面的 z，甚至可以改寫 func() 外部的 w，這就是所謂的 Side Effect。

因為讀取與寫入 function 的外部變數造成 Side Effect，使得變數改變的 時機 變得很重要，也就是所謂的 Race Condition。

OS 恐龍書花了很多的篇幅都在解決 Race Condition (Lock、Mutex ….)。

Functional Programming

把 function 當成 data 使用，並避免 State Mutation

  • Function as data (把 function 當成 data 使用)
  • No state mutation (不要修改 data，只要修改資料，就需擔心可能 Race Condition)

Function as Data

比 function 當成 data 使用

  • 能把 function 當 input、把 function 當 return
  • 能將 function 指定給變數
  • 能將 function 存進 Collection

以前 data 能怎麼用，function 就怎麼用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
using static System.Console;
using static System.Linq.Enumerable;

namespace ConsoleApp
{
    class Program
    {
        static void Main(string[] args)
        {
            string triple(int x) => (x * 3).ToString();

            Range(1, 3)
                .Select(triple)
                .ToList()
                .ForEach(WriteLine);
        }
    }
}
// 3
// 6
// 9

10 行

1
string triple(int x) => (x * 3).ToString();

使用 C# 7 的 Local Function 宣告 triple() 。

12 行

1
Range(1, 3)

使用 Range() 建立 IEnumerable<int>，因為有 using static System.Linq.Enumerable;

using static 在 FP 建議使用，會讓 code 更精簡

13 行

1
.Select(triple)

Select() 就是 FP 的 Map()，為 IEnumerable 的 Extension Method。

與 Map() 一樣，Select() 並沒有修改原本的 Range(1, 3)，而是 return 新的 IEnumerable。

triple 為 function，但如 data 般傳進 Select()，Select() 也就是所謂的 Higher Order Function。

在 LINQ 的 . ，若使用 Extension Method，則不是 OOP 的 Method，而是 FP 的 Pipeline

14 行

1
2
.ToList()
.ForEach(WriteLine);

因為 List 才有 ForEach()，所以要先轉成 List。

直接使用 WriteLine，因為有 using static System.Console;。

No State Mutation

不要修改 data

7, 6, 1 只取 奇數，並且 由小到大 排序。

Imperative

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
using System;
using System.Collections.Generic;

namespace ConsoleApp
{
    class Program
    {
        private static void Main()
        {
            var original = new List<int> {7, 6, 1};
            var result = GetOddsByAsc(original);

            foreach (var iter in result)
            {
                Console.WriteLine(iter);
            }
        }

        private static IEnumerable<int> GetOddsByAsc(IEnumerable<int> original)
        {
            var result = new List<int>();

            foreach (var iter in original)
            {
                if (iter % 2 == 1)
                {
                    result.Add(iter);
                }
            }

            result.Sort();
            return result;
        }
    }
}
// 1
// 7

21 行

1
var result = new List<int>();

Imperative 典型寫法會先建立一個 result 變數。

23 行

1
2
3
4
5
6
7
foreach (var iter in original)
{
    if (iter % 2 == 1)
    {
        result.Add(iter);
    }
}

根據 條件 不斷修改變數。

31 行

1
result.Sort();

直接修改 result 資料排序。

Functional

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
using System.Collections.Generic;
using System.Linq;
using static System.Console;

namespace ConsoleApp
{
    class Program
    {
        static void Main()
        {
            var original = new List<int> {7, 6, 1};
            var result = GetOddsByAsc(original);

            result.ForEach(WriteLine);
        }

        private static IEnumerable<int> GetOddsByAsc(IEnumerable<int> original)
        {
            bool isOdd(int x) => x % 2 == 1;
            int asc(int x) => x;
            
            return original
                .Where(isOdd)
                .OrderBy(asc);
        }
    }
}
// 1
// 7

22 行

1
2
3
return original
    .Where(isOdd)
    .OrderBy(asc);

original 經由 pipeline 方式，先經過 Where() 找出 奇數，最後再以 asc 排序。

Code 就類似 講話，看不到實作細節，可讀性高。

不需要建立 result 暫存變數，也沒有修改 original 與 result，從頭到尾都沒有修改 data，這就是所謂的 No State Mutation，而是每次 pipeline 都建立新的 data。

  • LINQ 的 Where() 就是 FP 的 filter()，
  • LINQ 的 OrderBy() 就是 FP 的 sort()

Parallel Computation

1
2
3
4
5
6
7
8
9
10
11
using static System.Linq.Enumerable
using static System.Console;

var nums = Range(-10000, 20001).Reverse().ToList();
// => [10000, 9999, ... , -9999, -10000]
Action task1 = () => WriteLine(nums.Sum());
Action task2 = () => { nums.Sort(); WriteLine(nums.Sum()); };

Parallel.Invoke(task1, task2);
// prints: 92332970
//         0

由於 Sort 會直接去改 nums，造成了 Race Condition。

1
2
3
4
5
6
7
8
9
10
11
using static System.Linq.Enumerable
using static System.Console;

var nums = Range(-10000, 20001).Reverse().ToList();
// => [10000, 9999, ... , -9999, -10000]
Action task1 = () => WriteLine(nums.Sum());
Action task2 = () => WriteLine(nums.OrderBy(x => x).Sum());

Parallel.Invoke(task1, task2);
// prints: 0
//         0

task2 並不會去修改 nums，因此不會 Race Condition。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
using System.Collections.Generic;
using System.Linq;
using static System.Console;

namespace ConsoleApp
{
    class Program
    {
        static void Main()
        {
            var original = new List<int> {7, 6, 1};
            var result = GetOddsByAsc(original);

            result.ForEach(WriteLine);
        }

        private static IEnumerable<int> GetOddsByAsc(IEnumerable<int> original)
        {
            int asc(int x) => x;
            bool isOdd(int x) => x % 2 == 1;

            return original
                .AsParallel()
                .Where(isOdd)
                .OrderBy(asc);
        }
    }
}

22 行

1
2
3
4
return original
    .AsParallel()
    .Where(isOdd)
    .OrderBy(asc);

只要加上 AsParallel() 之後，完全無痛升級多核心。

因為 Where(isOdd) 與 OrderBy(asc) 都是 Pure Function，沒有 Side Effect，也就沒有 Race Condition，因此可以放心使用多核心平行運算。

FP vs. OOP

OOP 是大家習慣的編程方式，FP 究竟有哪些觀念與 OOP 不同呢 ?

Encapsulation

  • OOP : data 與 logic 包在 class 內
  • FP : data 與 logic 分家，data 就是 data，logic 就是 function，不使用 class

State Mutation

  • OOP : 繼續使用 Imperative 修改 state
  • FP : No State Mutation => Immutable => No Side Effect => No Race Condition => Pure Function => Dataflow => Pipeline (其實都在講同一件事情)

大部分人最難突破的 FP 點在此，這與傳統程式思維差異很大，為什麼不能改 data 呢 ?

Modularity

  • OOP : 以 class 為單位
  • FP : 以 function 為單元

Dependency

  • OOP : Dependency Injection
  • FP : Higher Order Function (Function Injection)

Loose Coupling

  • OOP : 使用 Interface
  • FP : Function Signature 就是 interface，使用 Function Composition / Function Pipeline

SOLID

SRP

  • OOP : Class 與 Method 要單一職責
  • FP : Module 與 Function 要單一職責

OCP

  • OOP : Interface，使用 Object Composition
  • FP : Function Signature 就是 interface，使用 Function Composition

LSP

  • OOP : 有限度的繼承
  • FP : N/A

ISP

  • OOP : Interface 要盡量小
  • FP : Interface 小到極致就變成 function

DIP

  • OOP : Dependency Injection
  • FP : Higher Order Function

SOLID 原則在 OOP 與 FP 都適用，不過 OOP 與 FP 在實現手法並不一樣，OOP 以 class 實現，FP 以 function 實現

FP 鹹魚翻身

FP 其實是比 OOP 更古老的技術，LISP 早在 1958 年就問世，而 Smalltalk 則在 1972 年發表，但因為 FP 基於數學，且強調 No State Mutation，與 CPU 設計理念不合 (CPU 就是要你不斷改暫存器與記憶體)，很多人無法接受而視為 邪教，一直到最近才鹹魚翻身：

  1. 硬體單核心時脈出現瓶頸，CPU 已經無法做出時脈超過 5GHz 以上，因此單執行緒程式速度也面臨瓶頸，但隨著半導體製程進步，單位面積可以塞入更多電晶體，因此 CPU 可以放進更多核心，但 Imperative 寫法依賴 Side Effect，使得多核心很難發揮，但 FP 沒有 Side Effect，很容易多核心平行運算，發揮多核心威力
  2. Side Effect 寫法很難單元測試，因為不保證每次的結果都ㄧ樣，但 FP 的 Pure Function 很適合單元測試
  3. OOP 的 Object Compostion 需依賴 Interface，容易造成 interface 滿天飛與 Over Design，但 FP 的 Function Compostion 不需要額外 interface，只要求你使用 Dataflow 思考，並使用 Pure Function 避免 Side Effect 即可
  4. Reactive Programming 並不適合使用 OOP，但卻異常適合 FP，這使得 FP 找到了 殺手級 應用

C# 適合 FP 嗎 ?

回想 FP 定義 :

  1. Function as Data
  2. No State Mutation

Function as Data

  • C# 從 1.0 就有 Delegate，可以將 function 當成 input 與 output 使用
  • C# 3.0 支援 Lambda，讓 Anonymous Function 更容易實現
  • C# 3.0 支援 Func、Predicate、Action，讓 Anonyoua Delegate 更為方便
  • C# 的 Type Inference 比較弱，必須明確指定 Delegate 或 Func 型別 (不滿意但可接受，希望 C# 對 Type Inference 持續加油)

No State Mutation

  • Primitive Type 只有 string 與 datetime 為 Immutable
  • 由於 C# 是從 Imperative 與 OOP 起家，任何 data 預設都是 Mutable，而不像 FP 語言預設 data 都是 Immutable，需自己加上 readonly
  • 自訂型別預設是 Mutable
  • Collection 預設是 Mutable，但已經提供 Immutable Collection

所以大體上除了 Type Inference 與 Immutable 支援比較不足外，C# 7 算是個準 FP 語言，C# 亦持續朝更完整的 FP 邁進 :

  • Record Type (Immutable 自訂 Type)
  • Algebraic Data Type (適合 DDD)
  • Pattern Matching
  • 更強的 Tuple

C# 8 將會是更成熟的 FP 語言。

C# 對 FP 支援

C# 3 與 LINQ

  • LINQ 本質上就是 FP，並不是使用 OOP 技術
1
2
3
4
5
Enumerable
    .Range(1, 100)
    .Where(i => i % 20 == 0)
    .OrderBy(i => -i)
    .Select(i => $"{i}%")

Where()、OrderBy()、Select() 都以 function 為參數，且並沒有去修改原本的 Enumerable.Range(1, 100)，完全符合 FP 的基本定義 :

  • Function as Data
  • No State Mutation

且 C# 提供了 Lambda，讓我們以更精簡的方式撰寫 Delegate，對於 FP 這種只使用一次的 Anonymous Function 特別有效，這也使得 C# 更適合寫 FP。

不過 C# 社群大都沒發現 LINQ 的 FP 的本質，只有在處理 IEnumerable 與 IQueryable 才會使用 FP，其他 code 又繼續使用 Imperative 與 OOP，並沒有完全發揮 Functional C# 的潛力，也就是 FP 思維其實沒有深入 C# 社群

C# 6、7

C# 6、7 乍看之下沒有提供實質功能，都是 syntax sugar，若以 OOP 角度來看的確如此，但若以 FP 角度，所有的 syntax sugar 都是為了讓 C# 成為更好的 FP 而準備。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
using static System.Math;

public class Circle
{
    public double Radius { get; }
    public double Circumference => PI * 2 * Radius;
    
    public Circle(double radius) => Radius = radius;
    
    public double Area
    {
        get
        {
            double Square(double d) => Pow(d, 2);
            return PI * Square(Radius);
        }
    }
    
    public (double Circumference, double Area) Stats => (Circumference, Area);
}

Using Static

第 1 行

1
2
3
4
5
6
7
8
9
10
using static System.Math;

public double Area
{
    get
    {
        double Square(double d) => Pow(d, 2);
        return PI * Square(Radius);
    }
}

C# 6 的 using static 讓我們可以直接 PI 或 Pow 使用 Math.PI 與 Math.Pow。

Q : 為什麼 using static 對 FP 重要 ?

在 OOP，我們必須建立 object instance，然後才能用 method，主要是因為 OOP 的 instance method 會以 Imperative 與 Side Effect 方式使用 data，也就是 field，因此不同的 object instance 就有不同的 field，正就是 OOP 的 Encapsulation : data 與 logic 合一。

但因為 FP 是 data 與 logic 分家，logic 會以 static method 實現，也沒有 field，因此就不須建立 object instance，因此類似 Math 這種 instance variable 在 FP 就顯得沒有意義且多餘，因為 static method 都是 Pure Function，根本不需要 instance variable。

Immutable Type

第 5 行

1
2
public double Radius { get; }
public Circle(double radius) => Radius = radius;

C# 目前的缺點就是沒有 直接 支援 Immutable 自訂型別，C# 6 透過宣告 getter-only 的 auto-property，compiler 會自動建立 readonly 的 field，且只能透過 constructor 設定其值，達到 No State Mutation 的要求。

Expression Body

第 6 行

1
public double Circumference => PI * 2 * Radius;

Property 可直接使用 Expression Body 語法。

Q : 為什麼 Expression Body 對 FP 重要 ?

因為 FP 很習慣寫 小 property 與 小 function，最後再靠 Function Composition 與 Function Pipeleine 組合起來，為了這種只有一行的 小 function ，還要加上 {}，除了浪費行數，也不符合 FP 的 Lambda 極簡風。

C# 6 一開始只有在 Property 與 Method 支援 Expression Body，但 C# 7 可以在 Constructor、Destructor、Getter 與 Setter 全面使用 Expression Body。

Local Function

12 行

1
2
3
4
5
get
{
    double Square(double d) => Pow(d, 2);
    return PI * Square(Radius);
}

Local Function 使我們在 Method 內可直接建立 function。

Q : 為什麼 Local Function 對 FP 重要 ?

由於 FP 常常需要建立 小 function，最後再 compose 或 pipeline，C# 7 之前只能宣告 Func 型別變數並配合 Lambda，但 Func 寫法可讀性實在不高，這也使的 C# 族群不太願意抽 小 function。

但 Local Function 的可讀性就很高，也符合一般 function 的 syntax，讓我們更願意抽 小 function 來 compose。

Better Tuple

1
public (double Circumference, double Area) Stats => (Circumference, Area);

為了回傳 Tuple 外，還可以對 element 指定有意義的名字，讓 client 使用 Tuple 時有 Intellisense 支援。

Q : 為什麼 Tuple 對 FP 重要 ?

因為 FP 會在 Function Composition 與 Function Pipeline 時，拆很多小 function 實現 Dataflow，而這些 小 function 在傳遞資料時，就會使用 Tuple，但為這種只使用一次的 data 定義自訂型別，又會造成自訂型別滿天飛的問題，但若使用 Tuple 就可避免此問題。

C# 如何實現 Function ?

這裡的 Function 是所謂的 Mathematical Function，也就是 Pure Function。

Static Method

由於 Pure Function 要求 output 只與 input 有關，也就是 Pure Function 沒有 Side Effect，因此會直接使用 Static Method，如 System.Math 一樣，且還可搭配 C# 6 的 using static，讓程式碼更精簡。

Delegate

FP 要求 Function as Data，也就是 Pure Function 會以參數方式傳進其他 function，C# 1.0 function 包成 Delegate 後，以 Delegate 形式傳進其它 function。

Delegate 要求兩個步驟 :

  • 宣告 Delegate 型別
  • 實作符合 Delegate 型別的 function
1
2
3
4
namespace System
{
    public delegate int Comparison<T> (T x, Y x);
}

使用 Delegate 宣告 Comparison 型別。

1
2
3
4
5
6
7
8
9
10
var list = 
    Enumerable
        .Range(1, 10)
        .Select(i => i * 3)
        .ToList();

Comparison<int> alphabetically = 
    (1, r) => l.ToString().CompareTo(r.ToString());

list.Sort(alphabetically);

第 7 行

1
2
Comparison<int> alphabetically = 
    (1, r) => l.ToString().CompareTo(r.ToString());

根據 Comparison delegate 型別定義 alphabetically 變數，以 Lambda 描述 function。

若實作不符合 Delegate 定義，compiler 就會報錯，所以 Delegate 也被稱為 Type-Safe Function Pointer。

第 10 行

1
list.Sort(alphabetically);

將 alphabetically delegate 傳入 List.Sort()。

Func & Action

Delegate 讓我們實現 Function as Data，但對於只使用一次的 Anonymous Delegate 型別，到處宣告 Delegate 就類似 interface 一樣，造成檔案爆炸。

1
delegate Greeting Greeter(Person p);

其實相當於

1
Func<Person, Greeting>

.NET Framework 3 之後，以 Func 與 Action 取代 Custom Delegate

Lambda

1
2
3
4
5
6
7
var list = 
    Enumerable
        .Range(1, 10)
        .Select(i => i * 3)
        .ToList();

list.Sort((1, r) => l.ToString().CompareTo(r.ToString();

不用再宣告 Comparison<T> Delegate，也不用建立 Comparison<T> 的實作，直接以 Lambda 傳入 List.Sort()。

寫 Lambda 時，不用寫型別，compiler 會自動使用 Type Inference 導出參數型別，且會將 Lambda 轉型成 Delegate 型別，判斷是不是符合 List.Sort() 要求

因此 Lamba 雖然寫起來像 弱型別，但絲毫不會影響原本 Delegate 強型別的特性，這就是 Type Inference 強大之處

1
2
3
4
5
6
7
8
var days = Enum.GetValues(typeof(DayOfWeek)).Cast<DayOfWeek>();
// => [Sunday, Monday, Tuesday, Wednesday, Thursday, Friday, Saturday]

IEnumerable<DayOfWeek> daysStartingWith(string pattern)
	=> days.Where(d => d.ToString().StartsWith(pattern));

daysStartingWith("S")
// => [Sunday, Saturday]

不只 JavaScript 有 Closure，事實上 C# 也是有 Closure。

daysStartingWith() 會回傳 function，但傳入的參數 S 會以 Closure 方式存在於回傳的 function。

Dictionary

既然 Pure Function 只與 input 有關，我們甚至可以使用 查表法 的方式實作 function :

1
2
3
4
5
6
7
var frenchFor = new Dictionary<bool, string>
{
    [true]  = "Vari",
    [false] = "Faux"
};

frenchFor[true];

C# 6 提供了新的 Dictionary 初始化語法，甚至可以使用 true 與 false 當 key。

實務上有兩種需求很適合使用 Dictionary

  1. 沒有邏輯可言的 data 轉換
  2. 花時間的運算

Conclusion

  • FP 的 function 指的是 Mathematical Function，也就是 Pure Function，而不是 Programming Function
  • FP 屬於 Paradigm 層次，不是 framework 也不是程式語言，只要語言能支援 First-Class Function，就能以 FP 風格實現，若能支援 Immutable 與 Type Inference 更佳
  • C# 目前已經支援大部分的 FP 功能，隨著 C# 8 的發佈，FP 支援將更為完整

Reference

Math is Fun, Domain, Range and Codomain
Enrico Buonanno, Functional Programming in C#

2018-08-06
▲