我有以下身份，它（隐式）定义了正整数的分区数（即，您可以将整数写为有序非零正整数之和的方式数）：
一些注意事项：
这在 Flajolet 和 Sedjewick 的 Analytic Combinatorics 一书中进行了研究，公式的图像取自那里，因为 stackoverflow 不支持 LaTeX。
sigma 是一个数的除数之和
我想编写一个计算带有 P 系数的列表的 haskell 程序。第 i 项取决于所有先前的项（是压缩 sigma 和先前 Ps 产生的列表的总和）。这个问题是一个很好的例子，说明如何根据规范“计算”程序，就像 Gibbons 在他的论文中所写的那样。
问题是：是否有已知的递归方案可以捕获这种计算？列表中的每个术语都依赖于所有先前术语的计算，（并且结果与先前的术语无关，我的意思是，您必须对每个术语进行新的遍历）
法定微积分警告。这个问题的基本答案涉及专门的标准递归方案。但我有点得意忘形了。当我试图将相同的方法应用于列表以外的结构时，事情变得更加抽象。我最终找到了艾萨克·牛顿和拉尔夫·福克斯，并在此过程中设计了异形体，这可能是新事物。
但无论如何，这种东西应该存在。它看起来像是变形或“展开”的特例。让我们从unfoldr库中调用的内容开始。
unfoldr :: (seed -> Maybe (value, seed)) -> seed -> [value]
它展示了如何通过重复使用一个名为coalgebra的函数从种子中生成值列表。在每一步，余代数[]都会通过将一个值添加到从新种子生成的列表中来决定是停止还是继续。
unfoldr coalg s = case coalg s of
Nothing -> []
Just (v, s') -> v : unfoldr coalg s'
在这里，种子类型可以是任何你喜欢的——任何适合展开过程的本地状态。种子的一个完全合理的概念就是“到目前为止的列表”，可能是相反的顺序，因此最近添加的元素是最近的。
growList :: ([value] -> Maybe value) -> [value]
growList g = unfoldr coalg B0 where
coalg vz = case g vz of -- I say "vz", not "vs" to remember it's reversed
Nothing -> Nothing
Just v -> Just (v, v : vz)
在每一步，我们的g操作都会查看我们已经拥有的值的上下文并决定是否添加另一个：如果是这样，新值将成为列表的头部和新上下文中的最新值。
因此，这growList会在每一步为您提供先前结果的列表，为zipWith (*). 反转对于卷积来说相当方便，所以也许我们正在寻找类似的东西
ps = growList $ \ pz -> Just (sum (zipWith (*) sigmas pz) `div` (length pz + 1))
sigmas = [sigma j | j <- [1..]]
也许？
递归方案？对于列表，我们有一个变形的特殊情况，其中种子是我们迄今为止构建的上下文，一旦我们说过如何构建更多，我们就知道如何通过相同的方式扩展上下文令牌。不难看出这对列表是如何工作的。但一般来说，它是如何处理变形的呢？这就是事情变得多毛的地方。
我们建立可能无限的值，其节点形状由某个函子给出f（当我们“打结”时，其参数结果是“子结构”）。
newtype Nu f = In (f (Nu f))
在变形中，余代数使用种子为最外层节点选择形状，其中填充了子结构的种子。（共同）递归地，我们映射变形，将这些种子生长成子结构。
ana :: Functor f => (seed -> f seed) -> seed -> Nu f
ana coalg s = In (fmap (ana coalg) (coalg s))
unfoldr让我们从重构ana。Nu我们可以从几个简单的部分构建许多普通的递归结构：多项式 Functor 工具包。
newtype K1 a x = K1 a -- constants (labels)
newtype I x = I x -- substructure places
data (f :+: g) x = L1 (f x) | R1 (g x) -- choice (like Either)
data (f :*: g) x = f x :*: g x -- pairing (like (,))
有Functor实例
instance Functor (K1 a) where fmap f (K1 a) = K1 a
instance Functor I where fmap f (I s) = I (f s)
instance (Functor f, Functor g) => Functor (f :+: g) where
fmap h (L1 fs) = L1 (fmap h fs)
fmap h (R1 gs) = R1 (fmap h gs)
instance (Functor f, Functor g) => Functor (f :*: g) where
fmap h (fx :*: gx) = fmap h fx :*: fmap h gx
对于 的列表value，节点形状函子是
type ListF value = K1 () :+: (K1 value :*: I)
意思是“一个无聊的标签（对于 nil）或标签和子列表的（缺点）对value”。ListF value余代数的类型变为
seed -> (K1 () :+: (K1 value :*: I)) seed
这是同构的（通过“评估”多项式）ListF value到seed
seed -> Either () (value, seed)
这只是头发的宽度
seed -> Maybe (value, seed)
期望unfoldr。您可以像这样恢复普通列表
list :: Nu (ListF a) -> [a]
list (In (L1 _)) = []
list (In (R1 (K1 a :*: I as))) = a : list as
现在，我们如何培养一些将军Nu f？一个好的开始是选择最外层节点的形状。type 的值f ()仅给出节点的形状，在子结构位置中具有琐碎的存根。事实上，为了种植我们的树，我们基本上需要一些方法来选择“下一个”节点形状，因为我们需要了解我们已经到达的位置以及到目前为止我们所做的事情。我们应该期待
grow :: (..where I am in a Nu f under construction.. -> f ()) -> Nu f
请注意，对于不断增长的列表，我们的 step 函数返回 a ListF value ()，它与 同构Maybe value。
但是我们如何表达我们目前所处的位置Nu f呢？我们将从结构的根开始有这么多节点，所以我们应该期待一堆层。每一层都应该告诉我们 (1) 它的形状，(2) 我们当前在哪个位置，以及 (3) 已经在该位置左侧构建的结构，但我们希望在我们的位置仍然有存根还没有到。换句话说，这是我 2008 年关于小丑和小丑的 POPL 论文中的剖析结构示例。
剖析运算符将函子f（被视为元素的容器）转换为具有两种不同类型元素的双函子，即结构Diss f内“光标位置”的左侧（小丑）和右侧（小丑）元素。f首先，让我们拥有Bifunctor类和一些实例。
class Bifunctor b where
bimap :: (c -> c') -> (j -> j') -> b c j -> b c' j'
newtype K2 a c j = K2 a
data (f :++: g) c j = L2 (f c j) | R2 (g c j)
data (f :**: g) c j = f c j :**: g c j
newtype Clowns f c j = Clowns (f c)
newtype Jokers f c j = Jokers (f j)
instance Bifunctor (K2 a) where
bimap h k (K2 a) = K2 a
instance (Bifunctor f, Bifunctor g) => Bifunctor (f :++: g) where
bimap h k (L2 fcj) = L2 (bimap h k fcj)
bimap h k (R2 gcj) = R2 (bimap h k gcj)
instance (Bifunctor f, Bifunctor g) => Bifunctor (f :**: g) where
bimap h k (fcj :**: gcj) = bimap h k fcj :**: bimap h k gcj
instance Functor f => Bifunctor (Clowns f) where
bimap h k (Clowns fc) = Clowns (fmap h fc)
instance Functor f => Bifunctor (Jokers f) where
bimap h k (Jokers fj) = Jokers (fmap k fj)
请注意，Clowns f双函子相当于一个f只包含小丑的结构，而Jokers f只有小丑。如果您对重复所有Functor用具来获得Bifunctor用具感到困扰，那么您的烦恼是正确的：如果我们抽象出 arity 并在索引集之间使用函子，它会变得不那么费力，但那是另一回事了。
让我们将解剖定义为将双函子与函子相关联的类。
class (Functor f, Bifunctor (Diss f)) => Dissectable f where
type Diss f :: * -> * -> *
rightward :: Either (f j) (Diss f c j, c) ->
Either (j, Diss f c j) (f c)
该类型Diss f c j表示f在一个元素位置具有“孔”或“光标位置”的结构，在孔的左侧我们有“小丑” c，在右侧我们有“小丑” j。（该术语取自Stealer's Wheel歌曲“Stuck in the Middle with You”。）
类中的关键操作是同构rightward，它告诉我们如何将一个位置向右移动，从任一位置开始
并到达
艾萨克·牛顿（Isaac Newton）喜欢解剖，但他称它们为除差，并在实值函数上定义它们以获得曲线上两点之间的斜率，因此
divDiff f c j = (f c - f j) / (c - j)
他使用它们对任何旧函数等进行最佳多项式逼近。相乘和相乘
divDiff f c j * c - j * divDiff f c j = f c - f j
然后通过加到两边来摆脱减法
f j + divDiff f c j * c = f c + j * divDiff f c j
你有rightward同构。
如果我们查看实例，我们可能会为这些事情建立更多的直觉，然后我们可以回到我们最初的问题。
一个无聊的旧常数的除差为零。
instance Dissectable (K1 a) where
type Diss (K1 a) = K2 Void
rightward (Left (K1 a)) = (Right (K1 a))
rightward (Right (K2 v, _)) = absurd v
如果我们从左到右，我们会跳过整个结构，因为没有元素位置。如果我们从元素位置开始，有人在撒谎！
恒等函子只有一个位置。
instance Dissectable I where
type Diss I = K2 ()
rightward (Left (I j)) = Left (j, K2 ())
rightward (Right (K2 (), c)) = Right (I c)
如果我们从左边开始，我们到达位置并弹出小丑；推一个小丑，我们在右边完成。
对于总和，结构是继承的：我们只需要正确地进行去标签和重新标签。
instance (Dissectable f, Dissectable g) => Dissectable (f :+: g) where
type Diss (f :+: g) = Diss f :++: Diss g
rightward x = case x of
Left (L1 fj) -> ll (rightward (Left fj))
Right (L2 df, c) -> ll (rightward (Right (df, c)))
Left (R1 gj) -> rr (rightward (Left gj))
Right (R2 dg, c) -> rr (rightward (Right (dg, c)))
where
ll (Left (j, df)) = Left (j, L2 df)
ll (Right fc) = Right (L1 fc)
rr (Left (j, dg)) = Left (j, R2 dg)
rr (Right gc) = Right (R1 gc)
对于产品，我们必须在一对结构中的某个位置：要么我们在左边的小丑和小丑之间，右边的结构都是小丑，或者左边的结构都是小丑，我们在右边的小丑和小丑之间。
instance (Dissectable f, Dissectable g) => Dissectable (f :*: g) where
type Diss (f :*: g) = (Diss f :**: Jokers g) :++: (Clowns f :**: Diss g)
rightward x = case x of
Left (fj :*: gj) -> ll (rightward (Left fj)) gj
Right (L2 (df :**: Jokers gj), c) -> ll (rightward (Right (df, c))) gj
Right (R2 (Clowns fc :**: dg), c) -> rr fc (rightward (Right (dg, c)))
where
ll (Left (j, df)) gj = Left (j, L2 (df :**: Jokers gj))
ll (Right fc) gj = rr fc (rightward (Left gj)) -- (!)
rr fc (Left (j, dg)) = Left (j, R2 (Clowns fc :**: dg))
rr fc (Right gc) = Right (fc :*: gc)
rightward逻辑确保我们通过左侧结构工作，然后一旦我们完成它，我们就开始在右侧工作。标记的线(!)是中间的关键时刻，我们从左侧结构的右侧出现，然后进入右侧结构的左侧。
Huet 的数据结构中“左”和“右”光标移动的概念源于可剖析性（如果您完成了rightward与其leftward对应物的同构）。的导数只是f当小丑和小丑之间的差异趋于零时的极限，或者对我们来说，当光标两边都有相同类型的东西时，你会得到什么。
此外，如果你把小丑归零，你会得到
rightward :: Either (f x) (Diss f Void x, Void) -> Either (x, Diss f Void x) (f Void)
但我们可以去掉不可能的输入情况得到
type Quotient f x = Diss f Void x
leftmost :: f x -> Either (x, Quotient f x) (f Void)
leftmost = rightward . Left
它告诉我们每个f结构要么有一个最左边的元素，要么根本没有，这是我们在学校学习的“剩余定理”的结果。运算符的多元版本Quotient是 Brzozowski 应用于正则表达式的“导数”。
但我们的特例是 Fox 的导数（我从Dan Piponi那里了解到）：
type Fox f x = Diss f x ()
这是在f光标右侧带有存根的结构类型。现在我们可以给出通用grow运算符的类型。
grow :: Dissectable f => ([Fox f (Nu f)] -> f ()) -> Nu f
我们的“上下文”是一堆层，每一层在左边都有完全增长的数据，在右边有存根。我们可以grow直接实现如下：
grow g = go [] where
go stk = In (walk (rightward (Left (g stk)))) where
walk (Left ((), df)) = walk (rightward (Right (df, go (df : stk))))
walk (Right fm) = fm
当我们到达每个位置时，我们提取的小丑只是一个存根，但它的上下文告诉我们如何扩展堆栈以增长树的子结构，这给了我们需要向右移动的小丑。一旦我们用树填充了所有的存根，我们就完成了！
但这里有一个转折点：grow不像变形那样容易表达。为每个节点的最左边的孩子提供“种子”很容易，因为我们只有右边的存根。但是要将下一粒种子传给右边，我们需要的不仅仅是最左边的种子——我们需要从它长出的树！变形模式要求我们在生长任何子结构之前提供所有子结构的种子。我们growList是一种变形，只是因为列表节点最多有一个孩子。
所以它毕竟是新事物，从无到有，但允许给定层的后期增长依赖于早期的树，Fox 衍生品捕捉了“我们尚未工作的存根”的想法。也许我们应该称它为异形，来自希腊语αλωπηξ的“狐狸”。
使用自我引用和懒惰怎么样？
假设 σ 的值在无限列表 中sigma，则
p = [sum (zipWith (*) sigmas (reverse ps)) | ps <- inits p]
将非常巧妙地实现此递归。
我忽略了n这里的因素，为了代码的简单，也因为我不确定 P_0 应该是什么。