FP 之 Higher Order Function

歸納出 HOF 常用的 4 種 Pattern

Higher Order Function (HOF) 可以說是 FP 的精華，就算是目前主流 OOP，也大都接受了 HOF 概念，但實務上要活用 HOF 並不容易，需要時間與訓練，本文整理出實務上最常使用 HOF 的 4 種 Pattern，讓大家更容易運用在日常開發中。

Version

C# 7.2

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

Definition

Higher Order Function

  • 以 function 作為 function 的 input
  • 以 function 作為 function 的 outpt
  • 符合以上其中之一條件就算 Higer Order Function，簡稱 HOF

在 C# 中，最典型的 HOF 就是 LINQ，如最常用的 Select()、Where() 就是 HOF。

本文將以 HOF 稱呼 Higher Order Function

實務上的應用

HOF 在實務上可歸納出以下 4 種 Pattern：

  • Inversion of Control

  • Adapter Function

  • Function Factory

  • To Avoid Duplication

Inversion of Control

Inversion of Control

原本由高階模組決定 控制流程，改成由 低階模組 決定 控制流程，高階模組只決定 實作部分

可將 控制流程 寫成 Library 或 Framework，實現 Separation of Concerns (關注點分離)：低階模組關注於 控制流程，而高階模組專心於 實作部分

HOF 目的在實現 Inversion of Control

以 LINQ 的 Where() 為例 (相當於 FP 的 Filter()) 

1
2
3
4
5
6
7
8
9
10
public static IEnumerable<T> Where<T>(this IEnumerable<T> data, Func<T, bool> predicate)
{
    foreach(T iter in data)
    {
        if (predicate(iter))
        {
            yield return iter;
        }
    }
}

低階模組 LINQ 的 Where 決定了整個 控制流程，包含 foreach 與 if， 高階模組只決定 predicate 的 實作部分，這就是 Inversion of Control。

hof000

1
2
3
4
5
6
class Cache<T> where T : class
{
    public T Get(Guid id) => ...
        
    public T Get(Guid id, Func<T> onMiss) => Get(id) ?? onMiss();
}

若可由 Guid 對 Cache 抓資料，若有資料則從 Cache 傳回，若沒資料則執行高階模組提供的 function。

我們可發現低階模組 Cache 決定 控制流程，高階模組則提供 onMiss function 的實作，可能是複雜的演算法計算，也可能是實際從資料庫抓資料。

HOF 最常使用的場景就是為了實現 Inversion of Control。

IoC 與 DIP (Dependency Inversion Principle 依賴反轉原則) 並不一樣，IoC 強調的是 控制流程 的反轉，而 DIP 強調的是藉由 interface 達到 依賴 的反轉

Adapter Function

Adapter Function

HOF 的目的在於改變 function 的 Signature

1
2
int divide(int x, int y) => x / y;
var result = divide(10, 2); // 5

原本 divide() 的 被除數 是 x，除數 是 y。

因為需求改變，被除數 改成 y，而 除數 改成 x，也就是 Signature 會改變，argument 會對調。

當然可以直接修改 code，基於 開放封閉原則，且這也是常見的需求，決定將此功能 一般化，將寫一個 function 來處理。

1
2
static Func<T2, T1, R> SwapArgs<T1, T2, R>(this Func<T1, T2, R> f)
    => (t2, t1) => f(t1, t2);

SwapArgs() 回傳一個新的 function，其 argument 由原本的 (t1, t2) 改成 (t2, t1)。

1
2
var divideBy = divide.SwapArgs();
var result = divideBy(2, 10); // 5
  • 在 OOP 中，若 Interface 不同，我們會使用 Adapter Pattern，將 interface 加以轉換
  • 在 FP 中，Function Signature 就是 Interface，若 Signature 不同，我們可使用 HOF 加以轉換，也稱為 Adapter Function

Function Factory

Function Factory

HOF 的目的就是建立新的 function

1
2
3
var data = Enumerable.Range(1, 10)
                     .Where(x => x % 2 == 0);
// [2, 4, 6, 8, 10]

目前只能找出 偶數，也就是 除以 2 整除。

若我們想讓功能更 一般化，能找出 除以 n 整除的資料。

1
2
3
Func<int, bool> isMod(int n) => x => x % n == 0;
var data1 = Enumerable.Range(1, 10).Where(isMod(2)); // 2, 4, 6, 8, 10
var data2 = Enumerable.Range(1, 10).Where(isMod(3)); // 3, 6, 9

isMod() HOF 不只更 一般化，可讀性 也更高。

isMod() HOF 目的並不是回傳 data，而是回傳 Where() 所需要的 function。

hof001

To Avoid Duplication

To Avoid Duplication

HOF 的目的在抽出程式碼共用部分

1
2
3
4
5
6
7
8
9
10
11
12
13
int Foo1(Func<int, int> f1, ...)
{
    ...
    var x = f1(...);
    ...
}

int Foo2(Func<int, int> f2, ...)
{
    ...
    var x = f2(...);
    ...
}

