双射とF-代数

だから私はしばしば”catamorphism”と”recursion scheme”という言葉を聞いています。 それは何ですか？

Catamorphisms(またはcata)は、関数型プログラミングにおける折畳の概念の一般化である。 F代数と再帰的なデータ構造が与えられた場合、カタモルフィズムはデータ構造を再帰的に評価することによって値を生成します。

F-代数とは何ですか？ 多分あなたは最初にいくつかのコード例を示すことができますか？

設定はそれほど簡単ではないので、簡単に始めましょう。 式を表すために次のデータ構造があるとしましょう:

単純な式は次のようになります:

もちろん、結果を評価して取得する関数が必要です:

これがカタモルフィズムの一般化の出番です:

🤨, しかし、ポイントは何ですか？ 関数に引数を適用するだけですか？

それはnotReallyCataだからです。 実際のcata関数は汎用であり、特定のデータ構造やエバリュエーター関数には依存しません。 参照してください、再帰的なデータ構造を作成し、それを折りたたむことは、cataが一般化しようとする一般的なパターンです。

さて、本当のcataはどのように見えますか？

🤯

それがnotReallyCataから始まった理由です。 それがクリックされるまで、後で実装を分解します。 しかし今私達のExpressionの例を続けてみましょう。 まず、型パラメータを導入することによって再帰を取り除く必要があります:

Expressionへのすべての参照はa型パラメータに置き換えられ、データ構造は再帰的ではなくなりました。

型コンストラクタの最後にFがあるのはなぜですか？

あなたが尋ねてうれしい—それはExpressionFができるヒントですFunctor:

構造を保持するラップされた値にいくつかの関数を適用するだけです。

なぜそれが必要なのか分かりません🤔

それは今は意味がありませんが、少し後になります。 ここで、式の作成方法は変更されていません（コンストラクタ名を除きます):

しかし、結果の型は異なります:

expr すべてを単一のExpressionに折りたたみ、exprFは式ツリーのネストレベルに関する情報をエンコードします。 評価について言えば、これは私たちがevalの実装について行くことができる方法ですExpressionF:

元のevalExprとの主な違いは、evalExprFへの再帰呼び出しがないことです（ExpressionFは再帰的ではありません、覚えていますか？). また、エバリュエーターは単一レベルの式でのみ動作できることを意味します:

そして、これでコンパイルされません:

単純にexprFがExpressionF Intをexpepectsし、ExpressionF (ExpressionF Int)を押しているからです。

それを機能させるために、別の評価者を定義することができます:

ちょっとアドホックに見えますが、深く入れ子になった式がある場合はどうなりますか？

はい、任意のネストされた式の場合、このアプローチはスケーラブルではありません—追加のネストレベルごとに特殊な関数を記述する必要があります。

この入れ子を新しい型で一般化する方法があります:

修正？ それほど多くのことをしない再帰的なデータ構造のように見えます。 それはどのように便利ですか？

最初に等号の前の式を見てみましょう：実際にFixは、1つの型パラメータfを持つ再帰的なデータ構造です。 このパラメータにはkind* -> *があります。 たとえば、IntまたはBoolを提供するFixを構築することはできません。Maybe、Listまたは…ExpressionFのようなものでなければなりません。 これが、ExpressionFの型パラメータを導入した理由です。 次に、等号の後に、基本的にfの値を構成する式であるf (Fix f)型の単一の引数を取る単一の型コンストラクタFxがあります。 Maybeの場合、それはMaybe (Fix Maybe)になり、すべてがFxでラップされてタイプFix Maybeになります。

型シグネチャは、型コンストラクタが型自体と自己参照と同じ名前を持つことができるため、最初に読むのが混乱します。 しかし、高次の型をデータ構造にラップするだけではありません。 ところで、unfixはFxとは反対であり、Fxのパターンマッチングであり、ラップされた値を返します。

ここで、式ツリーのすべてのExpressionFをFix ExpressionFに置き換えます。 Fxの有無にかかわらず式を構築する際の違いに注意してください—それらは基本的に同じですが、前に追加する必要がありますFx $:

‘固定’バージョンの結果の型はFix ExpressionFなので、再帰的な表現に戻りますが、非再帰的なデータ構造を取り戻すにはunfix関数を使用する必要があります。

Fixを持つことの利点は何ですか？ 元のExpressionタイプと同じアプローチのように見えますが、今はこの奇妙なFixとunfixナンセンスがありますか？

はい、しかし、我々は折り畳みのプロセスを一般化しようとしている、それは我々が後で議論するFixとAlgebraのような追加の抽象化の導入を必要とします。 私と一緒に負担し、それは後でより多くの意味をなさないはずです。

だから、私たちは私たちの’固定’データ構造を持って、評価関数はどのように見えるでしょうか？

与えられたFix ExpressionF我々はそれで行うことができる唯一のことは、生成するunfixを呼び出すことですExpressionF (Fix ExpressionF):

