現代C++函數式編程

xiaofaf 9年前發布 | 39K 次閱讀函數式編程 C/C++開發 C/C++

概述

函數式編程是一種編程范式，它有下面的一些特征：

函數是一等公民，可以像數據一樣傳來傳去。
高階函數
遞歸
pipeline
惰性求值
柯里化
偏應用函數

C++98/03中的函數對象，和C++11中的Lambda表達式、std::function和std::bind讓C++的函數式編程變得容易。我們可以利用C++11/14里的新特性來實現高階函數、鏈式調用、惰性求值和柯理化等函數式編程特性。本文將通過一些典型示例來講解如何使用現代C++來實現函數式編程。

高階函數和pipeline的表現形式

高階函數就是參數為函數或返回值為函數的函數，經典的高階函數就是map、filter、fold和compose函數，比如Scala中高階函數：

    numbers.map((i: Int) => i * 2)
 
    對列表中的每個元素應用一個函數，返回應用后的元素所組成的列表。

filter

    numbers.filter((i: Int) => i % 2 == 0)
 
    移除任何對傳入函數計算結果為false的元素。

fold

    numbers.fold(0) { (z, i) =>
    a + i
    }
 
    將一個初始值和一個二元函數的結果累加起來。

compose

    valfComposeG = f _ compose g _
    fComposeG("x")
 
    組合其它函數形成一個新函數f(g(x))。

上面的例子中，有的是參數為函數，有的是參數和返回值都是函數。高階函數不僅語義上更加抽象泛化，還能實現“函數是一等公民”，將函數像data一樣傳來傳去或者組合，非常靈活。其中，compose還可以實現惰性求值，compose的返回結果是一個函數，我們可以保存起來，在后面需要的時候調用。

pipeline把一組函數放到一個數組或是列表中，然后把數據傳給這個列表。數據就像一個鏈條一樣順序地被各個函數所操作，最終得到我們想要的結果。它的設計哲學就是讓每個功能就做一件事，并把這件事做到極致，軟件或程序的拼裝會變得更為簡單和直觀。

Scala中的鏈式調用是這樣的：

    s(x) = (1 to x) |> filter (x => x % 2 == 0) |> map (x => x * 2)

用法和Unix Shell的管道操作比較像，|前面的數據或函數作為|后面函數的輸入，順序執行直到最后一個函數。

這種管道方式的函數調用讓邏輯看起來更加清晰明了，也非常靈活，允許你將多個高階函數自由組合成一個鏈條，同時還可以保存起來實現惰性求值。現代C++實現這種pipeline也是比較容易的，下面來講解如何充分借助C++11/14的新特性來實現這些高階函數和pipeline。

實現pipeline的關鍵技術

根據前面介紹的pipeline表現形式，可以把pipeline分解為幾部分：高階函數，惰性求值，運算符|、柯里化和pipeline，把這幾部分實現之后就可以組成一個完整的pipeline了。下面來分別介紹它們的實現技術。

高階函數

函數式編程的核心就是函數，它是一等公民，最靈活的函數就是高階函數，現代C++的算法中已經有很多高階函數了，比如for_each, transform.

std::vector<int> vec{1,2,3,4,5,6,7,8,9}
//接受一個打印的Lambda表達式
std::for_each(vec.begin(), vec.end(), [](auto i){ std::cout<<i<<std::endl; });
//接受一個轉換的Lambda表達式
transform(vec.begin(), vec.end(), vec.begin(), [](int i){ return i*i; });

這些高階函數不僅可以接受Lambda表達式，還能接受std::function、函數對象、普通的全局函數，很靈活。需要注意的是，普通的全局函數在pipeline時存在局限性，因為它不像函數對象一樣可以保存起來延遲調用，所以我們需要一個方法將普通的函數轉換為函數對象。std::bind也可以將函數轉化為函數對象，但是bind不夠通用，使用的時候它只能綁定有限的參數，如果函數本身就是可變參數的就無法bind了，所以，這個函數對象必須是泛化的，類似于這樣：

    class universal_functor 
    {
    public: 
        template <typename... Args> autooperator()(Args&&... args) const ->decltype(globle_func(std::forward<Args>(args)...))
        {
            return globle_func(std::forward<Args>(args)...);
        }
    };

