我试图从中理解组织形态关于递归方案的博客 https://blog.sumtypeofway.com/posts/recursion-schemes-part-4.html。当我运行示例来解决问题时遇到问题改变问题 https://en.wikipedia.org/wiki/Change-making_problem正如博客中提到的。

找零问题采用货币的面额，并尝试找到创造给定金额所需的最小硬币数量。下面的代码取自博客，应该计算答案。

{-# LANGUAGE DeriveFunctor #-}

module Main where

import Control.Arrow ( (>>>) )
import Data.List ( partition )
import Prelude hiding (lookup)

newtype Term f = In {out :: f (Term f)}

data Attr f a = Attr
  { attribute :: a
  , hole :: f (Attr f a)
  }

type CVAlgebra f a = f (Attr f a) -> a

histo :: Functor f => CVAlgebra f a -> Term f -> a
histo h = out >>> fmap worker >>> h
 where
  worker t = Attr (histo h t) (fmap worker (out t))

type Cent = Int

coins :: [Cent]
coins = [50, 25, 10, 5, 1]

data Nat a
  = Zero
  | Next a
  deriving (Functor)

-- Convert from a natural number to its foldable equivalent, and vice versa.
expand :: Int -> Term Nat
expand 0 = In Zero
expand n = In (Next (expand (n - 1)))

compress :: Nat (Attr Nat a) -> Int
compress Zero = 0
compress (Next (Attr _ x)) = 1 + compress x

change :: Cent -> Int
change amt = histo go (expand amt)
 where
  go :: Nat (Attr Nat Int) -> Int
  go Zero = 1
  go curr@(Next attr) =
    let given = compress curr
        validCoins = filter (<= given) coins
        remaining = map (given -) validCoins
        (zeroes, toProcess) = partition (== 0) remaining
        results = sum (map (lookup attr) toProcess)
     in length zeroes + results

lookup :: Attr Nat a -> Int -> a
lookup cache 0 = attribute cache
lookup cache n = lookup inner (n - 1) where (Next inner) = hole cache

现在如果你评估change 10它会给你3。

这是……不正确的，因为你可以用 1 个面值 10 的硬币赚到 10。

所以我想也许它可以解决硬币找零问题 https://math.stackexchange.com/questions/15521/making-change-for-a-dollar-and-other-number-partitioning-problems，它会找到您赚取给定金额的最大方式。例如你可以用 4 种方法制作 10 个{ 1, 1, ... 10 times }, { 1, 1, 1, 1, 5}, { 5, 5 }, { 10 }.

那么这段代码有什么问题呢？解决问题的过程中哪里出了问题？

TLDR

上面的一段代码来自于此关于递归方案的博客 https://blog.sumtypeofway.com/posts/recursion-schemes-part-4.html没有找到改变一笔钱的最小或最大的方法。为什么它不起作用？

我更多地考虑用递归方案来编码这个问题。也许有一个很好的方法来解决无序问题（即，考虑 5c + 1c 与 1c + 5c 不同），使用组织同态来缓存无向递归调用，但我不知道它是什么。相反，我寻找一种使用递归方案来实现动态编程算法的方法，其中以特定顺序探测搜索树，以便确保您不会多次访问任何节点。

我使用的工具是 hylomorphism，它会在您正在阅读的文章系列的后面部分出现。它由展开（变形）和折叠（变形）组成。 hylomorphism 使用 ana 构建中间结构，然后使用 cata 将其分解为最终结果。在这种情况下，我使用的中间结构描述了一个子问题。它有两个构造函数：要么子问题已经解决，要么还剩下一些钱可以找零，以及可以使用的硬币面额池：

data ChangePuzzle a = Solved Int
                    | Pending {spend, forget :: a}
                    deriving Functor
type Cent = Int
type ChangePuzzleArgs = ([Cent], Cent)

我们需要一个将单个问题转化为子问题的余代数：

divide :: Coalgebra ChangePuzzle ChangePuzzleArgs
divide (_, 0) = Solved 1
divide ([], _) = Solved 0
divide (coins@(x:xs), n) | n < 0 = Solved 0
                         | otherwise = Pending (coins, n - x) (xs, n)

我希望前三种情况是显而易见的。最后一种情况是唯一具有多个子问题的情况。我们可以使用第一个列出的面额的一枚硬币，然后继续找较小金额的硬币，或者我们可以保持金额不变，但减少我们愿意使用的硬币面额列表。

组合子问题结果的代数要简单得多：我们只需将它们相加即可。

conquer :: Algebra ChangePuzzle Int
conquer (Solved n) = n
conquer (Pending a b) = a + b

我最初尝试写conquer = sum（使用适当的 Foldable 实例），但这是不正确的。我们不是在总结a输入子问题；相反，所有有趣的值都在 Solved 构造函数的 Int 字段中，并且sum不看那些，因为它们不属于类型a.

最后，我们让递归方案通过一个简单的方法为我们完成实际的递归hylo call:

waysToMakeChange :: ChangePuzzleArgs -> Int
waysToMakeChange = hylo conquer divide

我们可以确认它在 GHCI 中有效：

*Main> waysToMakeChange (coins, 10)
4
*Main> waysToMakeChange (coins, 100)
292

您是否认为这值得付出努力取决于您。递归方案在这里为我们节省了很少的工作，因为这个问题很容易手工解决。但您可能会发现具体化中间状态使递归结构显式化，而不是隐式地隐含在调用图中。无论如何，如果您想练习递归方案以准备更复杂的任务，那么这是一个有趣的练习。

为了方便起见，完整的工作文件包含在下面。

{-# LANGUAGE DeriveFunctor #-}
import Control.Arrow ( (>>>), (<<<) )

newtype Term f = In {out :: f (Term f)}

type Algebra f a = f a -> a
type Coalgebra f a = a -> f a

cata :: (Functor f) => Algebra f a -> Term f -> a
cata fn = out >>> fmap (cata fn) >>> fn

ana :: (Functor f) => Coalgebra f a -> a -> Term f
ana f = In <<< fmap (ana f) <<< f

hylo :: Functor f => Algebra f b -> Coalgebra f a -> a -> b
hylo alg coalg = ana coalg >>> cata alg

data ChangePuzzle a = Solved Int
                    | Pending {spend, forget :: a}
                    deriving Functor

type Cent = Int
type ChangePuzzleArgs = ([Cent], Cent)
coins :: [Cent]
coins = [50, 25, 10, 5, 1]

divide :: Coalgebra ChangePuzzle ChangePuzzleArgs
divide (_, 0) = Solved 1
divide ([], _) = Solved 0
divide (coins@(x:xs), n) | n < 0 = Solved 0
                         | otherwise = Pending (coins, n - x) (xs, n)

conquer :: Algebra ChangePuzzle Int
conquer (Solved n) = n
conquer (Pending a b) = a + b

waysToMakeChange :: ChangePuzzleArgs -> Int
waysToMakeChange = hylo conquer divide