Functional Programming 簡介 (使用 C#)

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

Version

C# 7.2

Introduction

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

Function

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

Mathematical Function

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

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

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

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

int func(int x)
{
    return 2 * x + 1;
}

int
int x

Pure Function : Codomain 只與 Domain 相關。

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

Programming Function

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 就怎麼用

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 行

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

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

12 行

Range(1, 3)

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

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

13 行

.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 行

.ToList()
.ForEach(WriteLine);

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

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

No State Mutation

不要修改 data

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

Imperative

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 行

var result = new List<int>();

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

23 行

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

根據 條件 不斷修改變數。

31 行

result.Sort();

直接修改 result 資料排序。

Functional

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 行

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

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。

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。

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 行

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

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

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

想想原本 Where + OrderBy 的 Imperative + Side Effect 寫法，若要支援多核心，程式碼要改多少 ?

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 就是要你不斷改暫存器與記憶體)，很多人無法接受而視為 邪教 ，一直到最近才鹹魚翻身：

殺手級

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 語言。

Functional CSharp

C# 3 與 LINQ

• LINQ 本質上就是 FP，並不是使用 OOP 技術

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

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 行

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 行

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 行

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 行

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

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

namespace System
{
    public delegate int Comparison<T> (T x, Y x);
}

使用 Delegate 宣告 Comparison 型別。

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 行

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

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

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

第 10 行

list.Sort(alphabetically);

將 alphabetically delegate 傳入 List.Sort() 。

Func & Action

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

delegate Greeting Greeter(Person p);

其實相當於

Func<Person, Greeting>

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

Lambda

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 強大之處

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 :

var frenchFor = new Dictionary<bool, string>
{
    [true]  = "Vari",
    [false] = "Faux"
};

frenchFor[true];

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

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#