上面的函數對象內部包裝了一個普通函數的調用，當函數調用的時候實際上會調用普通函數globle_func，但是這個代碼不通用，它無法用于其他的函數。為了讓這個轉換變得通用，我們可以借助一個宏來實現function到functor的轉換。

    #define define_functor_type(func_name) class tfn_##func_name {\
    public: template <typename... Args> autooperator()(Args&&... args) const ->decltype(func_name(std::forward<Args>(args)...))\
    { return func_name(std::forward<Args>(args)...); } }
    
    //test code
    int add(int a, int b)
    {
        return a + b;
    }
    int add_one(int a) 
    { 
    return 1 + a; 
    }
    
    define_functor_type(add);
    define_functor_type(add_one);
    
    int main()
    {
        tnf_addadd_functor;
        add_functor(1, 2); //result is 3
    
        tfn_add_oneadd_one_functor;
        add_one_functor(1); //result is 2
    
        return 0;
    }

我們先定義了一個宏，這個宏根據參數來生成一個可變參數的函數對象，這個函數對象的類型名為tfn_加普通函數的函數名，之所以要加一個前綴tfn_，是為了避免類型名和函數名重名。define_functor_type宏只是定義了一個函數對象的類型，用起來略感不便，還可以再簡化一下，讓使用更方便。我們可以再定義一個宏來生成轉換后的函數對象：

    #define make_globle_functor(NAME, F) const auto NAME = define_functor_type(F);
    //test code
    make_globle_functor(fn_add, add);
    make_globle_functor(fn_add_one, add_one);
    
    int main()
    {
        fn_add(1, 2);
        fn_add_one(1);
    
        return 0;  
    }

make_globle_functor生成了一個可以直接使用的全局函數對象，使用起來更方便了。用這個方法就可以將普通函數轉成pipeline中的函數對象了。接下來我們來探討實現惰性求值的關鍵技術。

惰性求值

惰性求值是將求值運算延遲到需要值時候進行，通常的做法是將函數或函數的參數保存起來，在需要的時候才調用函數或者將保存的參數傳入函數實現調用。現代C++里已經提供可以保存起來的函數對象和lambda表達式，因此需要解決的問題是如何將參數保存起來，然后在需要的時候傳給函數實現調用。我們可以借助std::tuple、type_traits和可變模版參數來實現目標。

    template<typename F, size_t... I, typename ... Args>
    inline autotuple_apply_impl(const F& f, const std::index_sequence<I...>&, const std::tuple<Args...>& tp)
    {
        return f(std::get<I>(tp)...);
    }
    
    template<typename F, typename ... Args>
    inline autotuple_apply(const F& f, const std::tuple<Args...>& tp) -> decltype(f(std::declval<Args>()...))
    {
        return tuple_apply_impl(f, std::make_index_sequence<sizeof... (Args)>{}, tp);
    }
    
    int main()
    {
        //test code
        auto f = [](int x, int y, int z) { return x + y - z; };
        //將函數調用需要的參數保存到tuple中
        autoparams = make_tuple(1, 2, 3);
        
        //將保存的參數傳給函數f，實現函數調用
        autoresult = tuple_apply(f, params); //result is 0
        
        return 0;
    }

上面的測試代碼中，我們先把參數保存到一個tuple中，然后在需要的時候將參數和函數f傳入tuple_apply，最終實現了f函數的調用。tuple_apply實現了一個“魔法”將tuple變成了函數的參數，來看看這個“魔法”具體是怎么實現的。

tuple_apply_impl實現的關鍵是在于可變模版參數的展開，可變模版參數的展開又借助了std::index_sequence

