C++ で C# の delegate っぽいものも作ってみた

こないだ event 風のものを作ってみたけど、もう一ひねりしたら delegate っぽいものも作れた。

template<typename T>
class Delegate;

template<typename R, typename... A>
class Delegate<R(A...)> {
private:
    std::function<R(A...)> mFunc;
public:
    Delegate(std::function<R(A...)> func) : mFunc(func) {}
    template<typename C, typename T>
    Delegate(C* pObj, T func) {
        mFunc = [=](A... args) { std::mem_fn(func)(pObj, args...); };
    }
public:
    void operator()(A... args) {
        mFunc(std::forward<A>(args)...); // 修正
    }
};

ｅｖｅｎｔ と組み合わせるとこんな感じで使える。

class EventManager {
public:
    typedef Delegate<void(const std::string&)> TestEventHndlr;
    Event<TestEventHndlr> TestEvent;
    void InvokeTestEvent() {
        TestEvent("This is TestEvent. > ");
    }
};

class EventHandler {
public:
    void Hndlr(const std::string& msg) {
        std::cout << msg << "I'm a member function." << std::endl;
    }
};

void print_msg(const std::string& msg) {
    std::cout << msg << "I'm a static function." << std::endl;
}

int main()
{
    EventManager manager;
    EventHandler hndlr;
    manager.TestEvent += EventManager::TestEventHndlr([](const std::string& msg) {
        std::cout << msg << "I'm a lambda function." << std::endl;
    });
    manager.TestEvent += EventManager::TestEventHndlr(print_msg);
    manager.TestEvent += EventManager::TestEventHndlr(&hndlr, &EventHandler::Hndlr);
    manager.InvokeTestEvent();
    return 0;
}

※追記
unique_ptr を使おうとしたらハマったので Delegate を一部修正。
Event の方は複数のハンドラを登録できるようにしているのでもともと unique_ptr は適さない。
どうしても使いたければハンドラを一つしか登録できないイベントクラスを別途作る必要があるが、それよりはイベントハンドラ側にメモリ管理をさせないようにデータ構造を見直した方が健全かなぁ。。。

C++0x のラムダ式と可変長テンプレートで C# っぽいイベント処理

世の中便利になったものね～。
これでコールバックを多用した非同期処理がだいぶ書きやすくなりそう。

どうしてもメンバ関数は一旦ラムダ式で包んであげる必要があるので、デリゲートの仕組みも作れると完璧なんだが・・・

#include <iostream>
#include <list>
#include <functional>
#include <string>

template<typename T>
class Event {
private:
    std::list<T> mHndlrs;
public:
    void operator+=(T hndlr) {
        mHndlrs.push_back(hndlr);
    }
    template<typename... A>
    void operator()(A... args) {
        for (auto it = mHndlrs.begin(); it != mHndlrs.end(); it++) {
            (*it)(args...);
        }
    }
};

class EventManager {
public:
    Event<std::function<void(const std::string&)> > TestEvent;
    void InvokeTestEvent() {
        TestEvent("This is TestEvent. > ");
    }
};

class EventHandler {
public:
    void Hndlr(const std::string& msg) {
       std::cout << msg << "I'm a member function." << std::endl;
    }
};

void print_msg(const std::string& msg) {
    std::cout << msg << "I'm a static function." << std::endl;
}

int main()
{
    EventManager manager;
    EventHandler hndlr;
    manager.TestEvent += [](const std::string& msg) {
        std::cout << msg << "I'm a lambda function." << std::endl;
    };
    manager.TestEvent += print_msg;
    manager.TestEvent += [&](const std::string& msg) {
       hndlr.Hndlr(msg);
    };
    manager.InvokeTestEvent();
    return 0;
}

JavaScript で Sudoku を解いてみる (3)

前回までで、問題と条件が記述できたので、後は例によって解けば良い。

