再帰スキームに関するこのブログから、組織型を理解しようとしています。ブログに記載されているように、変更を行う問題を解決するために例を実行しているときに問題に直面しています。

両替問題は、通貨の額面を取り、特定の金額を作成するために必要なコインの最小数を見つけようとします。以下のコードはブログから取得したもので、答えを計算する必要があります。

これで評価change 10すると 3 になります。

これは... 10 の値のコイン 1 枚を使用して 10 を作ることができるため、間違っています。

だから私はそれが、与えられた金額を稼ぐことができる方法の最大数を見つけるコインチェンジ問題を解決しているのかもしれないと考えました. たとえば、 、 、 、 の 4 つの方法で 10 を{ 1, 1, ... 10 times }作成{ 1, 1, 1, 1, 5}でき{ 5, 5 }ます{ 10 }。

では、このコードの何が問題になっているのでしょうか? 問題を解決する上でどこが間違っていますか？

TLDR

再帰スキームに関するこのブログの上記のコードは、金額を変更する最小または最大の方法を見つけていません。なぜ機能しないのですか？

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

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

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

よろしく。

有用な議論と完全な実装を伴う再帰スキーム (RS) の使用法を説明するハイロモヒズムの例を探しているときに、@amalloy による SO に関する素敵な投稿に出くわしました。

コードは期待どおりに機能します。RSの側面についてはすでに漠然とした直感を持っていますが、私はまだ疑問に思っています:

1. これは組み合わせを数えることに関するものなので、なぜSolved CentですかSolved Int? (これは、たとえそれが妥当な質問であったとしても、つまらないことのように聞こえるかもしれませんが、それが以下の残りの不確実性の根源である可能性があることを願っていますが、もっと基本的なことを見逃していると思います!)。
2. 後で合計するので、divideでSolved0/1 はおそらく失敗/成功を意味しますか?
3. に、およびをconquer追加するとはどういう意味ですか? これらの 2 つの値 ( s として) は何を意味し、このコンテキストでそれらの合計は何を意味するのでしょうか?abPendingCent
4. ではconquer、単に s を合計する必要があると予想していましたがSolved、著者はこれに触れていますが、ケースがどのように寄与しているかはまだ明らかではありません(Pendingたとえば、修正は機能に悪影響を及ぼし、おそらく手がかりです)を返す、またはそのケースが固定されている定数)。conquer (Pending a b) = 11 waysToMakeChange11
5. in conquer、aおよびbはCentsですが、 individeはChangePuzzleArgs(別名([Cent], Cent)) です。その変換はどこで発生しますか?

注：SOが初めてなので、元の回答の下にコメントできませんでした。これはより適切だったかもしれませんが、これがそのまま役立つことを願っています。

私は最近、再帰スキームを調査しており、組織型のいくつかのユースケースを見つけたいと思っています.カタロニア語の数は楽しいものになると思います.質問）。私が思いついたのは次のとおりです。

ただし、次の場合はパフォーマンスが低下しcatalanHistoます。

と比較してかなり悪いcatalanMemoです：

少なくともそれが終了することを考えると、バージョンは間違いなく何かをメモ化しましたが、私が を誤用しているのか、それともこの方法でプログラムを書くための代償なのhistoか、私にはわからない大きなオーバーヘッドがあります。histoいくつかの基本的なプロファイリングを進めたとき:

これらの結果を解釈する専門家ではありません。 のいくつかの割り当てに加えて、おそらく と が原因で、Control.Comonad.Cofreeの重要なブランチで割り当てを行うのに大部分の時間を費やしていると思います。最適化の余地がどれだけあるかはわかりません.catalanHistotoListreverse