運算符operator|

pipeline的一個主要表現形式是通過運算符|來將data和函數分隔開或者將函數和函數組成一個鏈條，比如像下面的unix shell命令：

    psauwwx | awk '{print $2}' | sort -n | xargsecho

C++實現類似的調用可以通過重載運算符來實現，下面是data和函數通過|連接的實現代碼：

    template<typename T, class F>
    autooperator|(T&& param, const F& f) -> decltype(f(std::forward<T>(param)))
    {
        return f(std::forward<T>(param));
    }
    //test code
    autoadd_one = [](auto a) { return 1 + a; };
    autoresult = 2 | add_one; //result is 3

除了data和函數通過|連接之外，還需要實現函數和函數通過|連接，我們通過可變參數來實現：

    template<typename... FNs, typename F>
    inline autooperator|(fn_chain<FNs...> && chain, F&& f)
    {
        return chain.add(std::forward<F>(f));
    }
    
    //test code
    autochain = fn_chain<>() | (filter >> [](auto i) { return i % 2 == 0; }) | ucount | uprint;

其中fn_chain是一個可以接受任意個函數的函數對象，它的實現將在后面介紹。通過|運算符重載我們可以實現類似于unix shell的pipeline表現形式。

柯里化

函數式編程中比較靈活的一個地方就是柯里化(currying)，柯里化是把多個參數的函數變換成單參數的函數，并返回一個新函數，這個新函數處理剩下的參數。以Scala的柯里化為例：

未柯里化的函數

    defadd(x:Int, y:Int) = x + y
    
    add(1, 2)  // 3
    add(7, 3)  // 10

柯里化之后

    defadd(x:Int) = (y:Int) => x + y
    
    add(1)(2)  // 3
    add(7)(3)  // 10

currying之后add(1)(2)等價于add(1,2)，這種currying默認是從左到右的，如果希望從右到左呢，然而大部分編程語言沒有實現更靈活的curring。C++11里面的std::bind可以實現currying，但要實現向左或向右靈活的currying比較困難，可以借助tuple和前面介紹的tuple_apply來實現一個更靈活的currying函數對象。

    template<typename F, typename Before = std::tuple<>, typename After = std::tuple<>>
    class curry_functor {
    private:
        F f_;                      ///< main functor
        Beforebefore_;            ///< curryed arguments
        Afterafter_;              ///< curryed arguments
    
    public:
    
        curry_functor(F && f) : f_(std::forward<F>(f)), before_(std::tuple<>()), after_(std::tuple<>()) {}
        curry_functor(const F & f, const Before & before, const After & after) : f_(f), before_(before), after_(after) {}
    
        template <typename... Args>
        autooperator()(Args... args) const -> decltype(tuple_apply(f_, std::tuple_cat(before_, make_tuple(args...), after_)))
        {
            // execute via tuple
            return tuple_apply(f_, std::tuple_cat(before_, make_tuple(std::forward<Args>(args)...), after_));
        }
    
        // currying from left to right
        template <typename T>
        autocurry_before(T && param) const
        {
            using RealBefore = decltype(std::tuple_cat(before_, std::make_tuple(param)));
            return curry_functor<F, RealBefore, After>(f_, std::tuple_cat(before_, std::make_tuple(std::forward<T>(param))), after_);
        }
        // currying from righ to left
        template <typename T>
        autocurry_after(T && param) const
        {
            using RealAfter = decltype(std::tuple_cat(after_, std::make_tuple(param)));
            return curry_functor<F, Before, RealAfter>(f_, before_, std::tuple_cat(after_, std::make_tuple(std::forward<T>(param))));
        }
    };
    
    template <typename F>
    autofn_to_curry_functor(F && f)
    {
        return curry_functor<F>(std::forward<F>(f));
    }
    
    //test code
    void test_count()
    {
        auto f = [](int x, int y, int z) { return x + y - z; };
        autofn = fn_to_curry_functor(f);
    
        autoresult = fn.curry_before(1)(2, 3); //0
        result = fn.curry_before(1).curry_before(2)(3); //0
        result = fn.curry_before(1).curry_before(2).curry_before(3)(); //0
    
        result = fn.curry_before(1).curry_after(2).curry_before(3)(); //2
        result = fn.curry_after(1).curry_after(2).curry_before(2)();  //1
    }

