問題タブ [euclidean-algorithm]

という関数があるとしましょうmy_func(a,b,s,t)。aandを値渡ししたいbが、 and を参照渡ししたいsとtします。のように、私はいくつか言いたいと思います(4,5,s',t')。この関数は、 を呼び出して計算を実行しmy_func(a/2,b/2,s/2,t/2)ます。s問題は、再帰の「下部」に、とに具体的な値を与える基本ケースがあることですt。

ちょっとした例を挙げましょう：

したがって、この関数を と呼びますe_euclid(a,b, something, something)が、 と に具体的な値を指定する必要がsありtます。私がここで何をしようとしているのか、ちょっとわかりますか？

(s,t) を返す場所で再帰を実行すると、実行したくない難しい計算が発生するため、この方法で実行したいと考えています。

Euclid のアルゴリズムは、最初は次のように実装しました。

アルゴリズムは末尾再帰で、 recursion-schemesで直感的に書けると思います。そして、次のeucは再帰部分の抜粋です。このeuclid関数はeucを使用しますが、psiはワンステップ処理に専念しています。

euc関数はapo射に似ていますが、 apoをeucに特化する方法がわかりません。それらはまったく別のもののように私には思えます。再帰スキームである種のモーフィズムとしてeucを書くことは可能ですか?

よろしく。

いくつかの実験と検索の後、次の定義を思いつきました。

emcd' 56 15たとえば、次のように、最も内側のレベルまで評価します。

• 私の評価は正しい方向に進んでいますか？

編集：

ウィル・ネスさんのコメントから、評価を更新しています。