haskell - 这个hylo解决 "coin-change"问题的方案是怎么设计的呢？

Question

我遇到了 a nice post在@amalloy 上寻找 hylomorhism示例，通过有用的讨论和完整的实现来说明递归方案 (RS) 的用法:

{-# 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 Cent
                    | 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 Cent
conquer (Solved n) = n
conquer (Pending a b) = a + b

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

代码按预期工作。尽管对 RS 方面已经有了一些模糊的直觉，但我仍然想知道:

1. 既然这是关于计算组合，为什么是 Solved Cent 而不是 Solved Int？ (即使这是一个合理的问题，这听起来也像是一个 nitpic，但我希望它可能是下面其余不确定性的根源，尽管我怀疑我错过了一些更基本的东西!)。
2. 因为我们稍后要求和，在 divide 中，Solved 0/1 大概表示失败/成功？
3. 在conquer中，Pending的a和b是什么意思？这 2 个值(如 Cent)表示什么，它们的总和在这种情况下意味着什么？
4. 在 conquer 中，我原以为我们只需要对 Solved 求和，作者也提到了这一点，但目前还不清楚 Pending 案例有贡献(例如修复 conquer (Pending a b) = 11 does 对功能有不利影响，这可能是一个线索 waysToMakeChange 返回 11，或该大小写 固定 的任何常量)。
5. 在conquer中，a和b是Cent，而在divide中> 它们是 ChangePuzzleArgs(又名 ([Cent], Cent))- 转换发生在哪里？

注意:作为 SO 的新手，我无法在原始答案下方评论，这可能更合适，但我希望这也是有用的。

Answer 1

1. since this is about counting combinations, why Solved Cent and not Solved Int? (This may sound like a nitpic, if it is even a reasonable question, but I am hoping it may be the root of the rest of the uncertainty, below, although I suspect I missed something more fundamental!).

我也会在这里使用 Int。

2. since we're later summing, in divide, Solved 0/1 presumably signifies failure/success?

是的，但还不止于此。 Solved 0 表示“恰好有 0 种方法来生成该更改量”(即失败)，而 Solved 1 表示“恰好有 1 种方法来生成该更改量” "(即成功)。在后一种情况下，我们不仅表示“成功”，而且还报告只有一种方法可以解决任务。

3. in conquer, what does it mean to add, a and b, of Pending? What do those 2 values (as Cents) signify, and what would their sum mean in this context?

本质上，Pending a b 和 a,b::Int 的意思是“生成零钱的方法数可以分成两个不相交的集合，第一个具有 a 元素，第二个具有 b 元素”。

当我们划分时，我们返回Pending ... ...将问题分成两个不相交的子情况，(coins, n - x) 和 (xs, n)。这里 coins=(x:xs)。我们根据是否要使用硬币 x 至少一次(因此我们需要用所有硬币生成 n-x )进行拆分，或者我们不想使用它根本没有(因此我们只需要用其他硬币生成 n)。

4. in conquer, I would have expected we just need to sum the Solveds, and the author touches on this, but it's not clear, yet, how the Pending case is contributing (eg fixing conquer (Pending a b) = 11 does have an adverse impact on functionality, and it is probably a clue that waysToMakeChange returns 11, or whatever constant that case is fixed to).

总结所有 Solved ... 就是我们所做的。 cata 魔法基本上取代了简单的递归求和

foo (Solved n) = n
foo (Pending case1 case2) = foo case1 + foo case2

用 cata conquer 在哪里

conquer (Solved n) = n
conquer (Pending a b) = a + b

cata 的神奇之处在于，在 Pending 中，我们找不到要递归的子树，而是递归的结果，已经计算出来了。

5. in conquer, a and b are Cents, whereas in divide they're ChangePuzzleArgs (aka ([Cent], Cent)) - where does that transformation occur?

一开始这确实很微妙。我只会提供粗略的直觉。

在除法之后，我们在仿函数ChangePuzzle 的不动点中产生一个结果。请注意最后的 ana 是如何返回 Term ChangePuzzle 的，这是不动点。在那里，([Cent], Cent) 对神奇地消失了。

双重地，当我们使用 cata 时，Int 再次出现，即使我们从 Term ChangePuzzle 开始也是如此。

非常粗略地说，您可以将 Term ChangePuzzle 视为无限嵌套

ChangePuzzle (ChangePuzzle (ChangePuzzle ( ....

这与这样的树可以任意嵌套的事实是一致的。在那里，ChangePuzzle 的“争论”基本上消失了。

那我们如何得到最终的Int呢？好吧，我们明白了，因为 Solved 总是采用 Int 参数，而不是 a 参数。这提供了使最终 cata 递归工作的基本情况。