Yield 是實現 Lazy Evaluation 最簡單的方式

為了使 function 重複使用能力更高,我們會盡量將 function 寫成 composable function,但也因為如此,我們需要將處理完的 data 傳遞給下一個 function,而 function 之間不斷地傳遞 data,是執行效能殺手;而 YieldLazy Evaluation 讓我們 function 之間不需傳遞 data,大幅提高執行效能。

Version


macOS High Sierra 10.13.6
.NET Core 2.1
C# 7.2
Rider 2018.1.4

Composable Function


一個 function 若要能跟其他 function 完美組合,需達成 4 個條件:

  • Pure : function 不能有 Side Effect
  • Chainable : 也就是 Pipeline,讓 data 以 Dataflow 方式一直流下去
  • General : function 要越 一般化,越 針對性 則越難 Compose 重複使用
  • Shape-preserving : funciton 要能保持原本資料結構,才能在相同型別下繼續 Compose 與 Pipeline

也因為 Chainable 與 Shape-preserving,我們需要在 function 之間不斷的傳遞 data,則必須在記憶體建立一份 data,然後將 data 複製一份到記憶體其他地方,這會大幅影響執行效能,這也是 FP 一開始最被人詬病之處。

但 FP 引進 Lazy Evaluation 觀念之後,data 要不斷複製的問題得到解決;在 C# 2.0 是以 yield 實現 Lazy Evaluation。

無 Lazy Evaluation


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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
using System;
using System.Collections.Generic;
using static System.Console;

namespace ConsoleApp
{
static class Program
{
static void Main(string[] args)
{

IEnumerable<int> nums = new List<int> {1, 2, 3};
nums.Map(x => x * 3)
.Filter(x => x % 2 == 1)
.Each(WriteLine);
}

private static IEnumerable<T> Map<T>(this IEnumerable<T> list, Func<T, T> mapper)
{
List<T> result = new List<T>();

foreach (var iter in list)
{
WriteLine("Map : " + iter);
result.Add(mapper(iter));
}

return result;
}

private static IEnumerable<T> Filter<T>(this IEnumerable<T> list, Func<T, bool> predicate)
{
List<T> result = new List<T>();

foreach (var iter in list)
{
WriteLine("Filter : " + iter);
if (predicate(iter))
{
result.Add(iter);
}
}

return result;
}

private static void Each<T>(this IEnumerable<T> list, Action<T> action)
{
foreach (var iter in list)
{
WriteLine("Each : " + iter);
action(iter);
}
}
}
}

第 9 行

1
2
3
4
5
6
7
8
9
static void Main(string[] args)
{

IEnumerable<int> nums = new List<int> {1, 2, 3};
nums.Map(x => x * 3)
.Filter(x => x % 2 == 1)
.Each(WriteLine);
}
// 6
// 9

假設我們自行實現 Map()Filter() ,則結果如預期為 69

17 行

1
2
3
4
5
6
7
8
9
10
11
12
private static IEnumerable<T> Map<T>(this IEnumerable<T> list, Func<T, T> mapper)
{
List<T> result = new List<T>();

foreach (var iter in list)
{
WriteLine("Map : " + iter);
result.Add(mapper(iter));
}

return result;
}

我們會先建立一個新的 List,並將 mapper() 結果新增至 List,最後再 return List

這是典型 Imperative 常用手法。

30 行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
private static IEnumerable<T> Filter<T>(this IEnumerable<T> list, Func<T, bool> predicate)
{
List<T> result = new List<T>();

foreach (var iter in list)
{
WriteLine("Filter : " + iter);
if (predicate(iter))
{
result.Add(iter);
}
}

return result;
}

也一樣建立一個新 List,根據 predicate() 篩選後的結果新增至 List,最後再 return List

也一樣是 Imperative 常用手法。

yield000

執行結果也如預期,先執行完 Map(),再執行 Filter(),最後 Each()

目前的 Map()Filter(),已經達成 Composable Function 的要求,只是執行效率並不好,因為 Map()Filter() 都要不斷建立新的 List,並傳回 List,這些操作都不是在 CPU,而是在記憶體,因此會是效能瓶頸。