從測試代碼中可以看到這個currying函數對象，既可以從左邊currying又可以從右邊currying，非常靈活。不過使用上還不太方便，沒有fn(1)(2)(3)這樣方便，我們可以通過運算符重載來簡化書寫，由于C++標準中不允許重載全局的operater()符，并且operater()符無法區分到底是從左邊還是從右邊currying，所以我們選擇重載<<和>>操作符來分別表示從左至右currying和從右至左currying。

    // currying from left to right
    template<typename UF, typename Arg>
    autooperator<<(const UF & f, Arg && arg) -> decltype(f.template curry_before<Arg>(std::forward<Arg>(arg)))
    {
        return f.template curry_before<Arg>(std::forward<Arg>(arg));
    }
    
    // currying from right to left
    template<typename UF, typename Arg>
    autooperator>>(const UF & f, Arg && arg) -> decltype(f.template curry_after<Arg>(std::forward<Arg>(arg)))
    {
        return f.template curry_after<Arg>(std::forward<Arg>(arg));
    }

有了這兩個重載運算符，測試代碼可以寫得更簡潔了。

    void test_currying()
    {
        auto f = [](int x, int y, int z) { return x + y - z; };
        autofn = fn_to_curry_functor(f);
    
        autoresult = (fn << 1)(2, 3); //0
        result = (fn << 1 << 2)(3); //0
        result = (fn << 1 << 2 << 3)(); //0
    
        result = (fn << 1 >> 2 << 3)(); //2
        result = (fn >> 1 >> 2 << 3)(); //1
    }

curry_functor利用了tuple的特性，內部有兩個空的tuple，一個用來保存left currying的參數，一個用來保存right currying的參數，不斷地currying時，通過tuple_cat把新currying的參數保存到tuple中，最后調用的時候將tuple成員和參數組成一個最終的tuple，然后通過tuple_apply實現調用。有了前面這些基礎設施之后我們實現pipeline也是水到渠成。

pipeline

通過運算符|重載，我們可以實現一個簡單的pipeline：

    template<typename T, class F>
    autooperator|(T&& param, const F& f) -> decltype(f(std::forward<T>(param)))
    {
        return f(std::forward<T>(param));
    }
    //test code
    void test_pipe()
    {
    autof1 = [](int x) { return x + 3; };
        autof2 = [](int x) { return x * 2; };
        autof3 = [](int x) { return (double)x / 2.0; };
        autof4 = [](double x) { std::stringstreamss; ss << x; return ss.str(); };
        autof5 = [](string s) { return "Result: " + s; };
        autoresult = 2|f1|f2|f3|f4|f5; //Result: 5
    }