實務上常會發現不同 function，前面 setup 部分都相同，最後 teardown 部分也相同，只有中間 body 部分不同，這種時機就很適合使用 HOF，將共用部分抽出來。

將 Setup / Teardown 抽成共用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
using Dapper;

public class DbLogger
{
    string connString;
    
    public void CreateLog(LogMessage logMessage)
    {
        using (var conn = new SqlConnection(connString))
        {
            conn.Open();
            conn.Execute("sp_create_log", logMessage, CommandType.StoredProcedure);
        }
    }
    
    public IEnumerable<LogMessage> GetLogs(DateTime since)
    {
        using (var conn = new SqlConnection(connString))
        {
            conn.Open();
            conn.Query<LogMessage>(@"SELECT * FROM [Logs] WHERE [Timestamp] > @since", new {since = since});
        }
    }
}

我們可以發現 CreateLog() 與 GetLogs() 在 using 部份有重複，因此可以建立 HOF 將共用部分抽出來。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
using System;
using System.Data;
using System.Data.SqlClient;

public static class ConnectionHelper
{
    public static R Connect<R>(string connString, Func<IDbConnection, R> f)
    {
        using (var conn = new SqlConnection(connString))
        {
            conn.Open();
            return f(conn);
        }
    }
}

建立 ConnectionHelper.Connect() HOF，將 CreateLog() 與 GetLogs() 共用部分抽出來。

1
2
3
4
5
6
7
8
9
10
11
12
13
using Dapper;
using static ConnectionHelper;

public class DbLogger
{
    string connString;
    
    public void CreateLog(LogMessage logMessage)
        => Connect(connString, c => c.Execute("sp_create_log", logMessage, CommandType.StoredProcedure));
    
    public IEnumerable<LogMessage> GetLogs(DateTime since)
        => Connect(connString, c => c.Query<LogMessage>(@"SELECT * FROM [Logs] WHERE [Timestamp] > @since", new {since = since}))
}

抽出共用到 ConnectionHelper 之後，DbLogger 就不再有程式碼重複的部分。

實務上常將程式碼中 setup 與 teardown 部分抽成 HOF 共用

將 using 重構成 HOF

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
using System;
using System.Data;
using System.Data.SqlClient;

public class static class ConnectionHelper
{
    public static R Connect<R>(string connString, Func<IDbConnection, R> f)
    {
        using (var conn = new SqlConnection(connString))
        {
            conn.Open();
            return f(conn);
        }
    }
}

using 為 C# 內建的 statement，其實仔細一看，using 也是在做 setup 與 teardown 的事情：

  • Setup : 獲得 IDisposable resource
  • Body : 執行 {} 內的程式碼
  • Teardown：呼叫 Dispose() 釋放 resource

我們可以也可以比照將 foreach statement 重構成 ForEach() function，將 using statement 重構成 Using() function。

1
2
3
4
5
6
7
8
9
10
11
12
using System;

namespace LaYumba.Functional
{
    public static class F
    {
        public static R Using<TDisp, R>(TDisp disposable, Func<TDisp, R> f) where TDisp : IDisposable
        {
            using(disposable) return f(disposable);
        }
    }
}

將 Using() 建立在自己的 Functional Library 內。

1
2
3
4
5
6
7
using static LaYumba.Functional.F;

public static class ConnectionHelper
{
    public static R Connect<R>(string connString, Func<IDbConnection, R> f)
        => Using(new SqlConnection(connStr), conn => { conn.Open(); return f(conn); });
}

將 using 由 statement 重構成 Using() function 後，有幾個優點 :

  • Connect() 程式碼更加簡潔，可以使用 Expression Body
  • Using() 是 function，不是 statement，因此能夠再與其他 function 作 compose

HOF 的優點與缺點

優點

  • Conciseness : 使用 function 後，能夠再與其他 function 作 compose，幾乎都是一行就能解決，這也是為什麼 C# 要全面提供 Expression Body
  • Avoid Duplication : Setup 與 teardown 的邏輯不再重複
  • Separation of Concerns : ConnectionHelper 關注 connection 管理；而 DbLogger 關注於 log 相關邏輯

缺點
hof002

  • HOF 會使得 call stack 增加，可能會對效能有所影響，不過這是 CPU 層級，差異只是在幾個 clock cycle，所以可以忽略不計
  • 由於 call stack 的增加，debug 會比較複雜

不過 HOF 所帶給我們的優點，仍然是一個值得投資 trade off。

Conclusion

  • HOF 已經是算是目前所有程式語言都能接受的觀念，儘管是 OOP，也都能夠接受 HOF
  • 過度使用 HOF 反而會使得 code 過度抽象化而難以理解，記得要以 可讀性 為前提，適當地使用 HOF
  • HOF 雖然可能造成 call stack 增加而難以 debug，但 HOF 所帶來的優點更多，仍然值得投資

Reference

Enrico Buonanno, Functional Programming in C#

2018-08-19
▲