根据所有先前的术语计算列表的术语

Question

我有以下标识,它(隐式)定义正整数的分区数(即,您可以将整数写为有序正非零整数之和的方式):

一些说明:

1. 这在Flajolet和Sedjewick的Analytic Combinatorics一书中进行了研究,并且该公式的图像来自那里,因为stackoverflow不支持LaTeX.

2. sigma是一个数的除数的总和

我想编写一个计算带有P系数的列表的haskell程序.第i个术语取决于所有先前的术语(是压缩sigma和之前的Ps导致的列表的总和).这个问题就是如何从规范中"计算"程序的一个很好的例子,就像Gibbons在他的论文中写道的那样.

问题是:是否存在捕获此类计算的已知递归方案？列表中的每个术语都取决于所有先前术语的计算(并且结果与之前的术语无关,我的意思是,您必须为每个术语执行新的遍历)

Answer 1

法定微积分警告.这个问题的基本答案涉及专门化标准递归方案.但是我有点拉扯它的线索.当我试图将相同的方法应用于除列表之外的结构时,事情变得更加抽象.我最终选择了Isaac Newton和Ralph Fox,并且在此过程中设计了alopegmorphism,这可能是新的东西.

但无论如何,应该存在某种类型的东西.它看起来像是变形或"展开" 的特例.让我们从unfoldr库中调用的内容开始.

unfoldr :: (seed -> Maybe (value, seed)) -> seed -> [value]

它显示了如何使用称为余代数的函数重复从种子中生成值列表.在每一步中,余代数都表示是否[]通过将价值计入新种子的清单来停止或继续进行.

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))

在一个变形现象中,余代数使用种子为最外层节点选择一个形状,并用子结构填充子结构.(Co)递归地,我们将变形图映射到,将这些种子生长成子结构.

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)

意思是"无聊的标签(零)或value标签和子列表的(cons)对".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？一个好的开始是为最外层节点选择形状.类型的值f ()仅给出节点的形状,子结构位置具有普通的存根.事实上,为了种植我们的树木,我们基本上需要一些方法来选择"下一个"节点形状,给出一些想法我们已经到达的地方以及到目前为止我们已经做了什么.我们应该期待

grow :: (..where I am in a Nu f under construction.. -> f ()) -> Nu f

请注意,对于增长列表,我们的步骤函数返回a ListF value (),它是同构的Maybe value.

但是Nu f,到目前为止,我们如何表达我们所处的位置？我们将从结构的根部进入如此多的节点,因此我们应该期待一堆层.每一层都应该告诉我们(1)它的形状,(2)我们当前所处的位置,以及(3)已经建立在该位置左侧的结构,但我们期望在我们的位置仍然存在短截线还没来.换句话说,它是我2008年POPL论文中关于Clowns和Jokers的解剖结构的一个例子.

解剖操作员将f仿函数(被视为元素的容器)转换为Diss f具有两种不同元素的bifunctor ,左边的那些元素(小丑)和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 fbifunctor相当于f只包含小丑的结构,而Jokers f只有小丑.如果你对所有Functor用具的重复感到困扰Bifunctor,那么你就会感到困扰:如果我们抽象出来并在索引集之间使用仿函数,它会变得不那么费力,但那是另一个故事.

让我们将解剖定义为一个将bifunctor与仿函数联系起来的类.

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的歌曲"与你一同陷入困境".)

该类中的关键操作是同构rightward,它告诉我们如何从一个地方向右移动一个地方

• 左边是一个充满笑话的整个结构,或者
• 结构中的一个洞,连同一个小丑放入洞中

到达任何一个

• 结构中的一个洞,以及从它出来的小丑,或者
• 一个充满小丑的整个结构的权利.

艾萨克牛顿喜欢解剖,但他称他们分裂差异并在实值函数上定义它们以获得曲线上两点之间的斜率,从而

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只是一个变形,因为列表节点最多只有一个孩子.

毕竟,这是一种新的东西,从无到有增长,但允许后来在给定层的增长依赖于早期的树木,福克斯衍生物捕捉到"我们尚未工作的存根"的想法.也许我们应该把它称为一个变形,从希腊语αλωπηξ为"狐狸".

Answer 2

如何使用自我引用和懒惰？

假设σ的值是无限的名单sigma,然后

p = [sum (zipWith (*) sigmas (reverse ps)) | ps <- inits p]

会非常巧妙地实现这种递归.

n为了简化代码,我忽略了这里的因素,也因为我不确定P_0应该是什么.