第十三號艦隊
0%

Transduer in C++

Posted on Edited on In

Transducer原先是在Clojure 1.7被提出的新觀念，由於覺得這觀念實在很有趣。看了幾篇文章之後，打算寫些東西。試著一步一步前進，加深自己印象。

What is Transducer

Transducer 是遊 Transfrom 和 reducer 兩個字合成出來的，而
– Transform: 轉換，由 A 變成 B
– Reducer: 接受輸入和先前的狀態，產生一個新的狀態

從一個簡單範例開始

1
2
3
4
5
6
7
8
9
vector<int> calc(const vector<int> &vec)
{
        vector<int> result;
        for (const auto &v : vec) {
                if (v % 2 == 0)
                        result.push_back(v / 2);
        }
        return result;
}

這段程式很簡單就知道他在做什麼了，不過他還是有一些圈點
例如新增了一個條件, 不能修改原有條件。
只能寫個95%相像的程式，例如

1
2
3
4
5
6
7
8
9
vector<int> calc2(const vector<int> &vec)
{
        vector<int> result;
        for (const auto &v : vec) {
                if (v > 5)
                        result.push_back(v * v);
        }
        return result;
}

雖然一樣能夠解決問題，不過寫久了也是會覺得枯燥乏味。
這邊就缺少了Functional programming中的composability
接著用Functional Progrmaming的觀點來看這問題

來點Functional Programming

先來個C++版的Map和Filter吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
template <template <typename...> class C, typename T, typename ...TArgs,  typename Fn>
auto Map(Fn fn, const C<T, TArgs...> &container) {
        C<T, TArgs...> result;
        for (const auto &item : container)
                result.push_back(fn(item));
        return result;
}
template <typename In, typename Out, typename Pred>
Out filter(In first, In last, Out out, Pred pred) {
        for (; first != last; ++first)
                if (pred(*first))
                        *out++ = *first;
        return out;
}

重新構建我們的函數

1
2
3
4
5
6
vector<int> calc(const vector<int> &vec)
{
        auto div2 = [](auto v) { return v / 2; };
        auto isEven = [](auto v) { return v % 2 == 0; };
        return Map(div2, Filter(isEven, vec));
}

這下子可以用組合來看這個問題了，不過這方法的問題也顯而易見。仙不論C++中間產物的影響

  • 原先的Solution只要一次Lopp就結束了
  • 這方法需要兩次Loop，一次Filter，一次Map
    這就是改造的地方，因此Reducer上場了

    Reduce

    1
    2
    3
    4
    5
    6
    7
    template <template <typename...> class C, typename T, typename ...TArgs,
            typename S, typename Rf>
    auto reduce(const C<T, TArgs...> &container, S state, Rf step) {
            for (const auto &c : container)
                    state = step(state, c);
            return state;
    }
    這個救跟std::accumulate作法差不多。
    加上一個helper function
    1
    2
    3
    4
    auto concat = [](auto result, auto input) {
            result.push_back(input);
            return result;
    };
    上面的Map跟Filter能用Reduce重新實作了
    Map部分
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    auto mapping = [](auto fn) {
            return [=](auto step) {
                    return [=](auto s, auto ...ins) {
                            return step(s, fn(ins...));
                    };
            };
    };
    template <template <typename...> class C, typename T, typename ...TArgs,  typename Fn>
    auto Map(Fn fn, const C<T, TArgs...> &container) {
            using retType = C<T, TArgs...>;

            return reduce(container, retType(), mapping(fn)(concat));
    }
    Filter部分
    1
    2
    3
    4
    5
    6
    7
    auto filtering = [](auto pred) {
            return [=](auto step) {
                    return [=](auto s, auto ...ins) {
                            return pred(ins...) ? step(s, ins...) : s;
                    };
            };
    };
    Compose
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    auto compose = [](auto f) {
            return [=](auto g) {
                    return [=](auto ...ins) {
                            return f(g(ins...));
                    };
            };
    };
    template <template <typename...> class C, typename T, typename ...TArgs,  typename Pred>
    auto Filter(Pred pred, const C<T, TArgs...> &container) {
            using retType = C<T, TArgs...>;
            return reduce(container, retType(), filtering(pred)(concat));
    }
    我們可以甩開 Map 跟 Filter, 重新打造函數，這下只用到 Reduce，太神奇了
    1
    2
    3
    4
    5
    6
    vector<int> calc(const vector<int> &vec)
    {
            auto div2 = [](auto v) { return v / 2; };
            auto isEven = [](auto v) { return v % 2 == 0; };
            return reduce(vec, vector<int>(), filtering(isEven)(mapping(div2)(concat)));
    }
    加上Compose的話，威力就更大了

    Compose

    定義一個簡單的Compose實作
    1
    2
    3
    4
    5
    auto compose = [](auto f, auto g) {
            return [=](auto x) {
                    return f(g(x));
            };
    };
    重新實作我們的 calc function
    1
    2
    3
    4
    5
    6
    7
    vector<int> calc(const vector<int> &vec)
    {
            auto div2 = [](auto v) { return v / 2; };
            auto isEven = [](auto v) { return v % 2 == 0; };
            auto comp = compose(filtering(isEven), mapping(div2));
            return reduce(vec, vector<int>(), comp(concat));
    }
    一切就是這麼神奇

Reference

– CSP and transducers in JavaScript
– Transducers From Clojure to C++
– transducers in C++ 14