這個簡單的pipeline雖然可以實現管道方式的鏈式計算，但是它只是將data和函數通過|連接起來了，還沒有實現函數和函數的連接，并且是立即計算的，沒有實現延遲計算。因此我們還需要實現通過|連接函數，從而實現靈活的pipeline。我們可以通過一個function chain來接受任意個函數并組成一個函數鏈。利用可變模版參數、tuple和type_traits就可以實現了。

    template <typename... FNs>
    class fn_chain {
    private:
        const std::tuple<FNs...> functions_;
        const static size_tTUPLE_SIZE = sizeof...(FNs);
    
        template<typename Arg, std::size_t I>
        autocall_impl(Arg&& arg, const std::index_sequence<I>&) const ->decltype(std::get<I>(functions_)(std::forward<Arg>(arg)))
        {
            return std::get<I>(functions_)(std::forward<Arg>(arg));
        }
    
        template<typename Arg, std::size_t I, std::size_t... Is>
        autocall_impl(Arg&& arg, const std::index_sequence<I, Is...>&) const ->decltype(call_impl(std::get<I>(functions_)(std::forward<Arg>(arg)), std::index_sequence<Is...>{}))
        {
            return call_impl(std::get<I>(functions_)(std::forward<Arg>(arg)), std::index_sequence<Is...>{});
        }
    
        template<typename Arg>
        autocall(Arg&& arg) const-> decltype(call_impl(std::forward<Arg>(arg), std::make_index_sequence<sizeof...(FNs)>{}))
        {
            return call_impl(std::forward<Arg>(arg), std::make_index_sequence<sizeof...(FNs)>{});
        }
    
    public:
        fn_chain() : functions_(std::tuple<>()) {}
        fn_chain(std::tuple<FNs...> functions) : functions_(functions) {}
    
        // add function into chain
        template< typename F >
        inline autoadd(const F& f) const
        {
            return fn_chain<FNs..., F>(std::tuple_cat(functions_, std::make_tuple(f)));
        }
    
        // call whole functional chain
        template <typename Arg>
        inline autooperator()(Arg&& arg) const -> decltype(call(std::forward<Arg>(arg)))
        {
            return call(std::forward<Arg>(arg));
        }
    };
    
    // pipe function into functional chain via | operator
    template<typename... FNs, typename F>
    inline autooperator|(fn_chain<FNs...> && chain, F&& f)
    {
        return chain.add(std::forward<F>(f));
    }
    
    #define tfn_chain fn_chain<>()
    
    //test code
    void test_pipe()
    {
    autof1 = [](int x) { return x + 3; };
        autof2 = [](int x) { return x * 2; };
        autof3 = [](int x) { return (double)x / 2.0; };
        autof4 = [](double x) { std::stringstreamss; ss << x; return ss.str(); };
        autof5 = [](string s) { return "Result: " + s; };
        autocompose_fn = tfn_chain|f1|f2|f3|f4|f5; //compose a chain
        compose_fn(2); // Result: 5
    }

測試代碼中用一個fn_chain和運算符|將所有的函數組合成了一個函數鏈，在需要的時候調用，從而實現了惰性求值。

fn_chain的實現思路是這樣的：內部有一個std::tuple

    template<typename Arg, std::size_t I>
    autocall_impl(Arg&& arg, const std::index_sequence<I>&) const ->decltype(std::get<I>(functions_)(std::forward<Arg>(arg)))
    {
        return std::get<I>(functions_)(std::forward<Arg>(arg));
    }
 
    template<typename Arg, std::size_t I, std::size_t... Is>
    autocall_impl(Arg&& arg, const std::index_sequence<I, Is...>&) const ->decltype(call_impl(std::get<I>(functions_)(std::forward<Arg>(arg)), std::index_sequence<Is...>{}))
    {
        return call_impl(std::get<I>(functions_)(std::forward<Arg>(arg)), std::index_sequence<Is...>{});
    }

在調用call_impl的過程中，將std::index_sequence不斷展開，先從tuple中獲取第I個function，然后調用獲得第I個function的執行結果，將這個執行結果作為下次調用的參數，不斷地遞歸調用，直到最后一個函數完成調用為止，返回最終的鏈式調用的結果。

至此我們實現具備惰性求值、高階函數和currying特性的完整的pipeline，有了這個pipeline，我們可以實現經典的流式計算和AOP，接下來我們來看看如何利用pipeline來實現流式的mapreduce和靈活的AOP。

實現一個pipeline形式的mapreduce和AOP