今回はモナドを利用したおかげで条件の記述がそのまま条件をチェックするコードになるので、ソルバは非常にシンプルに書ける。

        function solve(question, conditions, iter) {
            var result;
            if(iter === undefined) iter = 0;
            else if(iter >= question.length) return;
            var answer = [];
            question[iter].selectEach(function() {
                result = conditions();
                if(result === undefined)
                    answer = answer.concat(solve(question, conditions, iter+1));
                else if(result === true) {
                    answer.push(question.map(function(tile) { return tile.get(); }));
                }
            });
            return answer;
        }

        var Question = Cells.reduce(function(prev, row) {
            return prev.concat(row);
        }, []);

        var Answer = solve(Question, Condition);

ここまでシンプルに書けると、もはやソルバは要らないんじゃないかと思えてきて、問題に吸収させて、問題生成時に問題に対応するソルバを生成するようにもしてみた。

        function Question(items) {
            this.Solve = items.reduce(function(prev, item) {
                return function(condition) {
                    var answer = [];
                    item.selectEach(function() {
                        result = condition();
                        if(result === undefined)
                            answer = answer.concat(prev(condition));
                        else if(result === true) {
                            answer.push(items.map(function(tile) { return tile.get(); }));
                        }
                    });
                    return answer;
                }
            }, function() { return []; });
        }

        var Answer = (new Question(Cells.reduce(function(prev, row) {
            return prev.concat(row);
        }))).Solve(Condition);

実際に解いてみると、簡単な問題なら一瞬で解けるが、難易度が上がると試行回数が跳ね上がってむちゃくちゃ時間がかかるようになる。
この辺はスクリプトの限界なのか、それとも工夫すればもっと速くなるのか。。。

JavaScript で Sudoku を解いてみる (2)

前回の続きで、塗り分けの時にモナド的に書きたいなと言っていたところを、無い知恵を絞ってモナドもどきを作ってみた。

        var Result = {
            False: {
                bind: function() {
                    return this;
                },
                get: function() {
                    return false;
                }
            },
            True: {
                bind: function(f) {
                    return f();
                },
                get: function() {
                    return true;
                }
            },
            Undefined: {
                bind: function(f) {
                    var result = f();
                    if(result.get() === false) {
                        return result;
                    }
                    return Result.Undefined;
                },
                get: function() {
                    return undefined;
                }
            }
        }

これを使うと、「与えられた要素が全て互いに異なる」という条件はこう書ける。
モナドを使いつつも、あまり関数型っぽくない書き方だが、実行効率を踏まえつつハイブリッドなやり方と言うことで

        function AllNotEqual() {
            return allNotEqual(arguments, arguments.length-2);
        }
        function allNotEqual(items, iter) {
            var result = (function(j) {
                var callee = arguments.callee;
                if(j <= iter + 1) return NotEqual(items[iter], items[j]);
                return NotEqual(items[iter], items[j]).bind(function() { return callee(j-1); });
            })(items.length - 1);
            if(iter <= 0) {
                return result;
            }
            return result.bind(function() { return allNotEqual(items, iter-1); });
        }
        function NotEqual(x, y) {
            var tmp_x = x.get(), tmp_y = y.get();
            if(tmp_x === undefined || tmp_y === undefined)
                return Result.Undefined;
            if(tmp_x != tmp_y)
                return Result.True;
            return Result.False;
        }

