問題タブ [scott-encoding]

または具体的に言うと、なぜfoldrを使用してリストをエンコードし、反復を使用して数値をエンコードするのですか?

長文の導入で申し訳ありませんが、質問したいことの名前をどのように挙げればよいかよくわからないので、最初にいくつかの説明をする必要があります. これは、この CAMcCann の投稿から大きく引き出されていますが、これは私の好奇心を完全に満足させるものではありません。また、ランク n 型と無限の怠惰な問題についても手短に説明します。

データ型を関数としてエンコードする 1 つの方法は、ケースごとに 1 つの引数を受け取る「パターン マッチング」関数を作成することです。各引数は、そのコンストラクターに対応する値を受け取り、すべての引数が同じ結果の型を返す関数です。

これはすべて、非再帰型の場合に期待どおりに機能します

ただし、パターン マッチングとの優れた類似性は、再帰型ではうまくいきません。私たちは次のようなことをしたくなるかもしれません

しかし、これらの再帰的な型定義を Haskell で書くことはできません! 通常の解決策は、コンス/成功ケースのコールバックを、再帰の最初のレベルだけでなく、すべてのレベルに強制的に適用することです (つまり、フォールド/イテレータを記述します)。このバージョンrでは、再帰型が次のような戻り値の型を使用します。

このバージョンは機能しますが、一部の関数の定義が非常に難しくなります。たとえば、リストの "tail" 関数や数値の "predecessor" 関数を書くことは、パターン マッチングを使用できる場合は簡単ですが、代わりに折り畳みを使用する必要がある場合は注意が必要です。

だから私の本当の質問に：

1. フォールドを使用したエンコーディングが、仮想の「パターン マッチング エンコーディング」と同じくらい強力であることをどのように確認できますか? パターンマッチングを介して任意の関数定義を取得し、代わりに折り畳みのみを使用して機械的に変換する方法はありますか? (もしそうなら、これはまた、foldr に関して、tail や foldl などのトリッキーな定義をあまり魔法のようにしないようにするのにも役立ちます)

2. Haskell 型システムが「パターンマッチング」エンコーディングで必要な再帰型を許可しないのはなぜですか? . 経由で定義されたデータ型で再帰型のみを許可する理由はありdataますか? 再帰代数データ型を直接消費する唯一の方法はパターン マッチングですか? 型推論アルゴリズムと関係がありますか?

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

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

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

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

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

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

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