自然数如何表示提供恒定的时间加法？
对于一个基本上不相关的问题， Cirdec的答案让我想知道如何用恒定的时间加法表示自然数，减去一个数，然后testing零。
为什么皮亚诺算术不够好：
假设我们使用
data Nat = Z | S Nat 那我们可以写
Z + n = n S m + n = S(m+n)
我们可以在O（1）时间内计算m+n ，通过放置mr借记（对于某个常量r ），每个S构造函数添加一个到n 。 为了得到O（1） isZero ，我们需要确保每S构造函数至多有p isZero ，对于一些常量p 。 如果我们计算a + (b + (c+...)) ，这个效果很好，但是如果我们计算((...+b)+c)+d ，它会分解。 麻烦的是，借方在前端堆积起来。
一个选项
简单的解决方法就是直接使用Okasaki描述的可链接列表。 有两个问题：
-
O（n）空间不是很理想。
-
至less对我而言，并不是完全清楚的是，当我们不关心按照列表的方式排列时，引导队列的复杂性是必要的。
据我所知，Idris（一个与Haskell非常接近的依赖types的纯函数式语言）以相当直接的方式处理这个问题。 编译器知道Nat和Fin （上限Nat ），并尽可能用机器整数types和操作replace它们，所以生成的代码是非常有效的。 然而，对于自定义types（甚至是同构的）以及编译阶段（有一些使用Nat进行types检查的代码样本导致编译时指数增长，如果需要，我可以提供这些代码样本），情况并非如此。
在Haskell的情况下，我认为可能会实现一个类似的编译器扩展。 另一种可能性是使THmacros变换代码。 当然，这两个选项都不容易。
我的理解是，在基本的计算机编程术语中，根本问题是你想要连续列表。 例如，这个列表没有像向前引用那样的秘籍，所以你不能在O（1）的时候跳到结尾。
无论是a+(b+(c+...))还是使用((...+c)+b)+a逻辑，都可以使用环来代替O（1）时间。 环中的节点不需要双向链接，只是到下一个节点的链接。
减法是删除任何节点，O（1），并testing零（或一）是微不足道的。 然而，testingn > 1是O（n）。
如果你想减less空间，那么在每个操作中，你可以合并插入或删除点上的节点，并加权剩下的节点。 你做的操作越多，表示就越紧凑！ 但是，我认为最坏的情况仍然是O（n）。
我们知道有两个“极值”解决scheme可以有效地添加自然数：
- 高效的内存，使用O（log n）内存的自然数的标准二进制表示，并且需要O（log n）时间来添加。 （另见冈崎书中的 “二进制表示法”一章。）
-
只使用O（1）次的CPU效率。 （请参阅本书的“结构抽象”一章。）但是，解决scheme使用O（n）内存，因为我们将自然数n表示为
()的n个副本的列表。我没有做过实际的计算，但是我相信对于O（1）数值加法，我们将不需要O（1）个 FIFO队列的全部function，只需引导标准列表
[]（LIFO）以同样的方式。 如果你有兴趣，我可以试着详细说明一下。
CPU高效的解决scheme的问题是，我们需要添加一些冗余的内存表示，以便我们可以腾出足够的CPU时间。 在某些情况下，添加这样的冗余可以在不影响存储容量的情况下完成（例如O（1）增加/减less操作）。 而且，如果我们允许任意树形状，就像带有自举列表的CPU高效解决scheme，那么在O（log n）内存中就有太多的树形状来区分它们。
所以问题是：我们能否find恰到好处的冗余，这样子线性的内存量就足够了，并且可以实现O（1）加法？ 我相信答案是否定的 ：
让我们有一个O（1）时间加法的表示+algorithm。 那么我们有一个m位的数量，我们将其计算为2 ^ k个数字的总和，它们中的每一个都是（mk）位的数量级。 为了表示我们所需要的每一个加数（不pipe表示），最小的（mk）位存储器，所以在开始时，我们从（至less） （mk）2 ^ k位的存储器开始。 现在，在每一个2 ^ k的加法中，我们被允许执行一个恒定的操作，所以我们能够处理（并且理想地移除）总共2 ^ 2个比特。 因此，最后，我们需要表示结果的比特数的下限是（mkC）2 ^ k个比特。 由于k可以任意select，所以我们的对手可以设置k = mC-1 ，这意味着总和将表示为至less2 ^（mC-1）= 2 ^ m / 2 ^（C + 1）∈O 2 ^ m）位。 所以一个自然数n总是需要O（n）位的内存！
