如何表示自然数以提供恒定的时间添加？

Question

Cirdec对一个很大程度上不相关的问题的回答让我想知道如何最好地用恒定时间加法表示自然数,减去1,并测试零.

为什么Peano算术不够好:

假设我们使用

data Nat = Z | S Nat

然后我们可以写

Z + n = n
S m + n = S(m+n)

我们可以m+n通过放置m-r借方(对于某些常数r)在O(1)时间内计算,每个S构造函数添加一个n.为了获得O(1)isZero,我们需要确保p每个S构造函数的最多借位,对于某些常量p.如果计算的话a + (b + (c+...)),这个效果很好,但是如果计算的话,它会分崩离析((...+b)+c)+d.问题是借方在前端叠加.

一种选择

最简单的方法就是直接使用可伸缩列表,例如Okasaki描述的列表.有两个问题:

1. O(n)空间并不是很理想.

2. 当我们不关心列表的排序时,并不完全清楚(至少对我而言)引导队列的复杂性是必要的.

Answer 1

据我所知,Idris(一种非常接近Haskell的依赖类型的纯函数式语言)以一种非常直接的方式处理这个问题.编译器知道Nats和Fins(上限Nats)并尽可能用机器整数类型和操作替换它们,因此生成的代码非常有效.但是,对于自定义类型(甚至是同构类型)以及编译阶段来说,情况并非如此(有些代码示例使用Nats进行类型检查,导致编译时指数增长,如果需要,我可以提供它们).

在Haskell的情况下,我认为可以实现类似的编译器扩展.另一种可能性是制作可以转换代码的TH宏.当然,这两种选择并不容易.

Answer 2

我的理解是，在基本计算机编程术语中，根本问题是您想要在恒定时间内连接列表。这些列表没有诸如前向引用之类的作弊功能，因此您无法在 O(1) 时间内跳到末尾。

a+(b+(c+...))您可以改用环，无论是否((...+c)+b)+a使用逻辑，都可以在 O(1) 时间内合并环。环中的节点不需要双向链接，只需链接到下一个节点即可。

减法是删除任何节点，O(1)，并且测试零（或一）是微不足道的。然而，测试的时间复杂度为n > 1O(n)。

如果您想减少空间，那么在每次操作时，您可以合并插入点或删除点处的节点，并提高剩余节点的权重。执行的操作越多，表示就越紧凑！不过，我认为最坏的情况仍然是 O(n)。