前面的pipeline已經可以實現鏈式調用了，要實現pipeline形式的mapreduce關鍵就是實現map、filter和reduce等高階函數。下面是它們的具體實現：

    // MAP
    template <typename T, typename... TArgs, template <typename...>class C, typename F>
    autofn_map(const C<T, TArgs...>& container, const F& f) -> C<decltype(f(std::declval<T>()))>
    {
        using resultType = decltype(f(std::declval<T>()));
        C<resultType> result;
        for (const auto& item : container)
            result.push_back(f(item));
        return result;
    }
    
    // REDUCE (FOLD)
    template <typename TResult, typename T, typename... TArgs, template <typename...>class C, typename F>
    TResultfn_reduce(const C<T, TArgs...>& container, const TResult& startValue, const F& f)
    {
        TResultresult = startValue;
        for (const auto& item : container)
            result = f(result, item);
        return result;
    }
    
    // FILTER
    template <typename T, typename... TArgs, template <typename...>class C, typename F>
    C<T, TArgs...> fn_filter(const C<T, TArgs...>& container, const F& f)
    {
        C<T, TArgs...> result;
        for (const auto& item : container)
            if (f(item))
                result.push_back(item);
        return result;
    }

這些高階函數還需要轉換成支持currying的functor，前面我們已經定義了一個普通的函數對象轉換為柯里化的函數對象的方法：

    template <typename F>
    autofn_to_curry_functor(F && f)
    {
        return curry_functor<F>(std::forward<F>(f));
    }

通過下面這個宏讓currying functor用起來更簡潔：

    #define make_globle_curry_functor(NAME, F) define_functor_type(F); const auto NAME = fn_to_curry_functor(tfn_##F());
    
    make_globle_curry_functor(map, fn_map);
    make_globle_curry_functor(reduce, fn_reduce);
    make_globle_curry_functor(filter, fn_filter);

我們定義了map、reduce和filter支持柯里化的三個全局函數對象，接下來我們就可以把它們組成一個pipeline了。

    void test_pipe()
    {
        //test map reduce
        vector<string> slist = { "one", "two", "three" };
    
        slist | (map >> [](auto s) { return s.size(); })
            | (reduce >> 0 >> [](auto a, auto b) { return a + b; })
            | [](auto a) { cout << a << endl; };
    
        //test chain, lazy eval
        autochain = tfn_chain | (map >> [](auto s) { return s.size(); })
            | (reduce >> 0 >> [](auto a, auto b) { return a + b; })
            | ([](int a) { std::cout << a << std::endl; });
    
        slist | chain;
    }

上面的例子實現了pipeline的mapreduce，這個pipeline支持currying還可以任意組合，非常方便和靈活。

有了這個pipeline，實現靈活的AOP也是很容易的：

    struct person
    {
        personget_person_by_id(int id)
        {
            this->id = id;
            return *this;
        }
    
        int id;
        std::string name;
    };
    void test_aop()
    {
    const person& p = { 20, "tom" };
        autofunc = std::bind(&person::get_person_by_id, &p, std::placeholders::_1); 
        autoaspect = tfn_chain | ([](int id) { cout << "before"; return id + 1; })
            | func
            | ([](const person& p) { cout << "after" << endl; });
    
        aspect(1);
    }

上面的測試例子中，核心邏輯是func函數，我們可以在func之前或之后插入切面邏輯，切面邏輯可以不斷地加到鏈條前面或者后面，實現很巧妙，使用很常靈活。

總結

本文通過介紹函數式編程的概念入手，分析了函數式編程的表現形式和特性，最終通過現代C++的新特性和一些模版元技巧實現了一個非常靈活的pipeline，展示了現代C++實現函數式編程的方法和技巧，同時也提現了現代C++的強大威力和無限的可能性。文中完整的代碼可以從我的 GitHub 上查看。

本文的代碼和思路參考和借鑒了這篇文章，在此表示感謝。

注：本文是作者發表在程序員8月刊上的文章，轉載請注明出處。

來自：http://purecpp.org/?p=904

本文由用戶 xiaofaf 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。

轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。

本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！

本文地址：http://www.baiduhome.net/lib/view/open1471952749919.html

函數式編程 C/C++開發 C/C++