FP 之 Yield 與 Lazy Evaluation

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

Contents

Version
Composable Function
Imperative
Lazy Evaluation
使用 LINQ
使用時機
Conclusion
Sample Code

為了使 function 重複使用能力更高，我們會盡量將 function 寫成 composable function，也因為如此，function 之間不斷地建立 data，且每個 function 又必須各自執行 for loop，這些都是執行效能殺手，而 Yield 與 Lazy Evaluation 讓我們優雅的解決這兩大難題。

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

很多人對於 FP 的 Chainable 有兩點疑慮：

Function 之間不斷的傳遞 data，則必須在記憶體建立一份新 data，這將大幅影響執行效能
每個 function 都要再重新執行一次 for loop，這將大幅影響執行效能

也由於這兩個因素，雖然 FP 更為優雅，因為效能因素，很多人對 FP 採取懷疑態度。

但 FP 引進 Lazy Evaluation 之後，這兩個疑慮都將獲得解決。

Imperative

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 行

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() ，則結果如預期為 6 與 9。

17 行

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，執行一次 foreach loop，並將 mapper() 結果新增至 List，最後再 return List。

這是典型 Imperative 常用手法。

30 行

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，執行一次 foreach loop，再根據 predicate() 篩選後的結果新增至 List，最後再 return List。

也一樣是 Imperative 常用手法。

yield000

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

目前的 Map() 與 Filter()，已經達成 Composable Function 的要求，只是執行效率並不好：

Map() 與 Filter() 都要不斷建立新的 List
Map() 與 Filter() 都要各自再跑一次 foreach loop

Lazy Evaluation

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 行

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 行

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：Lazy Evaluation 使 Function 之間不需傳遞 data，因此也不用建立 data，省下建立 data 時間與記憶體
直執行一次 Loop：Imperative 方式每個 funtion 都要自己執行 Loop，影響執行效能，但 Lazy Evaluation 只有一次 loop

使用 LINQ

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

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

使用時機

當 FP 寫 Higher Order Function 時，由於要不斷的將 data 傳給下一個 Higher Order Function，此時就是適合使用 yield 與 Lazy Evaluation，避免 function 間的不斷建立 data 與多次 loop 影響執行效能

Conclusion

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

Sample Code

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