Sudoku の条件である、「各行、各列、各3x3のブロックで同じ数字を使わない」は、関数型言語の勉強の時に作った do 記法もどきを利用してこう書ける。
ちとながいが、よく見れば単にルールをべた書きしただけの記述。

        var MonaDo = function(fs) {
            var monado = function(funcs) {
                if(funcs.length > 1) {
                    var inner = monado(funcs.slice(1));
                    return function(a) {
                        return funcs[0](a).bind(inner);
                    }
                }
                return funcs[0];
            }
            return monado(fs)();
        }

        function RowNotEqual(cells, row) {
            return AllNotEqual.apply(this, cells[row]);
        }
        function ColNotEqual(cells, col) {
            return AllNotEqual.apply(this, cells.map(function(row) {
                return row[col];
            }));
        }
        function BlkNotEqual(cells, row, col) {
            return AllNotEqual(
                cells[row][col],  cells[row][col+1],  cells[row][col+2],
                cells[row+1][col],cells[row+1][col+1],cells[row+1][col+2],
                cells[row+2][col],cells[row+2][col+1],cells[row+2][col+2]);
        }
        var Condition = function() {
            return MonaDo([
                function() {return RowNotEqual(Cells, 0); },
                function() {return RowNotEqual(Cells, 1); },
                function() {return RowNotEqual(Cells, 2); },
                function() {return RowNotEqual(Cells, 3); },
                function() {return RowNotEqual(Cells, 4); },
                function() {return RowNotEqual(Cells, 5); },
                function() {return RowNotEqual(Cells, 6); },
                function() {return RowNotEqual(Cells, 7); },
                function() {return RowNotEqual(Cells, 8); },
                function() {return ColNotEqual(Cells, 0); },
                function() {return ColNotEqual(Cells, 1); },
                function() {return ColNotEqual(Cells, 2); },
                function() {return ColNotEqual(Cells, 3); },
                function() {return ColNotEqual(Cells, 4); },
                function() {return ColNotEqual(Cells, 5); },
                function() {return ColNotEqual(Cells, 6); },
                function() {return ColNotEqual(Cells, 7); },
                function() {return ColNotEqual(Cells, 8); },
                function() {return BlkNotEqual(Cells, 0, 0); },
                function() {return BlkNotEqual(Cells, 0, 3); },
                function() {return BlkNotEqual(Cells, 0, 6); },
                function() {return BlkNotEqual(Cells, 3, 0); },
                function() {return BlkNotEqual(Cells, 3, 3); },
                function() {return BlkNotEqual(Cells, 3, 6); },
                function() {return BlkNotEqual(Cells, 6, 0); },
                function() {return BlkNotEqual(Cells, 6, 3); },
                function() {return BlkNotEqual(Cells, 6, 6); }
            ]).get()
        };

JavaScript で Sudoku を解いてみる (1)

こないだ塗り分け問題を解く JavaScript を書いてみたが、同じ原理で Sudoku も解けるんじゃないかと思ってコードを改良しつつやってみた。

Sudoku の場合は初期状態で値が決まっているセルと決まっていないセルがあるので、これを表現するために、Obvious と Ambiguous という二つのクラスを作成した。

        function Ambiguous(candidates) {
            this.candidates = candidates;
            this.selected = undefined;
        }
        Ambiguous.prototype = {
            get: function() {
                return this.selected;
            },
            selectEach: function(callback) {
                this.candidates.forEach(function(item) {
                    this.selected = item;
                    callback();
                }.bind(this));
                this.selected = undefined;
            },
        }
        function Obvious(value) {
            this.value = value;
        }
        Obvious.prototype = {
            get: function() {
                return this.value;
            },
            selectEach: function(callback) {
                callback();
            }
        }

長くなるのでヘルパーを使いつつ、どっかから探してきた Sudoku の問題を表現するとこうなる。

        var Nine = [1, 2, 3, 4, 5, 6, 7, 8, 9];
        function createRow(args) {
            return args.map(function(item) {
                if(Array.isArray(item)) return new Ambiguous(item);
                return new Obvious(item);
            });
        }
        var Cells = [
            createRow([Nine, Nine,    8, Nine,    9, Nine, Nine, Nine, Nine]),
            createRow([   9, Nine, Nine, Nine,    3, Nine, Nine, Nine,    1]),
            createRow([   6,    2, Nine, Nine,    4,    7, Nine,    8, Nine]),
            createRow([Nine, Nine,    7, Nine, Nine, Nine,    1,    9, Nine]),
            createRow([   1,    3, Nine,    4,    7, Nine,    2,    5,    8]),
            createRow([   5, Nine, Nine,    8,    2, Nine,    3,    6, Nine]),
            createRow([   3,    6,    1,    7, Nine,    4,    8,    2, Nine]),
            createRow([Nine,    5,    2,    9,    1, Nine,    4,    7,    6]),
            createRow([Nine,    9,    4,    6, Nine, Nine,    5, Nine,    3])
        ];

インデントは気にしない