3

我在寻找hylomorhism示例时遇到了@amalloy 关于 SO 的一篇不错的帖子，它通过有用的讨论和完整的实现来说明递归方案 (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？（如果这是一个合理的问题，这可能听起来像一个小问题，但我希望它可能是下面其余不确定性的根源，尽管我怀疑我错过了一些更基本的东西！）。
  2. 因为我们稍后在 中求和，所以divide0/1Solved大概表示失败/成功？
  3. 在 中，添加和是conquer什么意思？这两个值（作为s）表示什么，在这种情况下它们的总和意味着什么？abPendingCent
  4. 在 中conquer，我原以为我们只需要对Solveds 求和，作者就谈到了这一点，但目前尚不清楚这个Pending案例是如何起作用的（例如，修复conquer (Pending a b) = 11 确实对功能产生不利影响，这可能是一个线索waysToMakeChange返回，11或该情况固定为的任何常数）。
  5. in conquer, aand bare Cents, 而 in dividetheyre ChangePuzzleArgs(aka ([Cent], Cent)) - 转换发生在哪里？

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

4

1 回答 1

2
  1. 因为这是关于计算组合，为什么Solved Cent而不是Solved Int？（如果这是一个合理的问题，这可能听起来像是一个小问题，但我希望它可能是下面其余不确定性的根源，尽管我怀疑我错过了更基本的东西！）。

我也会Int在这里使用。

  1. 因为我们后来在除法中求和，Solved 0/1大概意味着失败/成功？

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

  1. 在 中，添加和是conquer什么意思？这两个值（as ）表示什么，在这种情况下它们的总和意味着什么？abPendingCents

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

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

  1. 在 中conquer，我原以为我们只需要对Solveds 求和，作者就谈到了这一点，但目前尚不清楚待处理的案例是如何做出贡献的（例如，修复conquer (Pending a b) = 11确实对功能产生不利影响，这可能是返回 11 的线索waysToMakeChange，或该情况固定为的任何常数）。

总结所有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，我们找不到要递归的子树，而是已经计算出的递归结果。

  1. in conquer, aand bare Cents, 而 in dividetheyre ChangePuzzleArgs(aka ([Cent], Cent)) - 这种转换发生在哪里？

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

在ana divide我们在函子的一个不动点上产生一个结果ChangePuzzle。注意ana最后是如何返回的Term ChangePuzzle，这是固定点。在那里，这对([Cent], Cent)神奇地消失了。

双重的，Int当我们使用 时cata，即使我们从 开始，也会重新出现Term ChangePuzzle。

非常粗略，你可以认为是Term ChangePuzzle无限嵌套

ChangePuzzle (ChangePuzzle (ChangePuzzle ( ....

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

那我们怎么打决赛Int呢？好吧，我们明白了，因为Solved总是需要一个Int论点，而不是一个a论点。这提供了使最终cata递归工作的基本情况。

于 2021-12-13T12:52:33.947 回答