問題タブ [y-combinator]

The Little Schemerlength≤1という本の166 ページを 1 日かけて読みました。次のコードがあります。

とlは次(apples)のeternityとおりです。

166ページ（第4版）には、次のように記載されています。

mk-length一度応募するともらえるlength≤1

その後

これを複数回行うことはできますか？

しかし、取得するためにこれを行う方法がわかりませんかlength≤2？

帰納的データ型とパターンマッチングの状態に関するAgdaマニュアル：

正規化を確実にするために、帰納的発生は厳密に正の位置に現れる必要があります。たとえば、次のデータ型は許可されていません。

コンストラクターへの引数にBadの負のオカレンスがあるためです。

誘導データ型にこの要件が必要なのはなぜですか？

この構造を理解したい。誰かがこのコードについて明確で簡単な説明をすることができますか?

たとえば、Y の式を忘れたとします。どうすればそれを覚えて、作業を行った後でも再現できるでしょうか?

Yコンビネータが理解できなかったので、ネイティブ実装なしで再帰を可能にする関数を実装してみました。いろいろ考えた結果、以下のようになりました。

これは実際のものよりも短いです:

そして、驚いたことに、うまくいきました。いくつかの例：

両方のスニペットは、期待どおり 10 (0 から 4 までの合計) を出力します。

これは何ですか、なぜ短いのか、なぜ長いバージョンが好まれるのでしょうか?

ラムダ計算、コンビネータ論理、関数型プログラミングの本で説明されているように、階乗ラムダ式を実装しようとしています。

そこに記述されている方法は次のとおりです。

どこ

およびis-zero、、、およびはone、標準のチャーチ数に対して定義されています。ここでの実際の定義。multiplypredecessor

私はそれを次のように翻訳しました

と

コメントアウトされたバージョンは、Rosettaコードの同等のfac関数とY関数です。

質問1：

他の場所を読んで、Y-rosettaβ-がに還元されることを理解していY-mineます。その場合、なぜそれを他のものよりも使用することが好ましいのですか？

質問2：

使ってもY-rosetta。試してみるとStackOverflowErrorが発生します

その間

正常に動作します。

無防備な再帰はどこで起こっていますか？

ifフォームがclojureでどのように機能するかと関係があるのではないかと思いますが、これは私のis-zero実装と完全には同等ではありません。しかし、私は自分でエラーを見つけることができませんでした。

ありがとう。

アップデート：

@amalloyの答えを考慮して、私はfac-mine怠惰な議論をするように少し変更しました。私はclojureにあまり詳しくないので、これはおそらく正しい方法ではありません。しかし、基本的に、私はis-zero匿名のゼロ引数関数を取り、それが返すものは何でも評価するようにしました。

次のようなエラーが発生します。

lazy-next-termそれが常にとと呼ばれてnいることを考えると、これは本当に奇妙に思えますf

stack固定小数点コンビネータを使用して、ラムダ計算でデータ構造を定義しようとしています。2つの操作、insertionおよびremoval要素のso、pushおよびを定義しようとしてpopいますが、定義できた唯一の操作である挿入が正しく機能していません。削除の定義方法がわかりませんでした。

これが私の操作に対するアプローチであり、 ：pushの定義です。stack

私のスタックは、一番下を示す要素で初期化されています。私は0ここを使用しています：

しかし、今、別の要素を挿入しようとすると、初期構造が分解されているため、機能しません。

STACK定義または定義を修正するにはどうすればよいですか？また、操作PUSHを定義するにはどうすればよいですか？POP再帰を許可するには、コンビネータを適用する必要があると思いますが、その方法がわかりませんでした。

参照： http： //en.wikipedia.org/wiki/Combinatory_logic

ラムダ計算でのデータ構造の定義に関する詳細な説明や例をいただければ幸いです。

この投稿に影響を与えました。

ネストされたラムダでフィボナッチ数列を実装しようとしています-

プロンプトですr5rs:body: no expression in body in: (r5rs:body)

私の調査によると、各関数にはここに「本体」があるので、私が間違ったことは何ですか？

ここで実行しようとしている実装は、前のシリーズの再計算を回避する反復モードであることに注意してください。

編集 ：

同様に機能する別のモード-

私は固定小数点コンビネータの世界に不慣れで、無名ラムダの再帰に使用されていると思いますが、実際にそれらを使用する必要はなく、頭を完全に包むことさえできませんでした。

Y コンビネータの Javascript の例を見たことがありますが、うまく実行できませんでした。

ここでの質問は、直感的な答えを誰かが与えることができるかということです:

• 固定小数点コンビネータとは何ですか (理論的にだけでなく、いくつかの例のコンテキストで、そのコンテキストで固定小数点が正確に何であるかを明らかにします)?
• Y-コンビネータ以外の固定小数点コンビネータにはどのようなものがありますか?

ボーナス ポイント:例が 1 つの言語だけでなく、できればClojureでもある場合。

アップデート：

Clojureで簡単な例を見つけることができましたが、それでも Y-Combinator 自体を理解するのは難しいと感じています。

例は簡潔ですが、関数内で何が起こっているのかを理解するのは難しいと思います。提供されるヘルプは役に立ちます。

Knights of the Lambda Calculus のロゴには、次のように書かれた無限があります。(Y F) = (F (Y F))

この Lisp コードは同じで、無限も表しているのですか?

(Y (λ (F) (YF)))