「F 代数は Proto で役立つと思います。」 このようにして Bartosz Milewski が私の頭の中に種を蒔き、それが今ではこのブログ記事へと成熟しました。 Bartosz は F 代数に関するブログ記事を書いていたので、私にそれを復習してもらうために、Proto ニンジンをぶら下げました。かみました。
F 代数では、式の評価は再帰とは別のものです。代数は、あるレベルの式ツリーがどのように評価されるかを指定し、残りは カタモルフィズム によって処理されます 、一度書かれ、すべての代数で共有されます。私は怠惰なプログラマーです。私はかなりの数学の吸盤でもあります。だから私は夢中になりました.
Bartosz のコードは Haskell で書かれているので、最初のステップは C++ に移植することでした。この投稿の残りの部分では、私の F 代数コードの C++11 への移植を紹介します。最初に Bartosz の投稿をお読みください。すべてが理解できたら、ここに戻って、これがすべて C++ にどのようにマップされるかを確認してください。
免責事項:これは、F 代数の読みやすい紹介を意図したものではありません。それについては Bartosz のブログを読んでください。
Haskell の ExprF 型
Bartosz は、運転例として単純な式ツリーを使用します。次のようになります:
data ExprF a = Const Int | Add a a | Mul a a type Expr = Fix ExprF
注目すべきは、06
という事実です。 ではない 再帰的;つまり、19
それ自体では実装されていません。それでも彼は、これはツリー データ構造であり、ツリーは再帰的であると主張しています。
答えは、再帰が 26
と呼ばれる型コンストラクターによって外部から提供されることです。 . 37
の場合 は 1 レベルのツリーで、42
は 2 レベルのツリーで、50
無限レベルのツリーです。無限に到達したことをどのように知ることができますか?もう1つがあなたが始めた場所に戻るとき。それは定点です 、および 69
は定点です。パラメータ 78
のアプリケーションを無限に偽装します。 .任意の型コンストラクタ 82
の場合 、タイプ 91
106
の別のアプリケーション 開始した場所に戻ります。 110
の方法を見てみましょう が定義されています。
修正タイプ
124
非再帰シェルから再帰データ構造を作成できます。ハスケルはこちら。 136
を含めます ここでも機能します。
newtype Fix f = Fx (f (Fix f)) unFix :: Fix f -> f (Fix f) unFix (Fx x) = x
ここでは、145
は単項型コンストラクタであり、 157
168
を取るデータコンストラクタです 171
を返します . C++ では、単項型コンストラクターは、1 つのパラメーターを受け取るクラス テンプレートです。 185
の場合、単項クラス テンプレートをパラメーターとして受け取るテンプレートであり、195
207
を返す関数です :
template<template<typename> class F> struct Fix : F<Fix<F>> { explicit Fix(F<Fix<F>> f) : F<Fix<F>>(f) {} }; template<template<typename> class F> Fix<F> Fx(F<Fix<F>> f) { return Fix<F>{f}; } template<template<typename> class F> F<Fix<F>> unFix(Fix<F> f) { return f; }
C++ から、219
であることがわかります。 本当に定点です。 228
233
から継承 .継承は IS-A です 関係なので、246
本当に 250
です . (逆を真と見なすかどうか — つまり、264
278
です —あなたがどれだけ文字通りの精神を持っているかによって異なります。私の目的では、286
関数はそうします。)
ハスケルに戻ります。 Bartosz の 294
の定義で および 301
、次のやや冗長な例のように、任意の深さの式ツリーを作成できます:
testExpr = Fx $ (Fx $ (Fx $ Const 2) `Add` (Fx $ Const 3)) `Mul` (Fx $ Const 4)
しかし、312
を表現する最良の方法は何ですか? C ++で?それは明らかではありません。
C++ の ExprF 型
322
の定義をもう一度見てみましょう
data ExprF a = Const Int | Add a a | Mul a a
これは次のように読むことができます:もし誰かが 332
を与えた場合 、 343
のいずれかを含むことができます 、 350
、または 369
.このどちらかまたは両方の演説は、組合のように聞こえます。 C++11 の無制限共用体を使ってこのようなものをハックすることもできますが、Boost はもっと良い方法を提供してくれます:370
.これ以上苦労することなく、これが 386
をどのように移植したかです C++ へ:
struct Const_ { int value; }; template<typename A> struct Add_ { A left; A right; }; template<typename A> struct Mul_ { A left; A right; }; template<typename A> using ExprF_ = boost::variant< Const_ , boost::recursive_wrapper<Add_<A> > , boost::recursive_wrapper<Mul_<A> > >; template<typename A> struct ExprF : ExprF_<A> { typedef ExprF<A> tag; ExprF(Const_ c) : ExprF_<A>(c) {} ExprF(Add_<A> c) : ExprF_<A>(c) {} ExprF(Mul_<A> c) : ExprF_<A>(c) {} }; using Expr = Fix<ExprF>;
これは冗長ですが、ほとんど簡単です。でも待って、398
はどうなっているの? ? 408
じゃないですか 非再帰的であるべきですか?そうです、技術的には、今でもそうです。しかし、木を作り始めると、それはできあがる 411
による再帰 . Haskell では、再帰型は問題ありません。ただし、C++ では、構造体 422
タイプ 433
のメンバーを持つことはできません . できます タイプ 441
のメンバーを持つ しかし、それは基本的に 456
469
を構築するためのいくつかのユーティリティ関数 オブジェクトは後で役に立ちます:
template<typename A = Expr> ExprF<A> Const(int val) {return Const_{val};} template<typename A> ExprF<A> Add(A a, A b) {return Add_<A>{a, b};} template<typename A> ExprF<A> Mul(A a, A b) {return Mul_<A>{a, b};}
カタ関数
データ型の再帰は 477
によって外部で行われます 、アルゴリズムの再帰は、カタモルフィズムと呼ばれる非常に一般的な関数によって外部で行われます 、または 484
. Bartosz による 491
の派生 関数は非常に興味深いので、ぜひお読みください。結果はこちら:
cata :: Functor f => (f a -> a) -> Fix f -> a cata alg o = alg . fmap (cata alg) . unFix o
すべての数学関数合成を右から左に行うように、これを読みます。 501
再帰的な固定小数点データ構造の 1 つのレベルをアンパックする効果があります。これにより、515
できる Functor が生成されます 以上。 521
の方法を知らなくても 私たちの型に実装されているので、532
を呼び出すことがわかります。 再帰的に。 (この時点では、再帰がどのように終了するかは明確ではありません。後で説明します。)
これは 544
です C++で。短くて甘い…ほぼ。
template<typename Alg, template<typename> class F> ???? cata(Alg alg, Fix<F> o) { using std::placeholders::_1; return alg(fmap(std::bind(&cata<Alg, F>, alg, _1), unFix(o))); }
Haskell では、2 つを期待する関数に 1 つの引数を渡すと、1 つの引数を取る関数が得られます。涼しい。 C++ でこれを行うと、コンパイラ エラーが発生します。 😛 代わりに、非常に便利な 556
を使用します .ラムダの方がファッショナブルですが、私は少し時代遅れです.
唯一の問題は、戻り値の型を宣言しようとするときです。 560
573
を返します 渡されたときに戻ります…何?まあ、どんな 580
でも 戻り値。しかし、598
によって返される型 603
への再帰呼び出しに依存します 、そしてそれを計算しようとして Catch-22 に行き詰まります。 617
の戻り値の型について言えること 一部になるということです テンプレート 627
のインスタンス 、しかしどれかはわかりません .だから、私はごまかします:
// A horrible hack for the purpose of computing // cata's return type. AnyF<F> stands in for a F<T> // when T is unknown. template<template<typename> class F> struct AnyF { template<typename T> operator F<T> &() const; }; template<typename Alg, template<typename> class F> typename std::result_of<Alg(AnyF<F>)>::type cata(Alg alg, Fix<F> o) { using std::placeholders::_1; return alg(fmap(std::bind(&cata<Alg, F>, alg, _1), unFix(o))); }
このハッキングの恐ろしさ、なぜ機能するのか、なぜ機能しないのかについては詳しく説明しません。言わないほうがいい。
fmap
あなたが Haskeller なら、633
を知っているでしょう ファンクターを意味します。 (これは、大文字の「F」が付いた数学的な「ファンクター」であり、おなじみの C++ のものとはおそらく異なるものです。) もしあなたが Haskeller でないなら、ここにスキニーがあります:>649 652
からマッピングされる関数 660
まで 、それはあなたに 670
を与えます 何かをすることによって . 685
ごとに何かが違うということ -可能なタイプ。
Haskell の Functor は型クラスです。型クラスとインスタンスは、C++ の概念と概念マップのようなものです。では、Haskell の Functor 型クラスのようなものはどのように C++ に変換すればよいのでしょうか?興味深い質問です。今のところ、単純化するための仮定を立てます:all C++ で「ファンクター」の概念をモデル化する型は、690
として実装されます。 . (明らかに、これは 703
の場合です。 .)
711
はこちら C++ で:
template<typename Fun, typename Tag> struct functor_visitor; template<typename Fun, typename Fa> typename functor_visitor<Fun, typename Fa::tag>::result_type fmap(Fun f, Fa fa) { return boost::apply_visitor( functor_visitor<Fun, typename Fa::tag>{f}, fa); }
725
バリアントでどのスロットが占有されているかを確認し、734
で適切なハンドラーにディスパッチする単純なラッパーです。 .そこに 749
を入れます あなたのタイプのロジック。これが 753
の方法です 768
用に実装されています :
template<typename Fun, typename A> struct functor_visitor<Fun, ExprF<A>> : boost::static_visitor< ExprF<typename std::result_of<Fun(A)>::type>> { typedef typename std::result_of<Fun(A)>::type B; explicit functor_visitor(Fun f) : f_(f) {} ExprF<B> operator()(Const_ i) const { return Const<B>(i.value); } ExprF<B> operator()(Add_<A> e) const { return Add(f_(e.left), f_(e.right)); } ExprF<B> operator()(Mul_<A> e) const { return Mul(f_(e.left), f_(e.right)); } private: Fun f_; };
つまり、776
関数と 785
を使用 798
の内容に応じて、3 つのいずれかを行います .各 801
オーバーロードは考えられる 1 つのケースを処理し、それらはすべて 814
を返します 、ここで 828
836
とは 847
が渡されると戻ります .
852
を見る 、関数は 861
になります -ing over は 877
になります . 887
の場合 893
を含む または 907
、その後、再帰的に 918
を呼び出すことになります .しかし、920
に到達すると 、私たちはしません 再帰。そうでなければ 938
二度と戻らない!
F代数
944
とは ?それが最良の部分です:あなたが決めます!それは代数です。シンボルから式を作成して評価する方法。以下は、955
を引き起こす Haskell の単純な代数です。 意味のある方法で式ツリーを評価するには:
alg :: ExprF Int -> Int alg (Const i) = i alg (x `Add` y) = x + y alg (x `Mul` y) = x * y
C++ では次のようになります:
struct alg_visitor : boost::static_visitor<int> { int operator()(Const_ i) const { return i.value; } int operator()(Add_<int> e) const { return e.left + e.right; } int operator()(Mul_<int> e) const { return e.left * e.right; } }; int alg(ExprF<int> e) { return boost::apply_visitor(alg_visitor{}, e); }
966
の例を次に示します。 と 975
式ツリーの評価:
// (2+3)*4 == 20 Expr testExpr = Fx(Mul( Fx(Add( Fx(Const(2)), Fx(Const(3)) )), Fx(Const(4)) )); int z = cata(alg, testExpr); std::cout << z << std::endl;
これは 986
を出力します あなたが期待するように。同じ式ツリーを異なる方法で評価させる他の代数を簡単に定義できます。
まとめ
991
に注意してください 再帰的ではありません。ここで本当に素晴らしいことが起こりました。 1 つのレベルのツリーを処理する方法を指定するだけで済み、任意の のツリーを無料で評価できます。 深さ。他のすべては 1002
によって処理されます および 1013
.
楽しくてかっこいいという事実以外に、なぜ私は気にするのですか? C++ で組み込みのドメイン固有言語を構築するための私のライブラリである Boost.Proto には、式の評価方法を指定するための小さな DSL があります。その DSL では、ツリー トラバーサル ロジックが残りのアルゴリズムと混合されます。これにより、Proto アルゴリズムを作成するのが難しくなります。興味深いビットのみを指定しながら、再帰的な評価を無料で取得する方法があれば…。それゆえ、F 代数に興味があります。
Bartosz と私は、これを拡張して私のユース ケースで動作させる方法について話し合ってきました。 State モナドと組み合わせると、1029
関数は、多くの式評価スキームの重要な部分である折り畳みを行うことができます。でも、それは後で取っておこうと思います。
このコードは、私の github リポジトリで少し一般化された形で見つけることができます。そこでは、State モナドの私の実装も見つけることができます。