返されるExpressionFは、型パラメータとしてFix ExpressionFを持つValueF、AddF、またはMultFのいずれかになります。 パターンマッチングを行い、次に何をすべきかを決定するのは理にかなっています:

はい、それはExpressionの最初の再帰的な評価者と同じように見えますが、式をunfixでラップ解除する必要があります。 では、なぜFixを気にするのですか？

ここにキーがあります: 私たちはExpressionFの元の’fix-less’エバリュエーターを再利用し、何とかそれをFix ExpressionF構造上に配布します。 したがって、これは2つの引数を取る関数でなければなりません—評価者と評価する構造体:

実装を理解してみましょう-最初に行うべき論理的なことは、unfixを使用してExpressionFを取得し、それをExpressionF渡すことですevaluator:

明らかにこれは機能しませんが、evaluatorはExpressionF (Fix ExpressionF)ではなくExpressionF Intを期待しています。 ところで、ExpressionFはFunctorであることを覚えていますか？ これが便利な場所です—fmapを使用して、式ツリーの内部レベルに同じプロセスを適用できます:

私たちは再帰関数almostCata evaluatorをfmapに渡しています。 現在の式がAddFまたはMultFの場合、この関数は1レベル深く渡され、fmapが再び呼び出されます。 これはValueFに達するまで起こり、ValueFをfmappingするとExpressionF Int型の値が返され、それがevaluator関数が受け入れるものです。

almostCataを見ると、ExpressionFまたはInt型に固有のものは実際にはなく、理論的にはいくつかの型パラメータfで一般化できることがわかります。 唯一の制約は、fのFunctorインスタンスを持つ必要があります。fmap:

そして、それがcataの最終版です。 以下は、いくつかの使用例を含む完全な実装です:

それはクールだと思います。 しかし、なぜカントー？

圏論や関数型プログラミングにおける多くの概念はかなり抽象的であり、時には特定のアイデアのための実用的なアプリケーションをすぐに見つ しかし、抽象化と一般化を探すことは、それ以外の場合はアドホックな実装を必要とする問題のパターンとエレガントな解決策を見つけるのに役立

ところで、私たちのExpressionF -> Int関数をFunctor f => (f a -> a)に一般化することによって、F-代数と呼ばれる別の重要な概念を発見しました。 基本的にF-代数は関手f、ある種の型aと評価関数f a -> aの三重である。 ここではaは多型ではなく、IntやBoolのような具体的な型でなければならず、キャリア型と呼ばれます。 任意のendo-functorfに対して、それに基づいて複数のF代数を作成できます。 式の例を取る—endo-functorfはExpressionF、aはInt、評価者はevalExprFです。 しかし、我々はキャリアの種類を変更し、より多くの代数を生成することができます:

それはcataに渡すことができるだけの異なる評価者ですよね？

はい、異なるキャリアタイプを選択し、実装を選択しています。 Fix ExprFになるようにキャリアタイプを選択することで作成できるすべての評価者の母親があります。

IntまたはBoolに評価することは完全に理にかなっていますが、このinitialAlgebraは何を評価しますか？ 私の評価者の結果として何かのFixが必要なのはいつですか？もちろん、あなたはそのようなことを自分で書くことはありません。f-algebrasとcataの背後にあるより深い意味を示したいだけです。 実際、私たちはすでにそのような評価者のための実装を持っており、それはまさにFxコンストラクタです:

待って、Fxは評価者ですか？ それは狂っている。

はい、それはあなたができる最も簡単なことをします—expessionをデータ構造に保存します。 他のすべてのエバリュエーター（algebra0、algebra1）は式を減らすことによって何らかの値を生成しましたが（合計や連結など）Fxは、データを失うことなく式をラップするだけです。

これが、最初にFixを導入した理由です—最初にFxで元のデータ構造を初期代数Fix fに評価し、cataを使用して”本当の”評価は、初期代数よりも具体的な評価者をfmap圏論の観点から見ると、同じ遠藤関手に基づくすべての代数は圏を形成する。 このカテゴリには、キャリアタイプをFix fとして選択することによって作成された初期代数である初期オブジェクトがあります。 Bartosz Milewskiによるいくつかの素晴らしいブログ記事があります。

それはまだ理解するのはかなり難しいです、私は概念を完全に理解しているとは思わない

それは常に手で行う方が良いです：あなた自身でFixとcata たとえば、Stringは再帰的に表すことができます（StringのCharheadとtailとして）、文字列のlengthはcataで計算できます。 ここにそれ以上の読書のためのある大きい資源はある:

• F代数とわずかに異なるF代数の理解Bartosz Milewski
• Catamorphisms in15minutes By Chris Jones
• Rob Norris
• Haskell wikiのCatamorphisms
• Pure Functional Database Programming with Fixpoint Types by Haskell wiki
• Practical recursion scheme by Chris Jones
• Catamorphisms by Haskell wiki
• Practical recursion scheme by Chris Jones
• Catamorphisms by Haskell wiki
• ジャレッド-トービン