有 Lazy Evaluation


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
38
39
40
41
42
43
44
45
46
47
using System;
using System.Collections.Generic;
using static System.Console;

namespace ConsoleApp
{
static class Program
{
static void Main(string[] args)
{

IEnumerable<int> nums = new List<int> {1, 2, 3};
nums.Map(x => x * 3)
.Filter(x => x % 2 == 1)
.Each(WriteLine);
}

private static IEnumerable<T> Map<T>(this IEnumerable<T> list, Func<T, T> mapper)
{
foreach (var iter in list)
{
WriteLine("Map : " + iter);
yield return mapper(iter);
}
}

private static IEnumerable<T> Filter<T>(this IEnumerable<T> list, Func<T, bool> predicate)
{
foreach (var iter in list)
{
WriteLine("Filter : " + iter);
if (predicate(iter))
{
yield return iter;
}
}
}

private static void Each<T>(this IEnumerable<T> list, Action<T> action)
{
foreach (var iter in list)
{
WriteLine("Each : " + iter);
action(iter);
}
}
}
}

17 行

1
2
3
4
5
6
7
8
private static IEnumerable<T> Map<T>(this IEnumerable<T> list, Func<T, T> mapper)
{
foreach (var iter in list)
{
WriteLine("Map : " + iter);
yield return mapper(iter);
}
}

List 拿掉,將新增至 List 重構成 yield

26 行

1
2
3
4
5
6
7
8
9
10
11
private static IEnumerable<T> Filter<T>(this IEnumerable<T> list, Func<T, bool> predicate)
{
foreach (var iter in list)
{
WriteLine("Filter : " + iter);
if (predicate(iter))
{
yield return iter;
}
}
}

List 拿掉,將新增至 List 重構成 yield

yield001

執行結果完全一樣,但執行順序已經完全不一樣。

我們發現執行順序變成每個數字各自執行 Map() -> Filter() -> Each(),而不是原本整個List 全部一起 Map() -> Filter() -> Each()

當使用 yield 時,Map()Filter() 並未執行,而是等 Each() 的 Side Effect : WriteLine() 執行時,才去呼叫 Filter(),然後 Filter() 去呼叫 Map()Map() 才真正開始執行,Map() 執行完再立即將結果傳給 Filter(),最後再傳給 Each() 執行WriteLine() 達成需求。

這就是所謂 Lazy Evaluation,function 的所有計算,都因為 Side Effect 發動後才會開始。

Lazy Evaluation 有兩大優點 :

  • 省下傳遞 data 時間 : Function 之間不需傳遞 data,只有在 Side Effect 發動後才會計算,省下 data 建立與傳遞時間
  • 節省記憶體 : 若 data 量龐大,且能夠執行的記憶體有限,則 Lazy Evaluation 就非常有用,因為完全不需事先在記憶體內建立 data

使用 LINQ


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

namespace ConsoleApp
{
static class Program
{
static void Main(string[] args)
{

IEnumerable<int> nums = new List<int> {1, 2, 3};
nums.Select(x => x * 3)
.Where(x => x % 2 == 1)
.ToList()
.ForEach(WriteLine);
}
}
}

可再將程式碼重構成 LINQ,Map() 相當於 LINQ 的 Select(),而 Filter() 相當於 Where()

yield002

  1. 事實上 LINQ 內部就是使用 yield 實現,這也是 LINQ 高效的原因

使用時機


  • 當 FP 寫 Higher Order Function 時,由於要不斷的將 data 傳給下一個 Higher Order Function,此時就是適合使用 yield,避免 function 間的傳遞 data 影響執行效能

Conclusion


  • yield 是眾多程式語言都具備的基礎功能,PHP 也有 yield,在 ECMAScript 2015 則稱為 Generator,但大部分人都採用 Imperative 方式寫程式,很少人會使用 Lazy Evaluation 思考;事實上如 Haskell,所有 function 都是 Lazy Evaluation,這對 FP 的執行效能有非常大的幫助
  • 是否覺得 Lazy Evaluation 很有 Agile 的味道呢 ? XDD

Sample Code


完整的範例可以在我的 GitHub 上找到

2018-08-18