問題タブ [church-encoding]

ラムダ計算を書き出そうとしていますが、教会の条件を機能させることができません。私はおそらく Haskell 初心者だと言うべきでしょう。

私はオンラインと SO で解決策を見てきましたが、それらはすべて新しい型やその他のトリックの導入を伴いますが、できるだけ元の構文に近づけたいと考えています。例えば：

教会のブール値の正確な構文に一致します。

教会のif/elseの正確な構文を一致させる方法はありますか? を複製しようとして\p.\a.\b.p a bいますが、何が間違っているのかわかりません:

私は、Scheme を通じて教会のエンコーディングの原理全体を理解しようとしています。などの基本は理解できたと思います。

• 0 の教会数字

  (定義 c-0 (ラムダ (f) (ラムダ (x) x)))

• 1の教会数字

  (定義 c-1 (ラムダ (f) (ラムダ (x) (fx))))

...そして、関数を x N 回適用し続けます。

今私の問題は、これが何を意味するのかということです。たとえば、church-3 を例にとると、次のようになります。

これは実際に何をしているのですか？私も基本的なスキームの知識しか持っていませんが、関数の使用方法さえ理解していませんか? c-3 関数を使用した入力例は何ですか? ループのように3回適用するだけですか？

SML にこの式があり、最も一般的なタイプを見つける必要があります。コンパイラを実行すると、以下に示すものが表示されます。この関数だけでなく、教会の数字関数「2」などの他の関数の最も一般的なタイプを見つけるにはどうすればよいでしょうか。

これのタイプはなぜですか：

次のようなスコットでエンコードされたリストがあるとします。

この種のリストを受け取り、それを実際のリスト ( [1,2,3]) に変換する関数が必要ですが、そのような関数は再帰できません。つまり、これは eta-beta 正規形でなければなりません。その機能はありますか？

パッケージのFreeデータ型を使用してControl.Monad.Freeいます。free今、私はそれを変換して使用しようとしてFいControl.Monad.Free.Churchますが、関数をマップする方法がわかりません。

たとえば、 を使用した単純なパターン マッチング関数Freeは次のようになります。

-とのF間で変換して使用する関数に簡単に変換できます。Free

toFただし、使用せずにそれを実行する方法がわかりませんfromF-

私が見逃している一般的なパターンがあるに違いありません。それを理解するのを手伝ってもらえますか？

Churchエンコーディングのリストにパッケージcataから使えるようにしたいです。recursion-schemes

便宜上二等式を使いましたが、気にしません。newtype必要に応じてを追加したり、GADT を使用したりしてください。

Church エンコーディングの考え方は広く知られており、単純です。

基本的に「未指定の抽象」consでありnil、「通常の」コンストラクターの代わりに使用されます。私はすべてがこの方法でエンコードできると信じています（Maybe、ツリーなど）。

List1が実際に通常のリストと同型であることを示すのは簡単です:

したがって、その基本ファンクターはリストのファンクターと同じであり、それを実装projectしてからの機構を使用できるはずrecursion-schemesです。

でもできなかったので、「どうしたらいいの？」というのが私の質問です。通常のリストの場合は、パターン マッチのみを実行できます。

関数のパターン マッチができないため、フォールドを使用してリストを分解する必要があります。project通常のリストの折り畳みベースを書くことができます：

ただし、教会でエンコードされたリストには適用できませんでした。

cata次の署名があります。

リストで使用するには、次のものが必要です。

1. を使用してリストの基本ファンクタ型を宣言するにはtype family instance Base (ListC a) = ListF a
2. 実装するinstance Recursive (List a) where project = ...

私は両方のステップで失敗します。

このプログラムに注意してください：

合計の両方の定義は、等式の推論までは同じです。それでも、2 番目の定義のコンパイルは機能しますが、最初の定義はコンパイルされず、次のエラーが発生します。

RankNTypes等式の推論を破るようです。それを壊すことなく、Haskellで教会でエンコードされたリストを持つ方法はありますか??